KSCE Journal of Civil Engineering (2014) 18(5):1261-1269 Copyright ⓒ2014 Korean Society of Civil Engineers DOI 10.1007/s12205-014-0401-x

Construction Management

pISSN 1226-7988, eISSN 1976-3808 www.springer.com/12205

TECHNICAL NOTE

Improved and Competitive Algorithms for Large Scale Multiple Resource-Constrained Project-Scheduling Problems Mohammad Rostami*, Dariush Moradinezhad**, and Azadeh Soufipour*** Received August 2, 2012/Accepted June 10, 2013

··································································································································································································································

Abstract Project scheduling using several resource constraints has been considered frequently by scholars in literatures, but when the dimensions of the problem is getting bigger those solution methods have not high efficiency. The objective of this paper is to propose a branch and bound algorithm and also an enhanced and competitive genetic algorithm to solve the problem of project scheduling with large scale and multiple resource-constrained. The aim of the model is to minimize the project’s completion time which is the objective of all employees. The proposed genetic algorithm in comparison with other meta-heuristic algorithms in the literature has been improved in order to solve larger scale problems easier and with less error. Also the branch and bound algorithm has the ability to solve the large scale problems in a short time using an appropriate upper and lower bound. In this algorithm, an upper bound heuristic that solves the problem with subtle error is proposed. This method is being used to faster prune the answer tree. Also a lower bound based on the solution of a Linear Programming (LP) model has been proposed that has high computational speed as well as tight that makes the solution of large scale problems possible. Computational results are also reported for the most known benchmark problems taken from the operational research literature. These results show that the improved GA in this paper is capable of solving the majority of the problems with less error than other metaheuristic methods. Especially in problems with 120 activities, this algorithm on average has 10% less error than the best existing metaheuristic method. Also the proposed B&B algorithm is capable of solving problems with more than 50 activities in a short time, while the existing algorithms could solve the problems with up to 50 activities so far. Keywords: multiple-resource constrained, branch and bound, project scheduling problem, genetic algorithm, heuristic method ··································································································································································································································

1. Introduction Resource-Constrained Project Scheduling Problem (RCPSP) is a general scheduling problem that includes precedence and resource constraints. The importance of this problem is because of the limited access of managers to the resources in the Operational environment. They have to meet their objectives by properly assigning the resources to the activities; and it increases the complexity of the problem several times because they have to consider the precedence of the activities as well. One of the most important of these objectives is minimization of the project completion time, because lower completion time leads to both higher satisfaction of employers and contractors, and reduction of the contractors’ cost as well. The RCPSP is NP-hard in a strong sense (Philippe et al., 2001). Being one type of NP-hard problem, the RCPSP problem presents a very large search space for exhaustive enumeration to attain the optimum solution. Moreover, they would require more computational expense as the problem size grows or additional constraints are added. Practically it’s impossible to search the

entire search space. It means minimization of makespan becomes tedious and time-consuming. Despite all difficulties to solve RCPSP, it has been the focus of high research efforts because even incremental improvements in project scheduling can lead to huge benefits in terms of resource and production time saving (Wall, 1996). Solution methods applied to solve RCPSP form two distinct classes: exact and heuristic methods. Exact methods are involved with finding the optimal solutions. However they are impractical faced with problems of any significant size or with large sets of constraints. Exact methods can be classified into two groups: (1) mathematical programming and (2) enumerative techniques. Solution methods of those type of problems using mathematical programming are reviewed in Garfinkel and Nemhauser (1972) and Daellenbach and George (1979) researches. Branch and Bound search is a typical implicit enumerative method. Christofides et al. (1987), Reyck and Herroelen (1997) and Brucker et al. (1998) has solved the single resource-constrained project scheduling problem and also Heilmann (2003) has solved Multi-mode Resource-constrained Project Scheduling Problem (MRCPSP)

*Ph.D. Student, Dept. of Industrial Engineering, University of Science and Technology, Tehran, Iran (Corresponding Author, E-mail: [email protected]) **Lecturer, Dept. of Industrial & Manufacturing Engineering, Western Michigan University, Michigan, USA (E-mail:[email protected]) ***Graduate, Dept. of Industrial Engineering, University of Science and Technology, Tehran, Iran (E-mail: [email protected]) − 1261 −

Mohammad Rostami, Dariush Moradinezhad, and Azadeh Soufipour

