Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.16 No.3 pp.307-315
DOI : https://doi.org/10.7232/iems.2017.16.3.307

A Fuzzy Ant Colony Approach to Fully Fuzzy Resource Constrained Project Scheduling Problem

Amir Yousefli*
Department of Industrial Management, Imam Khomeini International University, Qazvin, Iran
Corresponding Author, yousefli@soc.ikiu.ac.ir,
April 2, 2017 July 19, 2017 August 21, 2017

ABSTRACT

In this paper a fully fuzzy resource constrained project scheduling model is presented in which activities durations and resource consumptions of activities are estimated by fuzzy numbers. To increase compatibility between presented model and real world situations, availability of resources are predicted using fuzzy numbers. Taking into account the concept of “fuzzy decision making in fuzzy environment” and regarding the fact that all parameters of the presented model are uncertain, fuzzy scheduling is considered for this problem in which activities start and finish times are calculated in form of triangular fuzzy numbers. Also, due to this fact that resource constrained project scheduling problems (RCPSPs) belong to the class of the NP-hard problems, a solution approach is developed using Ant Colony Optimization (ACO) algorithm. Regarding fuzzy nature of decision variables, some modifications are made to ACO to make it compatible with the presented fuzzy RCPS model. To illustrate flexibility of the developed model and efficiency of the presented solution approach, some numerical examples are provided.