using branch and bound algorithm. Using branch and bound algorithm, multiple resource-constrained project scheduling problem was solved by Demeulemeester and Herroelen (1992). Using lower bounds, they solved the problem that had 50 activities. In order to solve the real world problems appropriately, many researchers turn their focus to Metaheuristic approaches. Basically, finding near optimal results and using limited computation time are the major characteristics of any heuristic algorithm. There are different heuristic approaches which deals with the RCPSP. Fayer (1990) reported fairly good performance by a simulated annealing approach on scheduling problems. Some researchers reported that they had achieved high-quality project scheduling results by tabu search (Dell’Amico and Trobian, 1993; Nowicki and Smutnicki, 1996). Merkle et al. (2002) reported that they had achieved promising results in project scheduling by an ant colony algorithm. They presented a new ant colony algorithm procedure (AS-RCPSP) in the project scheduling which combines the direct (local) and summation (global) pheromone evaluation methods. In recent years, with developing hybrid metaheuristic algorithms, there have been employed such methods related to RCPSP; specifically one can refer to (Colak et al., 2006; Debels et al., 2006; Kim et al., 2003; Ranjbar et al., 2009; Tseng and Chen 2006; Valls et al., 2005). In addition, there are several genetic algorithms applied to either MRCPSP or RCPSP. Jiang (2004) proposed a genetic algorithm for RCPSP and tested it on some benchmarks. Following him, Debels and Vanhoucke (2007) and Valls et al. (2008) tried to improve the performance of this algorithm using some changes in the GA structure in order to get closer to the optimal solution for the RCPSP. Mendes et al. (2009) combined genetic algorithm with a novel method capable to produce active schedules. They also exploited a new fitness function to enhance the quality of their procedure. Montoya-Torres et al. (2010) applied a new structure of the chromosomes to present schedules related to the decision support systems. Agarwal et al. (2011) has used a hybrid of GA and neural network algorithms. The aim of GA is to search entire solution space while neural network algorithm excels the performance of hybrid algorithm in local search. This problem refers to the Multiple Resource-Constrained Project Scheduling Problem (MRCPSP). An improved branch and bound algorithm will be proposed which has the advantage of reducing running time of the solution procedure and simultaneously solving larger scale problems by introducing and improving more effective upper and lower bounds, over the branch and bound method proposed by Demeulemeester and Herroelen (1992). Also an enhanced genetic algorithm will be proposed that has better results especially in larger scale problems in comparison to the researches previously done in the literature. The structure of this paper is organized in this manner: section 2 defines the problem and its formulation. In section 3, the structure of the proposed GA and its operators are described. Section 4 describes the structure of the branch and bound

algorithm and upper and lower bounds of it, using a numerical example. Finally, Section 5 includes computational results related to conventional benchmarks.

2. Problem Definition Let n be the number of activities with identical durations which are imposed to be done under precedence constraints. Interruption is not allowed while an activity is being processed. Although there is no constraint for the number of activities being processed, there are constant quantities of resources which are renewable. It means any feasible solution is not allowed to exceed available resources but every activity can be finally done by being floated in a time period which has sufficient available resources. Logically rjk indicates the amount of the resource k needed to progress activity j, which is assumed to be constant during the activity processing time. The LP model for RCPSP can be written as follow (Christofides et al., 1987): (1)

MinFn + 1 Fh ≤ Fj – pj j = 1, …, n + 1;

h ∈ Pred ( j )

(2)

∑ j ∈ A(t)rjk ≤ Rk k ∈ K; t > 0

(3)

Fj ≥ 0

(4)

j = 1, …, n + 1

Where: A(t) = Set of activities in process in time interval [t-1, t] = {i|Fh-pj < t < Fh;} Fj = Finish time for activity j pj = Processing time for activity j rjk = Amount of resource type k required by activity j Rk = Available level of th resource k Constraint (2) does not allow activities to start before the finish time of their precedents. Constraint (3) assures that they must be adequate resources needed by activities in each period of time. The last constraint simply imposes completion times to be positive.

3. Design of the GA A new Genetic Algorithm approach related to MRCPSP will be developed in this section. In general practices of GA, the following should be considered: (1) GA's exploration and exploitation ability, (2) the convergence and diversity of the population, and (3) the nature of Multiple Resources Constrained Project Scheduling Problem, especially in the feasibility of each solution (constraints of resource and precedence). In designing of our proposed GA, these issues and some measures associated with them will be considered and discussed. The main advantage of our designed upcoming GA is the design of its operators in a way that it can always generate feasible solutions to the complex MRCPSP, and thus it doesn’t need extra calculation steps to make chromosomes feasible. Also making population diversity using existing methods in such a problem has been always

− 1262 −

KSCE Journal of Civil Engineering

Improved and Competitive Algorithms for Large Scale Multiple Resource-Constrained Project-Scheduling Problems

Fig. 1. Displaying a Chromosome with 5 Activities

difficult and we have solved this shortcoming. 3.1 Encoding and Representation of Chromosome For many optimization problems, GA doesn’t operate directly on the solutions for the problems. Instead, they make use of problem-specific representations of the solutions. The genetic operators modify the representation which is then transformed into a solution by means of a so-called decoding procedure (Hartmann, 2002). During the last few decades, there have been two main chromosome encoding methods for representing the sequence of a set of numbers: (i) Adjacency, (ii) Path representation (Jean, 1996). However Adjacency method is proper for some problems such as Traveling Salesman Problem, but when used in RCPSP, Adjacency representation has some disadvantages (Jean, 1996). Based on these disadvantages, here the Path representation was chosen as the presentation of the Chromosome of our proposed GA. So an activity list that indicates the priority of activities was created. Fig. 1 shows scheme of a chromosome for a project with 5 activities. The numbers inside each gene show the activity’s number and each gene shows the priority in which the first gene has the first priority and the activity that sits inside it (here activity 3) has higher activities in comparison to other activities. After talking about how to represent the priority of a set of numbers in the chromosome, the way to allocate the resources and start time to the each activity needs to be chosen. We chose the serial SGS method in our proposed GA. The serial SGS constructs from activity lists as follow: First, the activity 1 is started at time 0. Then the activities are scheduled in the order that is prescribed by the activity list. Thereby, each activity is assigned the earliest precedence and resource feasible start time. Hartmann (2002) pointed out that the activity list representation together with the serial SGC as decoding procedure leads to better results than other representations for the RCPSP. 3.2 Crossover For the RCPSP, a simple crossover reproduction scheme does not work since it makes the chromosomes inconsistent (some activities may be repeated while others are missed out and hence solutions cannot meet the precedence constraints). The traditional crossover operators like one point crossover is regarded as inappropriate in the study of scheduling problems. The drawback of the simple crossover mechanism is illustrated in Fig. 2.

A simple crossover operator also cannot guarantee the precedence constraints; even no activity is missed out or visited twice. For example, in Fig. 2 it’s assumed as the precedence constraint that activity 5 must begin after activity 4 is finished. In this case, after the simple crossover, activity 5 maybe begins before activity 4. Except the traditional one or two point crossover, recently two crossover operators were developed for the sequence problem: Partially-Mapped (PMX) and Order (OX) crossovers. However, they only can guarantee no activities are missed out or visited twice. Sometimes they still break the precedence constraints. The crossover operator used in this paper is derived from them and inherits their merits. Respect to PMX and OX crossover operator, the crossover operator in this paper is described as follow. There are three main differences between this operator and PMX and OX: (i) Both PMX and OX focus on missed or replicated activities. However they do not consider the precedence constraints. The crossover operator used in this paper can guarantee the precedence constraints. (ii) The crossover operator used in this paper only produces one offspring rather than two. (iii) This crossover focuses on the change between the two cut points rather than outside the two cut points. The pseudo-code of the crossover operator is as follows: Input: parent1, parent2. Output: child. Begin Set R= φ Determine randomly x,y,crossover points. For each ai in parent1 chromosome If i < x or i > y Then copy aI in the same position in child’s chromosome Else R= R U {ai} Sort R according to the positions of the associated individuals in parent2’s chromosome Insert R in vacant space in child’s chromosome End.

Based on the procedure of our proposed crossover operator shown above, let’s set the following two parents to show the crossover operation in Fig. 3. The crossover of our proposed GA is also similar to (Hartmann, 2002). However Hartmann’s crossover can create two children, the crossover of this paper only creates one child. Another important thing is that our proposed crossover operator only considers the changes in the middle part of the schedules rather than the whole solution. 3.3 Mutation The classic mutation operator is also inappropriate in scheduling

Fig. 2. Illegal Solutions Created by Inappropriate Crossover Vol. 18, No. 5 / July 2014

Fig. 3. Proposed Crossover Operator − 1263 −

Mohammad Rostami, Dariush Moradinezhad, and Azadeh Soufipour

problems in terms of precedence constraints as well as crossover operators. Mutation used in this paper will first randomly choose 2 activities, and if possible, it swaps them. The reason for using the word possible is that the offspring after mutation may be invalid and our proposed algorithm checks the precedence constraints. This means that if the swap breaks the precedence constraints, the procedure abandons this switch. This procedure continues till the first feasible exchange is found, or the number of trials to find exceeds k. If k is determined a big number, there would be extra run time to find feasible swaps. On the other hand, a very small k practically eliminates the mutation chance in the population. In this algorithm we show the mutation rate by p which is set to 0.5. k value is equal to 3. If this operator can’t generate a feasible schedule after this much runs, then it uses the population diversity that was proposed in section 3.5. 3.4 Selection The parent selection operator used in this paper randomly chooses two individuals and compares them. Consequently, better individual is added to the mating pool. It is known as tournament-selection in literature, which not only chooses better individuals but also gives a chance to those have worse fitness value. For each individual i, the fitness function is computed as follow: i

Fitness function (i) = 1 ⁄ Fn + 1

(5)

i n+1

is completion time of the last activity in chromosome i. in F order to calculate it, first the priorities are determined by the chromosome’s shape; and then using serial SGS, a feasible scheduling plan will be produced and activities start times are assigned to each one. Having the start times, the finish time of the last i i activity is easy to calculate using the formula Fn + 1 = Sn + 1 + pn + 1 . i As a result, Fn + 1 value will be obtained. Applying crossover and mutation operators leads to a similarsize child population. Then the recent population is combined with the parent population. Logically the best solutions will participate in the next generation. 3.5 Population Diversity Lack of diversity results in premature convergence, in which prevents GA from exploring the whole solution space. In this paper in order to keep the population diverse, not only mutation is applied but also some new individuals are added to each generation. Either new individuals are as well as others or not, they help population to avoid premature convergence. Although the number of new individuals effectively affects the performance of the GA and the computation time, it seems to be the best way when the mutation scheme is not capable of keeping diversity in population because of the complexity caused by precedence constraints. So this method is being used in those chromosomes that mutation’s operator has not been able to make population diversity. GA’s steps will be continued until termination condition is met. Here we consider the number of achieved predetermined iterations as the termination condition. The overall flowchart of the proposed

Fig. 4. Proposed GA Flowchart

genetic algorithm is demonstrated in Fig. 4.