초록


    1.INTRODUCTION

    A resource constrained project scheduling problem (RCPSP) is a problem of scheduling a set of activities that should be sequenced in order to determine the optimal starting and finishing times of activities under resource constraint (Knyazeva et al., 2015). It is a popular NP-hard optimization problem and various searching methods, including exact methods, heuristic and metaheuristic procedures, have been proposed to solve this problem on the wide variety of assumptions (Ghoddousi et al., 2013). In a general classification, RCPS models can be categorized into two classes: deterministic scheduling and nondeterministic scheduling. Most of the presented models in the literature focus on deterministic scheduling. Comprehensive review of these models can be found in Artigues et al. (2013), Brucker et al. (1999), Abdolshah (2014), Kis (2005), Kolisch and Padman (2001) and Kolisch (2013).

    Due to the uniqueness of some projects, providing exact estimations for activities durations and resources consumptions as well as availability of resources at project initialization stage may not be possible. In such situations, uncertain scheduling methods could help project managers. RCPS models can be categorized into three classes in terms of uncertainty type: stochastic scheduling, fuzzy scheduling and hybrid (fuzzy-stochastic) scheduling. It has been claimed that fuzzy set theory is more appropriate to model uncertainty associated with parameters such as time, resource availability, resource consumption and etc. In practice, regarding lack of information about activities, values of the project parameters are often estimated by project managers and experts in the form of linguistic variables. These type of information might be best modeled by fuzzy numbers instead of probabilistic ones. Literature of fuzzy RCPSP is very rich. The model presented by Pan and Yeh (2004) is one of the fuzzy mathematical optimization models in which a fuzzy multi objective model was presented to formulate multimode resource constrained project scheduling problem. Lai and Li (1999) and Hussein and Abo-Sinna (1995) utilized fuzzy dynamic programming to model fuzzy RCPS problem. Fu and Wang (1996) proposed single objective and multi objective models to deal with resource allocation problems in fuzzy environment.

    Considering the order of complexity in RCPS problems, it has been proved that these problems belong to the class of NP-hard problems (Knyazeva et al., 2015; Jozefowska et al., 2000; Leon and Balakrishnan, 1995). So, in the optimization models, by increasing number of the project activities, activities performing mode or number of resources, the required time to solve the problem rises sharply. Therefore, the heuristic and metaheuristic methods can be used efficiently to tackle this problem. One of the metaheuristic solution approaches to solve fuzzy RCPS problem was presented by Pan and Yeh (2003). They used simulated annealing algorithm to solve this problem. Ji and Yao (2017) presented an uncertain project scheduling model in which both duration times and resources allocation times are uncertain. They developed an uncertain multi-objective optimization model in which minimization of total cost and overtime were considered as objective functions. Knyazeva et al. (2015) presented a fuzzy heuristic approach to obtain a near optimal solution in a reasonable computational time for RCPS problem in fuzzy environment. Also, Leu et al. (1999) utilized genetic algorithm to solve fuzzy RCPS problems. Ma et al. (2016) considered the RCPS problem with renewable resource constraints in uncertain environment, in which activities durations were estimated by belief degrees. They used a hybrid approach based on genetic algorithm and 99-method based uncertain simulation to obtain the quasi-optimal schedule. Afruzi et al. (2013) considered a multi-mode resource constrained discrete time–cost tradeoff problem and developed an adjusted fuzzy dominance genetic algorithm (AFDGA) to solve proposed model. Kaveh et al. (2016) utilized two new metaheuristic algorithms known as charged system search (CSS) and colliding body optimization (CBO) to solve fuzzy resource constrained project scheduling problem (FRCPSP). Meng and Wang (2013) discussed a resource constrained project scheduling problem considering fuzzy nature of data in uncertain environment and presented a solution approach using artificial immune algorithm. Hapke et al. (1997) developed an approach based on Pareto simulated annealing (PSA) to solve fuzzy RCPS problems. Xu and Feng (2014) presented a multi objective multi-mode RCPS model for large scale construction projects in fuzzy random environment. They considered cost, weighted makespan and quality as objectives and used a combinatorial- priority based hybrid particle swarm optimization algorithm to solve developed model. Kim et al. (2003) developed a hybrid genetic algorithm with fuzzy logic controller to solve the resource constrained project scheduling problem. They used fuzzy logic controller to design genetic algorithm operators. Masmoudi and Hait (2013) provided an approach to keep uncertainty at all steps of modelling and solving procedure and considered two project scheduling techniques: resource constrained scheduling and resource leveling problem (RLP) in fuzzy environment. They presented a greedy algorithm and a genetic algorithm to solve FRCPSP and FRLP, respectively. Long and Ohsato (2008) developed a fuzzy critical chain method for project scheduling under resource constraints. The method consists of developing a desirable deterministic schedule under resource constraints and adding a project buffer to the end of the schedule to deal with uncertainty. Hapke and Slowinski (1996) proposed a heuristic model to deal with fuzzy RCPS problems by combining priority rules and fuzzy numbers ranking methods. In this model, they assumed duration of each activity is uncertain, whereas resource availability and resource demand of each activity are crisp. While in many projects in the real world, these two parameters, resource availability and resource demand of each activity, are uncertain, too. The research and development projects are among the cases in which the two mentioned parameters are widely uncertain. Yousefli et al. (2008) proposed a heuristic model to deal with these types of RCPS problems. Their approach was based on fuzzy decision making in fuzzy environment concept. In fuzzy decision making in fuzzy environment, not only the parameters but also the decision variables are considered uncertain. So, the purpose of solving problem under this concept is to calculate optimal possibility distributions of the objective functions as well as the decision variables. By contrast, in crisp optimization problems or deterministic decision making in fuzzy environment, the main focus is on finding optimum values for the objective function and the decision variables. In another attempt, Ghazanfari et al. (2008) developed a new approach to solve possibilistic time cost-trade off problems in which decision variables had triangular possibility distributions. Ke and Liu (2010) considered a project scheduling problem with fuzzy activities durations and presented three types of fuzzy models to solve this problem. Moreover, fuzzy simulation and genetic algorithm were integrated to design a hybrid intelligent algorithm to solve developed fuzzy models. Bhaskar et al. (2011) proposed a heuristic method, for resource con strained project scheduling problem with fuzzy activities durations.

    In this paper, a mathematical model for fully fuzzy resource constrained project scheduling is proposed. In this model the duration of each activity, the resource availability and the resource demand of each activity are considered to be uncertain and are defined by fuzzy numbers. Regarding the uncertainty of all parameters, and considering the concept of “fuzzy decision making in fuzzy environment” (Tanaka et al., 2000; Yousefli et al., 2008; Guo and Tanaka, 1996; Ghazanfari et al., 2007), activities schedule (start time and finish time of each activity) is calculated in the form of fuzzy numbers. This type of scheduling gathers all possible situations that could occur in future and helps project managers to make proper decisions. Due to the complexity degree of the presented model, a fuzzy ant colony optimization (FACO) algorithm is extended as a solution approach to tackle the projects with numerous activities. FACO is an extension of ACO in which a fuzzy numbers ranking method is employed to construct fuzzy solutions and also to evaluate created solutions.

    This paper is organized as follows. In second section, a fuzzy number ranking method which is used in this paper is introduced and third section consists of the proposed model for fully fuzzy resource constrained project scheduling problem. The solution approach based on fuzzy ant colony algorithm is presented in fourth section. Some numerical examples will be discussed in the fifth section to illustrate the flexibility of the proposed model and efficiency of the developed solution approach. Finally, in the last section, conclusions will be remarked.

    2.CHENG’S FUZZY NUMBERS RANKING METHOD

    In this paper the fuzzy numbers ranking method presented by Cheng (1998) is employed to formulate fuzzy RCPS model and also to extend ant colony optimization algorithm to fuzzy environment. Cheng (1998) proposed a fuzzy numbers ranking method based on calculating centroid point ( x 0 ¯ , y 0 ¯ ) of a fuzzy number A ˜ . Consider fuzzy number A ˜ is denoted by [a1, a2, a3] . The membership function of fuzzy number A ˜ can be expressed by:(1)

    μ A ˜ ( x ) = { μ A ˜ L ( x ) a 1 x a 2 1 x = a 2 μ A ˜ R ( x ) a 2 x a 3
    (1)

    Where μ A ˜ L ( x ) : [ a 1 , a 2 ] [ 0 , 1 ] is a continuous and strictly increasing function. Also, μ A ˜ R ( x ) : [ a 2 , a 3 ] [ 0 , 1 ] is a continuous and strictly decreasing function. So, inverse functions of both of them do exist and are denoted by g A ˜ L ( y ) and g A ˜ R ( y ) , respectively. Herein, we describe Cheng’s method for triangular fuzzy numbers through following steps:

    • Step 1: Centroid point ( x 0 ¯ , y 0 ¯ ) calculation

      For triangular fuzzy number A ˜ = [ a 1 , a 2 , a 3 ] , the membership function can be written as follows:(2)

      μ A ˜ ( x ) = { x a 1 a 2 a 1 a 1 x a 2 1 x = a 2 a 3 x a 3 a 2 a 2 x a 3
      (2)

      The inverse functions of μ A ˜ L ( x ) and μ A ˜ R ( x ) are g A ˜ L ( y ) = ( a 2 a 1 ) y + a 1 and g A ˜ R ( y ) = a 3 ( a 3 a 2 ) y , respectively. The centroid point ( x 0 ¯ , y 0 ¯ ) for a fuzzy number A ˜ is defined as follows:

      x ¯ 0 ( A ˜ ) = a 1 a 2 [ x μ A ˜ L ( x ) ] d x + a 2 a 3 [ x μ A ˜ R ( x ) ] d x a 1 a 2 μ A ˜ L ( x ) d x + a 2 a 3 μ A ˜ R ( x ) d x y ¯ 0 ( A ˜ ) = 0 1 [ y  g A ˜ L ( y ) ] d y + 0 1 [ y g A ˜ R ( y ) ] d y 0 1 g A ˜ L ( y ) d y + 0 1 g A ˜ R ( y ) d y
      (3)

      For triangular fuzzy numbers, Eq. (3) can be simplified as:(4)

      x ¯ 0 = a 3 2 a 1 2 + a 2 × a 3 a 2 × a 1 3 × ( a 3 a 1 ) y ¯ 0 = a 1 + 4 × a 2 + a 3 3 × ( a 1 + 2 × a 2 + a 3 )
      (4)

    • Step 2: Ranking function calculation

      The ranking index is the distance between the centroid point ( x 0 ¯ , y 0 ¯ ) and original point which can be expressed as:(5)

      R ( A ˜ ) = ( x ¯ 0 ) + ( y ¯ 0 ) 2
      (5)

    • Step 3: Fuzzy numbers ranking

      For any triangular fuzzy numbers A ˜ i and A ˜ j , Cheng’s method presents the following properties:(6)

      1) if  R ( A ˜ i ) > R ( A ˜ j ) ,  then  A ˜ i > A ˜ j 2) if  R ( A ˜ i ) = R ( A ˜ j ) ,    then  A ˜ i = A ˜ j 3) if  R ( A ˜ i ) < ( A ˜ j ) ,    then  A ˜ i < A ˜ j
      (6)

    3.FULLY FUZZY RESOURCE CONSTRAINED PROJECT SCHEDULING

    The problem that is discussed in this paper is a project scheduling problem under resource constraint, in which duration and resource demand of each activity as well as resource availability are uncertain and are depicted in the form of triangular fuzzy numbers. Minimization of makespan is the criteria which should be optimized under resource and precedence relationship constraints and fuzzy goal programming concept is used to solve it. In this paper, the concept of fuzzy decision making in fuzzy environment, which has rarely been used by researchers, is employed. Nature of fuzzy decision making in fuzzy environment allows us to directly consider the uncertainty associated with the parameters in final decisions. The assumptions of this model are as follows:

    • 1: Duration of each activity is estimated by triangular fuzzy number.

    • 2: Resources demands of each activity are estimated by triangular fuzzy numbers.

    • 3: Availability of each resource is uncertain and it is depicted in the form of triangular fuzzy number.

    • 4: Each activity is performed in one prescribed way (mode).

    • 5: Activities are shown in nodes in a precedence network.

    The parameters and the decision variable of the model are as follows:

    Parameters:

    • e s ˜ i : Earliest start time of ith activity

    • l s ˜ i : Latest start time of ith activity

    • Ck : The cost per unit of kth resource

    • r ˜ i k : The amount of resource k demanded by activity i

    • d ˜ i : Duration of activity i

    • Si : Set of activities that immediately begin after activity i

    • a ˜ k : Available amount of resource k

    • T ˜ : Estimation of project makespan

    • K : Number of renewable resources

    • n : Number of activities (first and last activities are dummy)

    • F S ˜ i j : Time lag between activities i and j

    Variable:

    x i t ˜ = { 1 If activity i starts in uncertain time   t ˜ 0 Otherwise

    The developed model for resource constrained project scheduling problem in fuzzy environment is as follows:

    min  z ˜ = t ˜ = e s ˜ n l s ˜ n t ˜ × x n t ˜
    (7)

    S.t.

    t ˜ = e s ˜ j l s ˜ j x j t ˜ = 1 , j = 1 , 2 , , n
    (8)

    t ˜ = e s ˜ i l s ˜ i t ˜ × x i t ˜ + d ˜ j + F S ˜ i j < t ˜ = e s ˜ j l s ˜ j t ˜ × x j t ˜ ,    j S i
    (9)

    i = 1 n r ˜ i j × s ˜ = max { t ˜ d ˜ i , e s ˜ i } min { t ˜ 1 , l s ˜ i } x i s ˜ a ˜ k ,    k = 1 , 2 , , K ;    t ˜ T ˜
    (10)

    The objective function (7) minimizes makespan of the project. Eq. (8) guarantees exactly one start time is assigned to each activity. Eq. (9) shows the precedence relationship between activities. Eq. (10) is the constraint on resources availability.

    e s ˜ i and l s ˜ i should be obtained using heuristic methods such as the model developed by Yousefli et al. (2008).

    Here, each period of time is shown as a triangular fuzzy number t ˜ = ( t α , t , t + β ) and it means “approximately tth time period.” t is mean value and α and β are left and right deviations, respectively. In this paper, without loss of generality, α and β are considered equal to 1. Also, the start time of project is (0, 0, 0). To solve the proposed model using fuzzy goal programming concept, an uncertain aspiration level for objective function must be obtained. This aspiration level could be asked of the decision maker or can be obtained using heuristic methods such as the one proposed by Yousefli et al. (2008). The obtained aspiration level for objective function (7) is named T ˜ . Therefore, the objective function (7) could be rewritten as follows:

    t ˜ = e s ˜ n l s ˜ n t ˜ × x n t ˜ T ˜
    (11)

    Relations (9), (10) and (11) are fuzzy inequalities, the right-hand sides and the left-hand sides of which are combinations of fuzzy variables and fuzzy numbers. Therefore, the decision vector must be determined in a way that constraints are satisfied and obtained uncertain value for the objective function is smaller than or equal to the aspiration level. To achieve these goals, the fuzzy numbers ranking method, discussed in the second section, is used. In other words, to satisfy constraints, the following equations must be met.(12)(13)

    R ( t ˜ = e s ˜ i l s ˜ i t ˜ × x i t ˜ + d ˜ j + F S ˜ i j ) < R ( t ˜ = e s ˜ j l s ˜ j t ˜ × x j t ˜ ) ,    j S i
    (12)

    R ( i = 1 n r ˜ i k × s ˜ = max { t ˜ d ˜ i , e s ˜ i } min { t ˜ 1 , l s ˜ i } x i s ˜ ) R ( a ˜ k ) ,      k = 1 , 2 , , K ; t ˜ T ˜
    (13)

    For the objective function it could be written:(14)

    R ( t ˜ = e s ˜ n l s ˜ n t ˜ × x n t ˜ ) R ( T ˜ )
    (14)

    In case of the aspiration level being crisp, R ( T ˜ ) should be replaced by T. Due to this fact that the objective function has cost nature, it should be obtained in a way that its value be as smaller as possible than the aspiration level. Therefore, d T ˜ is defined as follows:(15)

    d T ˜ = R ( T ˜ ) R ( t ˜ = e s ˜ n l s ˜ n t ˜ × x n t ˜ )
    (15)

    So, the objective function must be maximization of the d T ˜ and model (7)-(10) should be rewritten as follows:

    max   d T ˜ S . t . t ˜ = e s ˜ j l s ˜ j x j t ˜ = 1 , j = 1 , 2 , , n R ( t ˜ = e s ˜ i l s ˜ i t ˜ × x i t ˜ + d ˜ j + F S ˜ i j ) < R ( t ˜ = e s ˜ i l s ˜ i t ˜ × x j t ˜ ) , j S i R ( i = 1 n r ˜ i k × s ˜ = max { t ˜ d ˜ i , e s ˜ i } min { t ˜ 1 , l s ˜ i } x i s ˜ ) R ( a ˜ k ) ,      k = 1 , 2 , , K ;     t ˜ T ˜ d T ˜ = R ( T ˜ ) R ( t ˜ = e s ˜ n l s ˜ n t ˜ × x n t ˜ ) ,
    (16)

    Having model (16) solved, optimum values of start and finish times of each activity as well as project makespan are calculated as triangular fuzzy numbers. Consider resulted fuzzy makespan is denoted by M ˜ = ( M L , M M , M R ) , which could be shown schematically as Figure 1.

    As it is illustrated in Figure 1, project duration might take different values with different degrees of possibility (π (.)∈[0,1] ). For instance, makespan may be equal to M0 with possibility degree of π(M0). Also, when project manager wants to know the possibility degree for having the makespan within the interval [M1, M2], following equation could be used (Zimmermann, 2011):

    π ( M 1 m a k e s p a n M 2 ) = max { π { M } | M 1 M M 2 }
    (17)

    Such analysis on fuzzy results could help project managers to have a proper knowledge about several situations which may occur for the project duration in future.

    Model (16) is a fuzzy binary nonlinear programming problem that hardly could be solved with common mathematical methods. So, a metaheuristic method using ant colony optimization algorithm is developed in next section to deal with complexity of the proposed model.

    4.FUZZY ANT COLONY OPTIMIZATION ALGORITHM

    In an ACO algorithm, firstly, the parameters values and the initial pheromone trails are set and then, the algorithm builds solutions using a state transition rule. In each iteration online and offline pheromone update rules are utilized and the process continues until a stopping criterion is reached. The ACO algorithm which is developed to solve model (16) presents fuzzy solution instead of crisp schedule. In other words, a fuzzy ant colony optimization (FACO) algorithm is developed to solve fully fuzzy RCPS model. The pseudo code of FACO-RCPSP algorithm is given below:

    Initialize all parameters and the pheromone trails

    Loop

       Create the fuzzy schedule using the state transition rule

       Apply the online pheromone update rule

       Continue until all ants present a complete fuzzy schedule

       Evaluate all solutions using fuzzy numbers ranking method and keep the best one

       Apply the offline pheromone update rule

    Continue until the stopping criterion is reached

    4.1.State Transition Rule

    Each ant generates a complete feasible fuzzy project schedule. This is done using parallel schedule generation method. To construct a solution, artificial ants choose activities sequentially to be added to existing subschedule until all activities are scheduled. In order to select the activities, the ants use ηi as local heuristic information and τij as pheromone trails. Here, for each activity i, local heuristic information is related to activity duration ( d ˜ i ), so that the activity with shortest process time has more chance to be selected by ants. Therefore, ηi has inverse relation with d ˜ i . So, fuzzy durations should be compared in order to rank activities. For this aim, fuzzy numbers ranking method described in section 2 could be helpful. Following equation calculates ηi using Cheng (1998) index:(18)

    η i = 1 R ( d ˜ i )
    (18)

    In order to balance the exploitation of good solutions and the exploration of the feasible space, state transition rule shown below is employed for solution construction process, where activity p is selected to be performed following its immediate predecessor i in the schedule.(19)(20)

    p = { arg max j S i [ ( τ i j ) a × ( η j ) b ] i f q q 0 Pr  o b i p i f q q 0
    (19)

    Pr o b i p = { ( τ i p ) a × ( η p ) b j S i ( τ i p ) a × ( η p ) b i f j S i 0 O t h e r w i s e
    (20)

    Where a and b are control parameters that adjust relative weights of the pheromone and the local heuristic, respectively. 0 < q0 < 1 is a predetermined constant and q is a random number uniformly generated between 0 and 1, which is a parameter that determines the relative importance of exploitation versus exploration. When qq0, exploitation of available knowledge about the problem (local heuristic knowledge for choosing activities) and learned knowledge memorized in form of pheromone trails are used, whereas q > q0 favors more random exploration.

    4.2.Pheromone Updating

    The pheromone value determines the probability of selecting an activity to be added to the schedule and to assign given resources to selected activity. Pheromone values are updated via two stages: online and offline updating phases. The goal of online updating phase is to increase pheromone intensity of the selected move to support exploration. Eq. (21) updates pheromone online, after an ant constructs a solution.

    τ i j n e w = ( 1 ρ ) τ i j o l d + ρ τ 0
    (21)

    Where, ρ ∈[0,1] is the proportion of pheromone evaporation and τ0 represents the initial pheromone intensity. After all ants followed the selection process and thus, constructed a complete fuzzy schedule, the pheromone trails are updated offline. Depending on makespan presented by each ant, the corresponding pheromone trails are changed. The offline trail update can formally be expressed as follows:

    τ i j n e w = ( 1 ρ ) τ i j o l d + ρ Δ τ i j b e s t Δ τ i j b e s t = { 1 R ( t h e b e s t m a k e s p a n ) i f a c t i v i t i e s i a n d j a r e 0 i n c l u d e d i n t h e b e s t s c h e d u l e O t h e r w i s e
    (22)

    where, best Δ τ i j b e s t is the amount of pheromone trail added to old τ i j o l d by the best ant. All ants present fuzzy makespan as total length of the project. Therefore, fuzzy solutions should be compared and ranked to determine the best ant. Chang’s index introduced in section 2 could be employed for this purpose. Also, as it is shown in Eq. (22), Chang’s index should be used to calculate best Δ τ i j b e s t based on the fuzzy makespan presented by the best ant.

    5.NUMERICAL EXAMPLES

    To illustrate efficiency of the fully fuzzy RCPS model and the solution approach developed here, some numerical examples are presented in this section. The ant colony algorithm is coded in MATLAB software and was run using an Intel Core i5 2.40GHz PC with 4.0 GB RAM. Parameters in this algorithm are set as follows:

    a = 1 , b = 0.5 , q 0 = 0.1 , ρ = 0.05

    First example is a project with 9 activities (first and ninth activities are dummy). Details of the activities are given in Table 1.

    First column shows activities numbers and the immediate predecessors of each activity are presented in second column. Based on these columns, the precedence network which is depicted in Figure 2 is constructed. Also, activities fuzzy durations are shown in column 3. In this example, three types of resources are considered and activities resource demands are shown through last three columns. Availability of each resource and aspiration level of makespan are presented in last two rows.

    The developed fuzzy ACO algorithm is applied to the example and results are shown in Table 2.

    As it is shown in Table 2, start and finish times of each activity are calculated in uncertain form as triangular fuzzy numbers. It means that a fuzzy scheduling is presented to the project manager and he/she could have a wide perspective to different situations that might occur to project activities in future. As it is shown in Figure 3, different durations might be obtained as a makespan (M) for different project situations. It should be emphasized that all durations in support set of the makespan (M ∈[47, 52] ) are optimum; while each of them has its own possibility degree for occurrence. For example, the possibility of makespan being smaller than or equal to 48 days can be calculated using Eq. (17) as follows:

    π ( m a k e s p a n 48 ) = max  π { M | M 48 } = o .33

    Such analysis gives helpful and illustrative information to project manager which could be valuable for him / her to make better and more effective decisions.

    As it was mentioned before, RCPSPs belong to NPhard problems. It means that the time required to solve the problem increases very quickly as the size of project grows. So, it seems CPU time could be a proper index to assess efficiency of the developed FACO algorithm. To illustrate the efficiency of presented solution approach, some examples with different sizes are solved and the results are reported in Table 3 and Table 4. Table 3 includes different sample projects with 8 to 240 activities that all of them use just one resource. These examples are generated randomly and CPU time for each problem is recorded.

    As it is shown in Table 3, CPU time for medium and large scale problems seems to be rational and it proves that performance of the developed FACO could be acceptable.

    Table 4 shows another set of problems which need two resources. As same as Table 3, projects are considered with different number of activities and CPU times are reported.

    As it is shown in Table 4, processing times for medium and large scale problems are acceptable. So, it can be concluded that the developed fuzzy ACO could efficiently schedule projects with numerous activities.

    6.CONCLUSION

    In real world situations, project parameters are uncertain due to the variations such as weather conditions, resource availability and etc. Regarding these variations, employing deterministic approaches in project scheduling results in an increase in scheduling risk. Therefore, uncertain project scheduling has more stability against environmental variations. In this paper, a fuzzy mathematical model has been proposed to formulate fuzzy resource constrained project scheduling problem, in which activities durations, resource availability and resource demands are uncertain. Also, to solve presented FRCPS model, a fuzzy ACO algorithm has been developed to deal with large scale projects and its efficiency was illustrated by some numerical examples with different number of activities and resources. As it is discussed before, presented model and solution approach are applications of fuzzy decision making in fuzzy environment concept in field of project scheduling. This concept could also be used to deal with other project scheduling models such as fuzzy time-cost trade off models, fuzzy earned value management and etc.

    Figure

    IEMS-16-307_F1.gif

    Schematic representation of fuzzy project makespan.

    IEMS-16-307_F2.gif

    Precedence network of project with 9 activities.

    IEMS-16-307_F3.gif

    Fuzzy makespan of the example.

    Table

    Information of activities

    ACO results

    Results of single resource problems

    Results of two-resource problems

    REFERENCES

    1. Abdolshah M. (2014) A review of resource-constrained project scheduling problems (RCPSP) approaches and solutions, Int. Trans. Journal of Engineering, Management, & , Applied Sciences & Technologies, Vol.5 ; pp.253-286
    2. Afruzi E.N. , Roghanian E. , Najafi A.A. , Mazinani M. (2013) A multi-mode resource-constrained discrete time-cost tradeoff problem solving using an adjusted fuzzy dominance genetic algorithm , Sci. Iran, Vol.20 (3) ; pp.931-944
    3. Artigues C. , Demassey S. , Neron E. (2013) Resource-Constrained Project Scheduling: Models, Algorithms, Extensions and Applications, John Wiley & Sons,
    4. Bhaskar T. , Pal M.N. , Pal A.K. (2011) A heuristic method for RCPSP with fuzzy activity times , Eur. J. Oper. Res, Vol.208 (1) ; pp.57-66
    5. Brucker P. , Drexl A. , Mohring R. , Neumann K. , Pesch E. (1999) Invited Review; Resource-constrained project scheduling, notation, classification, models and methods , Eur. J. Oper. Res, Vol.112 (1) ; pp.3-41
    6. Cheng C.H. (1998) New approach for ranking fuzzy numbers by distance method , Fuzzy Sets Syst, Vol.95 (1) ; pp.307-317
    7. Fu C.C. , Wang H.F. (1996) Fuzzy resource allocations in project management when insufficient resources are considered , In Fuzzy Systems Symposium, 1996. Soft Computing in Intelligent Systems and Information Processing, Proceedings of the 1996 Asian, ; pp.290-295
    8. Ghazanfari M. , Shahanaghi K. , Yousefli A. , Abiry M.B. (2007) A new approach to obtain possibility distributions of fuzzy decision variables in possibility linear programming problems , Frontiers Science Series, Vol.49 ; pp.59-60
    9. Ghazanfari M. , Shahanaghi K. , Yousefli A. (2008) An application of possibility goal programming to the time-cost trade off problem , Journal of Uncertain Systems, Vol.2 ; pp.22-28
    10. Ghoddousi P. , Eshtehardian E. , Jooybanpour S. , Javanmardi A. (2013) Multi-mode resource-constrained discrete time-cost-resource optimization in project scheduling using non-dominated sorting genetic algorithm , Autom. Construct, Vol.30 ; pp.216-227
    11. Guo P. , Tanaka H. (1996) Fuzzy decision in possibility programming problems , Proceeding of Asian Fuzzy Systems Symposium, ; pp.278-283
    12. Hapke M. , Jaszkiewicz A. , Slowinski R. (1997) Fuzzy project scheduling with multiple criteria , Proceedings of the Sixth IEEE International Conference on Fuzzy Systems, ; pp.1277-1282
    13. Hapke M. , Slowinski R. (1996) Fuzzy priority heuristics for project scheduling , Fuzzy Sets Syst, Vol.83 (3) ; pp.291-299
    14. Hussein M.L. , Abo-Sinna M.A. (1995) A fuzzy dynamic approach to the multi-criterion resource allocation problem , Fuzzy Sets Syst, Vol.69 (2) ; pp.115-124
    15. Guo P. , Tanaka H. (1996) Fuzzy decision in possibility programming problems , Proceeding of Asian Fuzzy Systems Symposium, ; pp.278-283
    16. Ji X. , Yao K. (2017) Uncertain project scheduling problem with resource constraints , J. Intell. Manuf, Vol.28 (3) ; pp.575-580
    17. Jozefowska J. , Mika M. , Rozycki R. , Waligora G. , Weglarz J. (2000) Solving the discrete-continuous project scheduling problem via its discretization , Math. Methods Oper. Res, Vol.52 (3) ; pp.489-499
    18. Kaveh A. , Khanzadi M. , Alipour M. (2016) Fuzzy resource constraint project scheduling problem using CBO and CSS algorithms , Int. J. Civ. Eng, Vol.14 (5) ; pp.325-337
    19. Ke H. , Liu B. (2010) Fuzzy project scheduling problem and its hybrid intelligent algorithm , Appl. Math. Model, Vol.34 (2) ; pp.301-308
    20. Kis T. (2005) Project scheduling: A review of recent books , Oper. Res. Lett, Vol.33 ; pp.105-110
    21. Kim K.W. , Gen M. , Yamazaki G. (2003) Hybrid genetic algorithm with fuzzy logic for resourceconstrained project scheduling , Appl. Soft Comput, Vol.2 (3) ; pp.174-188
    22. Knyazeva M. , Bozhenyuk A. , Rozenberg I. (2015) Resource-constrained project scheduling approach under fuzzy conditions , Procedia Comput. Sci, Vol.77 ; pp.56-64
    23. Kolisch R. (2013) Project Scheduling under Resource Constraints: Efficient Heuristics for Several Problem Classes, Springer Science & Business Media,
    24. Kolisch R. , Padman R. (2001) An integrated survey of deterministic project scheduling , Omega, Vol.29 (3) ; pp.249-272
    25. Lai K.K. , Li L. (1999) A dynamic approach to multi- objective resource allocation problem , Eur. J. Oper. Res, Vol.117 (2) ; pp.293-309
    26. Leon V.J. , Balakrishnan R. (1995) Strength and adaptability of problem-space based neighborhoods for resource-constrained scheduling , OR-Spectrum, Vol.17 (2-3) ; pp.173-182
    27. Leu S.S. , Chen A.T. , Yang C.H. (1999) Fuzzy optimal model for resource-constrained construction scheduling , J. Comput. Civ. Eng, Vol.13 (3) ; pp.207-216
    28. Long L.D. , Ohsato A. (2008) Fuzzy critical chain method for project scheduling under resource constraints and uncertainty , Int. J. Proj. Manag, Vol.26 (6) ; pp.688-698
    29. Ma W. , Che Y. , Huang H. , Ke H. (2016) Resource- constrained project scheduling problem with uncertain durations and renewable resources , Int. J. Mach. Learn. Cybern, Vol.7 (4) ; pp.613-621
    30. Masmoudi M. , Hait A. (2013) Project scheduling under uncertainty using fuzzy modelling and solving techniques , Eng. Appl. Artif. Intell, Vol.26 (1) ; pp.135-149
    31. Meng H. , Wang B. (2013) A modified artificial immune algorithm for fuzzy resource-constrained project scheduling problem , IFAC Proceedings, Vol.46 (13) ; pp.450-455
    32. Pan H. , Yeh C.H. (2003) A metaheuristic approach to fuzzy project scheduling , Proceedings of the International Conference on Knowledge-Based and Intelligent Information and Engineering Systems, ; pp.1081-1087
    33. Pan H. , Yeh C.H. (2004) Fuzzy Project scheduling with multiple objectives , Proceedings of the Pacific Rim International Conference on Artificial Intelligence, ; pp.1011-1012
    34. Tanaka H. , Guo P. , Zimmermann H.J. (2000) Possibility distributions of fuzzy decision variables obtained from possibilistic linear programming problems , Fuzzy Sets Syst, Vol.113 (2) ; pp.323-332
    35. Xu J. , Feng C. (2014) Multimode resource-constrained multiple project scheduling problem under fuzzy random environment and its application to a large scale hydropower construction project , Sci. World J, Vol.2014 ; pp.1-20
    36. Yousefli A. , Ghazanfari M. , Shahanaghi K. , Heydari M. (2008) A new heuristic model for fully fuzzy project scheduling , Journal of Uncertain Systems, Vol.2 (1) ; pp.73-78
    37. Zimmermann H.J. (2011) Fuzzy Set Theory and Its Applications, Springer Science & Business Media,