4. Proposed Branch and Bound Algorithm’s Structure As it was mentioned in section 1, Demeulemeester and Herroelen (1992) proposed a B&B algorithm for RCPSP, but their algorithm is not capable enough because it’s only capable of solving the problems with up to 50 activities and 3 resources. This has happened due to two reasons: first they haven’t proposed a heuristic upper bound for pruning the answers tree and because of this more nodes is evaluated in the tree in which increase the running time. Second is its branching way and calculating the lower bound in each tree. They simultaneously evaluate all the activities that can be processed and use the critical path method for unassigned activities in order to calculate the lower bound. Such works leads to first increase the complexity of calculating the lower bound and second, the achieved lower bound is not tight enough. Considering these two principal shortcomings, first of all we propose a heuristic upper bound that can generate answers with subtle error, and then we change the branching and lower bound calculation structure at each node so we can generate better pruning rules which will be explained later on. The notion of a branch and bound algorithm is to consider all possible solutions implicitly. It can be improved by calculating either an upper bound or a lower bound appropriately. These help to decrease considered solutions using this algorithm. While scheduling the project, the fact that which of the ready to be processed activities should be assigned to the resources is highly important. Considering this fact the branch and bound algorithm was designed in the form of depth-first search, so in each level of this tree the nodes are produced for the activities that either have not any predecessor (Level zero), or all their predecessors have been assigned in the previous levels of the tree. If letter m is used

− 1264 −

KSCE Journal of Civil Engineering

Improved and Competitive Algorithms for Large Scale Multiple Resource-Constrained Project-Scheduling Problems

to show the level, the set of these activities is shown by A(m). However, this doesn’t mean all the predecessor tasks of that must be done before, but even if the last predecessor of that is still being processed (meaning that it’s in m-1th level), it could be placed in A(m). In fact in each node, one activity from the set A(m) is assigned to its resource and its lower bound calculations will be executed. Assigning just one activity to each node increase the computational rate and improving B&B as a result. Obviously that tree must generate levels equal to the number of activities. 4.1 Fathoming and Backtracking The node will be closed and have no chance of getting to the optimal solution in two cases: 1. The node which is considered is leaf and it’s not possible to make another node. 2. Lower bound that has obtained in that node is equal or greater than the upper bound at that time. When a node is closed, backtracking happens. If there is no node in the branch and bound algorithm, then the current upper bound would be the optimized solution for the problem. 4.2 Upper Bound (Heuristic Method) Heuristic methods are usually applied to solve problems, because they are simple and fast enough to be used commercially. Additionally they indicate some facts of problem natures. In this paper a two-stage heuristic method is introduced. First stage simply calculates the longest path to achieve the project finish from the current activity and rates them according the following expression. α j = pj + max { α j′ | j « j′ }

⎧ Sj ⎪ B = ⎨ Mij ⎪ i ⎩ βj i j

MR heuristic approach: •Let αj = pj + max { α j′ | j « j′ } •Let t = 0, U = {1, 2, …, n} 1) While U ≠ φ 2) Let At = {available activities at t according precedence constraints} 3) Sort At according to αj, descendingly. 4) For each aj ∈ At : 5) If starting aj at t does not exceed resource limits, 6) Schedule aj and modify U unscheduled activities and resources capacity 7) Increase t to the nearest resource modifications. 8) End.

∀j ∈ A ( s ) j ∈ A( m ) and node ( i )

(7)

∀j ∈ A ( β) in node (i )

In other word, Sj is the start date of the activities that are i assigned to the resources, Mj is the earliest date of assigning jth i activity that are being assigned in the ith node, and Bj is the earliest start date of the activities that has not been assigned yet. 0 Specifically Bj will be calculated this way: 0

0

β j = max{ β j′ + pj′|j′ « j }

(8)

0 j

β = 0 for j ∈ A( m = 0)

(6)

Notice it is assumed that there is a dummy job with zero progress time ought to be done last with α j = 0 . Second stage schedules activities according the obtained results in previous stage. As it is summarized below, it starts with an empty scheduled list U.Then it lists available jobs at the current time which is shown by At. They should respect just precedence constraints. Next step considers resource constraints and schedules activities in order. If there was any extra requirement to do the activity, the algorithm simply checks the next activity. When there is no feasible activity at current time the time is raised to the next event. The event happens whenever an activity ends and causes a change in resource levels. The following procedure is repeated till all activities are planned.

Vol. 18, No. 5 / July 2014

4.3 Lower Bound Carlier and Néron (2003) proposed some non-linear bounds that had being used in single resource constraint scheduling problem. Also Brucker and Knust (2003) and Bianco and Caramia (2011) has obtained lower bounds for this problem. Introducing a linear model here, lower bound for each node is calculated for multiple resource-constrained project scheduling problems based on that. The procedure is to consider the resource constraint for those activities that have not been assigned up to that node and also those that are being assigned. For the remaining activities, earliest start date will be calculated regardless of resource constraints, because it’s obvious that always the problem in which no resourceconstrained is considered is always a lower bound for the same problem that has the resource-constrained. A(s) is the set of assigned activities to the resources and A ( β ) = { j| j ∉ A ( s ), j ∉ A ( m )} is defined. Earliest start dates of each activity j in each node i is demonstrated by B ij that is calculated this way:

(9)

And for other nodes is equal to: i

i

β j = max{ Bj′ + pj ′| j′ « j } i ≠ 0

(10)

i j

M in each node will be obtained solving the following conceptual mathematical model: i

Mj = Min γ

(11)

Subject to: γ ≥ Sj′ + pj′; j′ « j Rk ( t ) = Rk – ∑ rj′k

(12) for

any t ≥ 0 and j′ ∈ A ( t )

(13)

j′

Rk ( t ) ≥ Rk – rjk ; γ ≤ t ≤ γ + pj

(14)

Equation (11) gives the earliest date of assigning activity j to the resource i. Constraint (12) brings up the necessity of assigning activity j after its predecessors. Constraint (13) calculates the required resourced Kin hand at time t. Constraint (14) states that from the time activity j is assigned until the end of processing on this activity, the considered resource for that must have the required capacity. Considering the above definitions and the values of the achieved parameters, lower bound for each node could be obtained using Eq. (15) as follow:

− 1265 −

Mohammad Rostami, Dariush Moradinezhad, and Azadeh Soufipour i

i

i

LBi = Max { B1 + p1, B2 + p2, …, Bn + pn }

(15)

As it is seen in Eq. (15), the lower bound in each node is equal to the maximum value of the earliest finish dates of all the activities in that node. A formal definition of the proposed branch and bound algorithm and the generation of new nodes is given below: Step0. Get AON of problem, calculate initial UB and set m=0 (generate node 0). Step1. m=m+1 and update A(m), A(s) and A(β), Step2. Generate nodes at level m and assign each j ∈ A ( m ) to each node at this level, i Step3. Calculate Bj for all activities in each node i with using Eq. (7) and then calculate the lower bound with using Eq. (15) Step4. If LBi
4.4 Numerical Example In order to see the way how branch and bound algorithm works and the way the tree is being made, the following numerical example that has 4 activities and 2 resources is being solved. Corresponding AON, process times, and required amount of each resource for each one of the activities is shown in Fig. 5. Upper Bound: MR Heuristic step 0: t=0, U={1, 2, 3, 4}, α4=3, α3=5, α2=4+3=7, α1=2+ max{3, 5}=7; step 1: A0={1, 2} ∴ a1 and a2 are scheduled in t=0, R1=1, R2=3, U={3, 4}; step 2: t=2, A2={3}, (r32=3) ≤ (R2=3) ∴ a3 is scheduled in t=2, R1=1, R2=0, U={4}; step 3: t=4, A4={4}, (r41=3) ≤ (R1=6) ∴ a4 is scheduled in t=4, R1=3, R2=0, U=φ; step 4: End. So the upper bound is calculated equal to 7. The assigned activities are shown in Fig. 6. Branch and Bound Figure 7 shows the complete tree for this problem. However, the tree is fathomed in node 0, because the lower bound will become equal to the upper bound. Calculations in each node are

Fig. 6. Scheduled Activities with MR Heuristic

as following: node 0: 0

0

0

0

β 1 = β 2 = 0, β 3 = 0 + 2 = 2, β 4 = max{ 0 + 4, 0 + 2 } = 4, A( x ) = A ( m ) = φ, A ( β) = { 1, 2, 3, 4 } 0

0

0

2

0

0

0

0

∴ B1 = β 1 = 0, B2 = β 2 = 0, B3 = β 4 = 2, B4 = β 4 = 4, 0

0

0

0

∴ LB0 = Max { B1 + p1, B2 + p2, B3 + p3, B4 + p4 } = 7 ∴ LB0 = UB = 7 ∴ backtracking While there are no more nodes to be generated, so the optimal solution to the problem is that heuristic MR solution in Fig. 6. In Fig. 7, ai demonstrates the ith activity that its location and priority is being determined considering its predecessors and successors. For example in node 9, a3 means first a2 and then a1 have been assigned to their correspondent resources and we are in the stage that a3 needs to be assigned considering them. This problem has been designed to first of all show the efficiency of the proposed lower bound, and second, to clarify the calculations method in each node. The first one was clearly

Fig. 5. AON of Example Upper Bound: MR Heuristic

Fig. 7. Branch and Bound Scheme − 1266 −

KSCE Journal of Civil Engineering

Improved and Competitive Algorithms for Large Scale Multiple Resource-Constrained Project-Scheduling Problems

demonstrated, but to show the second one the way the lower bound is calculated in node 4 is shown here: node 4: A ( s ) = { 1 }, A ( m ) = { 3 }, A ( β) = { 2, 4 } ; ∴ B41 = S1 = 0, B43 = M 43 = 2, B42 = β 42 = 0, B44 = β 44 = max { 0 + 2, 0 + 4 } = 4, 4

Where the M3 value is calculated by solving the below conceptual mathematical model: 4

M3 = Min γ Subject to:

Parameters: Dj = The best solutin found till jth N = The number of iterations D = Optimal solution or the best found solution Table 2 shows the running time for problems j30, j60, j90, and j120 using branch and bound algorithm that has been solved once using MR heuristic and the other time without using it. This table shows the number of visited nodes as well. It is apparent that the number of generated nodes and also the process time required to reach the optimal solution using heuristic MR algorithm in comparison to the case that it is not being used is lower; and this

γ ≥ S1 + p1 ⇒ γ ≥ 2;

Table 2. Results for B&B Algorithm

R2 ( t ) = 5 – ∑ rj′k for any t ≥ 0 and j′ ∈ A( t ) = φ

B&B Without MR With MR Problem Activities Number of Running Number of Running nodes time(s) nodes time(s) j30 30 401,172 7.52 286,453 5.14 j60 60 874,441 16.41 801,794 14.06 j90 90 1,569,002 29.23 1,507,016 26.89 j120 120 3,804,251 72.40 3,750,185 67.11

j′

R2 ( t ) ≥ 5 – 3 ⇒ R2 ( t ) ≥ 2; γ ≤ t ≤ γ + 5 4

4

4

4

∴ LB4 = Max { B1 + p1, B2 + p2, B3 + p3, B4 + p4 } = 7 ∴ LB0 = UB = 7 ∴ backtracking

5. Computational Results

Table 3. Average Deviation from the Optimal Solution for j30

Kolisch and Sprecher (1996) presented a set of benchmark instances for the evaluation of scheduling techniques for the RCPSP. It is called PSPLIB. It is accepted in the literature as the set of benchmark problems. The feature of PSPLIB is that the instances are classified according to various indicators. Here, Both the Genetic Algorithm and Branch and Bound algorithm were coded in C# and have been run on a PC with core i5 2.53 GHz CPU and 4 GB of RAM. Table 1 compares proposed GA with MR heuristic. Notice that after 1000 seconds the GA reports best solution found. Consequently, reported results which have greater running time than 1000 seconds have not completed their search. Although the GA has better results, the running time raises dramatically, as the number of activities increases. In this sense MR heuristic has acceptable performance. In order to distinguish between algorithms, those are faster than average deviation is usually computed as follow. N

∑ j = 1 Dj – N × D-⎞ × 100 Ave.Deviation% = ⎛ ----------------------------------⎝ ⎠ N×D

(16)

Algorithm

Reference

Optimized GA Scatter search, path relinking Filter and fan Hybr scatter search

This paper

Number of generations N = 1000 N = 5000 Average Average deviation deviation 0.04 0.02

(Mobini et al., 2009)

(Ranjbar, 2008) (Ranjbar et al., 2009) (Kochetov and Stolyar, GA, TS, path relinking 2003) Decomposition Based (Debels and Vanhoucke, GA 2007) Neurogenetic (FBI) (Agarwal et al., 2011) Sampling-LFT-FBI (Tormos and Lova, 2003) GA-forw.-backw. (Alcaraz et al., 2004) HNA-FBI (Colak et al., 2006) Sampling-LFT-FBI (Tormos and Lova, 2001) GA-hybrid, FBI (Valls et al., 2008) Scatter search-FBI (Debels et al., 2006) GA-forw.-backw. (Alcaraz and Maroto, 2001) GA-FBI (Valls et al., 2005)

0.05

0.02

0.09 0.1

0 0.03

0.1

0.04

0.12

0.04

0.13 0.23 0.25 0.25 0.25 0.27 0.27 0.33 0.34

0.1 0.14 0.06 0.11 0.15 0.06 0.11 0.12 0.2

Table 1. Comparison between Proposed Algorithms GA Problem

Activities

j30 j60 j90 j120

30 60 90 120

Vol. 18, No. 5 / July 2014

N = 1000 Average deviation Run time(s) 0.04 23.90 10.10 102.38 11.02 224.40 27.65 511.95

N = 5000 Average deviation Run time(s) 0.02 119.96 9.94 512.66 10.75 >1000 21.73 >1000 − 1267 −

MR heuristic Average deviation 0.90 3.84 10.76 31.31

Run time(s) 0.01 0.06 1.25 8.16

Mohammad Rostami, Dariush Moradinezhad, and Azadeh Soufipour

Table 4. Lower Bound for Average Deviation from the Optimal Solution For J60

Algorithm

Number of generations N = 1000 N = 5000 Reference Average Average deviation deviation This paper 10.10 9.94 (Tchomte et al., 2007) 9.52 9.01

Optimized GA PSO Scatter search, (Mobini et al., 2009) path relinking Filter and fan (Ranjbar, 2008) Hybr scatter search (Ranjbar et al., 2009) Decomposition (Debels and Based GA Vanhoucke, 2007) Neurogenetic (FBI) (Agarwal et al., 2011) (Tormos and Lova, Sampling-LFT-FBI 2003) HNA-FBI (Colak et al., 2006) GA-hybrid, FBI (Valls et al., 2008) Scatter search-FBI (Debels et al., 2006) (Alcaraz and Maroto, GA-forw.-backw. 2001) GA-FBI (Valls et al., 2005)

11.12

10.74

10.66 11.59

10.56 11.07

11.31

10.95

11.51

11.29

12.04

11.72

11.72 11.56 11.73

11.39 11.10 11.10

11.89

11.19

12.21

11.27

Reference

Optimized GA This paper Filter and fan (Ranjbar 2008) Decomposition (Debels and Vanhoucke, Based GA 2007) Neurogenetic (FBI) (Agarwal et al., 2011) GA-hybrid, FBI (Valls et al., 2008)

Number of generations N = 1000 N = 5000 Average Average deviation deviation 11.02 10.75 10.52 10.11 10.80

10.35

11.51 NA

11.29 10.46

Algorithm

Reference

Optimized GA This paper Scatter search, (Mobini et al., 2009) path relinking Filter and fan (Ranjbar, 2008) Decomposition (Debels and Vanhoucke, Based GA 2007) Neurogenetic (FBI) (Agarwal et al., 2011) Sampling-LFT-FBI (Tormos and Lova, 2003) GA-forw.-backw. (Alcaraz et al., 2004) HNA-FBI (Colak et al., 2006) Sampling-LFT-FBI (Tormos and Lova, 2001) GA-hybrid, FBI (Valls et al., 2008) Scatter search-FBI (Debels et al., 2006) GA-FBI (Valls et al., 2005)

Number of generations N = 1000 N = 5000 Average Average deviation deviation 27.65 21.73 34.49

32.61

32.96

31.42

33.55

32.18

34.65 36.32 36.53 34.94 35.98 34.07 35.22 35.39

34.15 35.62 33.91 34.57 35.30 32.54 33.10 33.24

6. Conclusions

Table 5. Lower Bound for Average Deviation from the Optimal Solution for j90

Algorithm

Table 6. Lower Bound for Average Deviation from the Optimal Solution for j120

shows the efficiency of the proposed methods. Tables 3-5 compare our proposed GA with other Metaheuristics in the literature. Table 3 reports our results for j30 problems. Only Ranjbar (2008) algorithm has better performance than our GA when the number of generations is five thousands. Although our GA algorithm used to have better performance but it consumes exhaustive running time to find feasible solutions and add new members to the population. Similarly Table 4 shows the results related to j60. Because there is not optimal solution for problems which their size is greater than 30, the results are a lower bound for average deviation from the optimal solution. The PSO algorithm presented by Tchomte et al. (2007) outperformed other algorithms, but it is followed by our proposed GA. For j90 problems, Table 5 indicates that Ranjbar (2008) algorithm has the best performance. Finally, Table 6 indicates that our proposed GA has the best performance for large scale problems and it is observed that producing massive amount of individuals as well as keeping population diverse has improved algorithm performance for larger problems.

In this paper the problem of multiple resource-constrained project scheduling problems with large scale was studied. This problem is NP-hard and an effort was made to solve it using an enhanced genetic algorithm and choosing special designs for specific requirements of the problem such as the representation of the chromosome in order to achieve better solutions in comparison to the meta-heuristic methods which have been proposed so far. Compared with other methods, the GA presented in this paper can search the results efficiently. This research has shown that the representation of the chromosome, the crossover and mutation operator in this study can obey the precedence and resource constraints. This means that after crossover, the child solutions can still satisfy precedence constraints. This is a crucial issue for the RCPSP, but many other methods couldn’t handle it. Also by proposing branch and bound algorithm and effective upper and lower bounds, larger scale problems were solved and their global optimal solutions were achieved. The results show this algorithm has better performance in comparison to the branch and bound algorithm that has been proposed in the literature, and also can solve the problems of bigger sizes.

References Agarwal, A., Colak, S., and Erenguc, S. (2011). “A Neurogenetic approach for the resource-constrained project scheduling problem.” Computers & Operations Research, Vol. 38, No. 1, pp. 44-50. Alcaraz, J. and Maroto, C. (2001). “A robust genetic algorithm for resource allocation in project scheduling.” Annals of Operations Research, Vol. 102, Nos. 1-4, pp. 83-109. Alcaraz, J., Maroto, C., and Ruiz, R. (2004). “Improving the performance of genetic algorithms for the RCPS problem.” Proceedings of the Ninth International Workshop on Project Management and Scheduling,

− 1268 −

KSCE Journal of Civil Engineering

Improved and Competitive Algorithms for Large Scale Multiple Resource-Constrained Project-Scheduling Problems

pp. 40-43. Bianco, L. and Caramia, Massimiliano (2011). “A new lower bound for the resource-constrained project scheduling problem with generalized precedence relations.” Computers & Operations Research, Vol. 38, No. 1, pp. 14-20. Brucker, P. and Knust, Sigrid (2003). “Lower bounds for resourceconstrained project scheduling problems.” European Journal of Operational Research, Vol. 149, No. 2, pp. 302-313. Brucker, P., Knust, S., Schoo, A., and Thiele, O. (1998). “A branch-andbound algorithm for the resource-constrained project scheduling problem.” European Journal of Operational Research, Vol. 107, Issue 2, pp. 272-288. Carlier, J. and Néron, E. (2003). “On linear lower bounds for the resource constrained project scheduling problem.” European Journal of Operational Research, Vol. 149, No. 2, pp. 314-324. Christofides, N, Alvarez-ValdOes, R., and Tamarit, J. M. (1987). “Project scheduling with resource constraints: a branch and bound approach.” European Journal of Operational Research, Vol. 29, No. 3, pp. 262-273. Colak, S., Agarwal, A., and Erenguc, S. S. (2006). “Resource-constrained project scheduling problem: A hybrid neural approach.” Perspectives in Modern Project Scheduling, pp. 297-318. Daellenbach, H. and George, J. (1979). Operation research techniques (Allyn and Bason). Debels, D., De Reyck, B., Leus, R., and Vanhoucke, M. (2006). “A hybrid scatter search/electromagnetism meta-heuristic for project scheduling.” European Journal of Operational Research, Vol. 169, No. 2, pp. 638653. Debels, D. and Vanhoucke, M. (2007). “A decomposition-based genetic algorithm for the resource-constrained project-scheduling problem.” Operations Research, Vol. 55, No. 3, pp. 457-469. Dell’Amico, M. and Trobian, M. (1993). “Applying tabu search to the job shop scheduling problem.” Annals of Operations Research, Vol. 41, No. 3, pp. 231-252. Demeulemeester, E. and Herroelen, W. (1992). “A branch-and-bound procedure for the multiple resource-constrained project scheduling problem.” Management Science, Vol. 38, No. 12, pp. 1803-1818. Fayer, F.B (1990). “Some efficient multi-heuristic procedures for resourceconstrained project scheduling.” European Journal of Operational Research, Vol. 49, No. 1, pp. 3-13. Garfinkel, R. S. and Nemhauser, G. L. (1972). Integer programming (New York: John Wiley). Hartmann, S. (2002). “A self-adapting genetic algorithm for project scheduling under resource constraints.” Naval Research Logistics, Vol. 49, No. 5, pp. 433-448. Heilmann, Roland (2003). “A branch-and-bound procedure for the multimode resource-constrained project scheduling problem with minimum and maximum time lags.” European Journal of Operational Research, Vol. 144, No. 2, pp. 348-365. Jean, Y. P. (1996). “Genetic algorithms for the traveling salesman problem.” Annual of Operations Research, Vol. 63, No. 3, pp. 339-370. Jiang, Q. (2004). A genetic algorithm for multiple resource-constrained project scheduling, Master Thesis, University of Wollongong. Kim, K. W., Gen, M., and Yamazaki, G. (2003). “Hybrid genetic algorithm with fuzzy logic for resource-constrained project scheduling.” Applied Soft Computing, Vol. 2, No. 3, pp. 174-188. Kochetov, Y. and Stolyar, A. (2003). “Evolutionary local search with variable neighborhood for the resource constrained project scheduling problem.” Proceedings of the Third International Workshop of

Vol. 18, No. 5 / July 2014

Computer Science and Information Technologies (Russia). Kolisch, R. and Sprecher, A. (1996). “PSPLIB – A project scheduling library.” European Journal of Operational Research, Vol. 96, No. 1, pp. 205-216. Mendes, J. J. M., Gonçalves, J. F., and Resende, M. G. C. (2009). “A random key based genetic algorithm for the resource constrained project scheduling problem.” Computers & Operations Research, Vol. 36, No. 1, pp. 92-109. Merkle, D., Middendorf, M., and Schmeck, H. (2002). “Ant colony optimization for resource-constrained project scheduling.” Evolutionary Computation, IEEE Transactions, Vol. 6, No. 4, pp. 333-346. Mobini, M. M., Rabbani, M., Amalnik, M. S., Razmi, J., and RahimiVahed, A. R. (2009). “Using an enhanced scatter search algorithm for a resource-constrained project scheduling problem.” Soft Computing, Vol. 13, No. 6, pp. 597-610. Montoya-Torres, Jairo R., Gutierrez-Franco, Edgar, and PirachicánMayorga, Carolina (2010). “Project scheduling with limited resources using a genetic algorithm.” International Journal of Project Management, Vol. 28, No. 6, pp. 619-628. Nowicki, B. A. and Smutnicki, C. (1996). “A fast tabu search algorithm for the job shop problem.” Management Science, Vol. 42, No. 6, pp. 797-813. Philippe, B., Claude, L. P., and Wim, N. (2001). Constraint-based scheduling; Applying constraint programming to problems Kluwer Academic Publishers, Massachusetts, USA. Ranjbar, M. (2008). “Solving the resource constrained project scheduling problem using filter-and-fan approach.” Applied Mathematics and Computation, Vol. 201, No. 1, pp. 313-318. Ranjbar, M., Reyck, B. D., and Kianfar, F. (2009). “A hybrid scatter search for the discreet time/resource trade-off problem in project scheduling.” European Journal of Operational Research, Vol. 193, No. 1, pp. 35-48. Reyck, B. De and Herroelen, W. (1997). “A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence constraints.” European Journal of Operational Research, Vol. 45, No. 2. Tchomte, S. K., Gourgand, M., and Quilliot, A. (2007). “Solving resourceconstrained project scheduling problem with particle swarm optimization.” Proceedings of Fourth Multidisciplinary International Scheduling Conference, pp. 251-258. Tormos, P. and Lova, A. (2001). “A competitive heuristic solution technique for resource constrained project scheduling.” Annals of Operations Research, Vol. 102, No. 1-4, pp. 65-81. Tormos, P. and Lova, A. (2003). “An efficient multi-pass heuristic for project scheduling with constrained resources.” International Journal of Production Research, Vol. 41, No. 5, pp. 1071-1086. Tseng, L.-Y. and Chen, S.-C. (2006). “A hybrid metaheuristic for the resource-constrained projectscheduling problem.” European Journal of Operational Research, Vol. 175, No. 2, pp. 707-721. Valls, V., Ballestin, F., and Quintanilla, M. S. (2005). “Justification and RCPSP: A technique that pays.” European Journal of Operational Research, Vol. 165, No. 2, pp. 375-386. Valls, V., Ballestín, Francisco, and Quintanilla, Sacramento (2008). “A hybrid genetic algorithm for the resource-constrained project scheduling problem.” European Journal of Operational Research, Vol. 185, No. 2, pp. 495-508. Wall, M. B. (1996). A genetic algorithm for resource-constrained scheduling, Massachusetts Institute of Technology.

− 1269 −