Application 2 – Annotated Bibliography

Improvedgeneticalgorithmforresource-constrainedschedulingoflargeprojects.pdf

Home >Information Systems homework help >Application 2 – Annotated Bibliography

Improved genetic algorithm for resource- constrained scheduling of large projects

Jin-Lee Kim

Abstract: The generalized model of the resource-constrained project scheduling problem (RCPSP) is valuable because it can be incorporated into the advanced computational methods of commercial project management software for practical applications. A construction schedule generated by most commercial project management programs does not guarantee its optimality when the resources are limited. This paper presents an improved elitist genetic algorithm (GA) for resource-con- strained scheduling of large projects. The proposed algorithm allocates multiple renewable resources to activities of a sin- gle large-sized project to achieve the objective of minimizing the project duration. A permutation-based decoding procedure is developed using the improved parallel schedule generation scheme. A new parameter, named transformation power, is created in the transformation method of the improved algorithm to ensure that the individual selection process performs correctly. Extensive computational results using a standard set of large-sized multiple resource-constrained proj- ect scheduling problems are presented to demonstrate the performance and accuracy of the algorithm.

Key words: algorithm, heuristics, optimization, project management, resource, scheduling.

Résumé : Le modèle généralisé du problème d’ordonnancement de projet avec contrainte de ressources (« RCPSP ») est utile puisqu’il peut être incorporé dans les méthodes computationnelles avancées d’un logiciel commercial de gestion de projets permettant des applications pratiques. Le calendrier des travaux généré par la majorité des programmes commer- ciaux de gestion de projets ne peut garantir son optimalité lorsque les ressources sont limitées. Cet article présente un algo- rithme génétique élitiste amélioré pour le calendrier d’exécution de grands projets avec ressources limitées. L’algorithme proposé assigne plusieurs ressources renouvelables aux activités d’un seul grand projet afin d’atteindre l’objectif de mini- miser la durée du projet. Une procédure de décodage basée sur la permutation est élaborée en utilisant un mécanisme d’élaboration d’un calendrier amélioré en parallèle. Un nouveau paramètre appelé puissance de transformation est créé dans le cadre de la méthode de transformation de l’algorithme amélioré afin d’assurer que le processus de sélection indivi- duel fonctionne adéquatement. Les principaux résultats computationnels utilisant un ensemble-type de problèmes d’établis- sement du calendrier d’exécution de grands projets à plusieurs ressources limitées sont présentés afin de démontrer le rendement et la précision de l’algorithme.

Mots-clés : algorithme, heuristique, optimisation, gestion de projet, ressource, calendrier d’exécution.

[Traduit par la Rédaction]

Introduction Project planning plays a significant role in defining proj-

ect goals and objectives, setting out the deadlines for project completion, and developing contingency plans on potential risks. Project management tools are essential to reduce po- tential problems in the area of specification, estimation, monitoring, and control. Many project managers are willing to invest in a variety of project management tools for the reasons previously mentioned. In contrast to strong reasons for the use of project management tools, the majority of project management literature argues that looking for the best procedure for resolving resource conflicts is useless in practice as it does not impact the planned project duration

(Herroelen 2004; Herroelen and Leus 2005). However, proj- ect scheduling problems have been interesting and challeng- ing subjects of extensive research for several decades in the optimization study area to make them applicable in practice.

A variety of commercialized project management soft- ware packages have been used for construction planning and scheduling. For example, Microsoft Project and Prima- vera Project Planner are the two most popular project man- agement software packages. However, a construction schedule generated by most commercial project management software packages does not guarantee its optimality when the resources are limited. Project scheduling programs re- vealed the limitation because they employ simple priority rules for generating a precedence and resource feasible schedule, even though they provide the schedules in a rea- sonable amount of time regardless of the project size. The generalized model of the resource-constrained project sched- uling problem (RCPSP) is valuable to project planners be- cause it can be incorporated into the advanced computational methods of commercial project management software for practical applications.

Various meta-heuristic methods, such as genetic algorithm (GA), simulated annealing, tabu search, and ant colonies

Received 3 January 2007. Revision accepted 12 March 2009. Published on the NRC Research Press Web site at cjce.nrc.ca on 23 June 2009.

J. Kim. Department of Engineering Technology, Missouri Western State University, 4525 Downs Drive, St. Joseph, MO 64507, USA (e-mail: [email protected]).

Written discussion of this article is welcomed and will be received by the Editor until 31 October 2009.

1016

Can. J. Civ. Eng. 36: 1016–1027 (2009) doi:10.1139/L09-049 Published by NRC Research Press

have been applied to solve the RCPSP. These methods at- tempt to overcome the drawbacks of the exact optimal meth- ods and priority-rule based heuristics as well as to improve the performance of the existing meta-heuristic methods. Most meta-heuristics that employed the activity list repre- sentation in the RCPSP literature make use of the serial schedule generation scheme as a decoding procedure (Pinson et al. 1994; Boctor 1996; Hartmann 1998; Baar et al. 1999; Bouleimen and Lecocq 2003; Kim and Ellis 2008). A few meta-heuristics used the parallel schedule gen- eration scheme as a decoding procedure (Lee and Kim 1996; Kohlmorgen et al. 1999). The selection of the serial scheme in most research has been recognized due to the fact that all optimal solutions from the search space may not be included when applying the parallel scheme, whereas the search space of the serial scheme always contains an optimal schedule. This paper intends to develop a more efficient al- gorithm that utilizes the parallel schedule generation scheme as a decoding procedure in an attempt to fulfill the lack of an optimal solution algorithm as well as to find near-optimal schedules for large projects associated with multiple resour- ces.

This paper presents an improved elitist GA for resource- constrained scheduling of large projects associated with multiple resources. The proposed algorithm aims to allocate multiple renewable resources to activities of a single large- sized project to achieve the objective of minimizing the project duration. A permutation-based decoding procedure is developed using the improved parallel schedule genera- tion scheme. A new parameter, named transformation power, is created in the transformation method of the im- proved algorithm to ensure that the individual selection process performs correctly. Extensive computational results using large-sized multiple resource-constrained project scheduling problems are presented to demonstrate the per- formance and accuracy of the algorithm.

Previous studies on the genetic algorithm approach

The RCPSP has been solved using the various exact methods, priority-rule based heuristics, and various meta- heuristic methods. Table 1 tabulates the various solution ap- proaches with their notable features in solving the RCPSP. Several studies have been done to solve the RCPSP using a GA (Chan et al. 1996; Hartmann 1998; Hegazy 1999; Leu and Yang 1999; Kohlmorgen et al. 1999; Alcaraz and Mar- oto 2001; Hartmann 2002; Hindi et al. 2002; Toklu 2002; Valls et al. 2003, 2005; Kim and Ellis 2008). Chan et al. (1996) combined resource allocation with resource leveling by setting a single equation with the objective of minimizing the difference between resource availability and utilization. In the string representation of GA, they adopted the concept of current float to set the scheduling priority. The current float concept proposed by Shanmuganayagam (1989) was used for elimination of network recalculation, which is the main disadvantage of the total float concept in the critical path method (CPM) analysis.

Hartmann (1998) proposed a permutation-based GA, which did not consider the elitism in the GA, and made use of activity list representation. Hegazy (1999) also solved re-

source allocation problems using GA, where the concept of minimum total slack was incorporated as the decision varia- ble for the problem. Leu and Yang (1999) proposed a GA- based multicriteria optimal model for construction schedul- ing. A parallel GA developed by Kohlmorgen et al. (1999) has been applied to solve the RCPSP. The algorithm in- cludes a fine-grained parallel version of the island model of genetic algorithms and of variants of the neighborhood model called the diffusion model. In the island model, the population is divided into several subpopulations by appro- priately dividing the grid into sub-arrays. It was imple- mented on a coarse-grained parallel machine using one processor per island. In the neighborhood model, every pro- cessor selects a partner for recombination from some local neighborhood by considering neighbors at different distances in the possible directions. Although a comparative evalua- tion of two models was not demonstrated, Kohlmorgen et al. (1999) argued that their algorithm showed good perform- ance due to the larger genetic diversity obtained by several sub-populations.

A GA of Alcaraz and Maroto (2001) was the generaliza- tion of the activity list GA of Hartmann (1998). They used the serial schedule generation scheme and included an addi- tional gene that decides whether the activity list is scheduled in a forward or backward direction. From extensive compu- tational experiments based on a standard set of project in- stances (Kolisch and Sprecher 1997), it was shown that the algorithm provides good performance based on the devel- oped forward-backward crossover techniques. An extended self-adapting genetic algorithm (SAGA) proposed by Hart- mann (2002) was developed based on a previous GA (Hart- mann 1998). SAGA has been provided with several features: (i) an extended representation of an individual, which in- cludes an additional gene that decides the decoding proce- dure; (ii) adapted crossover and mutation operators; and (iii) a new method for computing an initial population. Although the result increased the quality of the solutions, an additional computational cost was required.

A GA developed by Hindi et al. (2002) employed the ac- tivity list representation, the serial schedule generation scheme, and the related order-preserving crossover strategy, which are similar to the work of Hartmann (1998). The dif- ference between the two algorithms is that the initial popula- tion in Hindi et al. (2002) is generated by a pure random mechanism, whereas Hartmann (1998) generated an initial population using the late finish time-based sampling. On the other hand, Toklu (2002) developed a GA that applies di- rectly to schedules using a vector of start times. A penalty function was used to repair infeasible offspring schedules that the genetic operators may produce.

Valls et al. (2005) developed the extended activity list- based GA by combining a forward-backward improvement proposed by Valls et al. (2003). A peak crossover operator was developed to aim at inheriting those parts of the pa- rents’ activity lists that correspond to peaks in the resource usage. Kim and Ellis (2008) proposed a permutation-based elitist GA for optimization of large-sized resource schedul- ing problems using the serial schedule generation scheme. The following sections briefly introduce the description for a GA because the writer utilized GA for the improvement of search solutions to the RCPSP, followed by the problem

Kim 1017

Published by NRC Research Press

definition and its mathematical formulation. The proposed GA is then developed to incorporate the improved parallel schedule generation scheme and a new parameter named transformation power for the individual selection process. The experimental results and analysis section presents two- fold: (i) sensitivity analysis that examines the effects of the genetic operators such as the elitist, crossover, and mutation; and (ii) implementation aspects that present the results ob- tained from extensive computational experiments. Addi- tional studies for the further improvement based on the proposed algorithm are included in the conclusions.

Genetic algorithms A GA is a meta-heuristic and optimization technique that

has emerged as a tool that is beneficial for a variety of study fields including construction applications since its introduc- tion in the 1960s by Holland (Holland 1975). The basic GA performs a random search for the optimal solution to a prob- lem by simulating natural evolution and survival-of-the-fit- test mechanisms. GA differs from conventional optimization and search procedures in the following four ways, as sum- marized by Goldberg (1989): (i) GA works with a coding of the parameter (solution) set, not the parameters (solu- tions) themselves; (ii) GA searches from a population of sol- utions, not a single solution; (iii) GA uses objective function (fitness function) information, not derivatives or other auxil- iary knowledge; and (iv) GA uses probabilistic transforma- tion rules, not deterministic ones.

The main components of GA are the population, the indi- vidual or string, and the gene. A population is a set of pos- sible solutions to the problem. An individual or a string (chromosome) is a possible solution to the problem. A gene (feature) is a part of a solution to a given problem. Usually, a gene is an independent variable in the problem. Genotype is an individual’s group of chromosomes whereas phenotype is a set of values corresponding to a given genotype. GA starts with an initial population of individuals generated at random. Each individual in the population represents a po- tential solution to the problem under consideration. The in- dividuals evolve through successive iterations, called generations. During each generation, each individual in the population is evaluated using some measure of fitness. Then, the population of the next generation is created

through genetic operators. The procedure continues until the termination condition is satisfied.

Three main genetic operators are selection, crossover, and mutation. Selection (reproduction) is a process in which in- dividuals are generated according to their objective function value. Individuals with a higher value have a higher proba- bility of contributing one or more offspring in the next gen- eration. After selection, crossover (recombination) can proceed in two steps: (i) genes of the newly reproduced individuals in the mating pool are mated at random; and (ii) each pair of individuals undergoes crossover. Mutation is the occasional random alteration of the value of an indi- vidual position. The mutation operator plays a secondary role in GA. The frequency of mutation to obtain good re- sults in empirical GA studies is on the order of one muta- tion per thousand position transfers. Mutation probabilities are similarly small in natural populations, leading to the conclusion that mutation is appropriately considered as a secondary mechanism of GA adaptation.

The three basic parameters of GA are crossover probabil- ity, mutation probability, and population size. Population size indicates how many individuals in a population are in one generation. The most important component in the GA approach is deciding the fitness function and evaluation function. The evaluation function (objective function) pro- vides a measure of performance with respect to a particular set of parameters. The fitness function transforms that meas- ure of performance into an allocation of reproductive oppor- tunities. A schema theorem is a similarity template that describes a subset of individuals with similarities at certain individual positions.

Problem definition and formulation The objective of RCPSP is to allocate the available re-

sources to activities so as to find the shortest duration of a project within the constraints of precedence relationships. The assumptions underlying this problem are that the avail- ability of resources is constrained to some maximum value and that the project has to be completed using the given re- sources. As a result of the RCPSP, a schedule that shows the shortest duration with resource limits is created for a project network. The objective function is formulated for exploring a solution to the RCPSP. As a constrained optimization

Table 1. Various solution approaches to resource-constrained project scheduling problem.

Approach Method Advantage Disadvantage Exact solution Dynamic programming Optimal solutions for

small-sized projects Suitable for a small size of

project instance; requires complicated assumptions

Zero-one integer programming Implicit enumeration with

branch-and-bound Priority rule-based heuristic Single-pass methods; May produce solutions

regardless of the project size Uses rules of thumb and

experience; dependent on the project instance; the quality of the solutions is inconsistent

Multi-pass methods (multi-priority rule methods, forward-backward schedul- ing methods, and sampling methods)

Meta-heuristic Genetic algorithm Applicable to overcome the drawbacks of two approaches above and to improve the performance of the meta-heuristic methods

Difficult to choose an encoding and fitness function; requires long computation time

Simulated annealing Tabu search Ant colonies Forward-backward improvement

1018 Can. J. Civ. Eng. Vol. 36, 2009

Published by NRC Research Press

problem, the RCPSP represents one type of sequencing problem. Therefore, the proposed algorithm minimizes the project duration when constrained by precedence relation- ships among project activities and the availability of resour- ces. The single-project, single, and (or) multiple RCPSP can be formulated as follows:

minimize

½1� fðiÞ¼ maxfti þ diji ¼ 1; 2; :::ng

subject to

½2� tj � ti � di; 8j 2 Si

½3� XP

p¼1

m¼1

i¼1 HRRimt �

p¼1

m¼1 X

RA mt

½4� fðiÞ� 0

where, N is the total number of activities, P is the total number of time periods, such as days, and M is the total number of resource types. The symbols of f(i), di, ti,j, and Si stand for the fitness function of an individual, which means the finish time of activity i, the duration of activity i, the starting date of activity i and j, and the set of successors of activity i, respectively. HRRimt and X

RA mt mean the resource re-

quirement of mth resource of activity i on time p and the resource availability of mth resource of activity i on time p, respectively.

For ease of notation, the activities are topologically or- dered, i.e., each predecessor of activity i has a smaller num- ber i. It is assumed that daily resource requirements of any activity are predetermined. Equation [1] expresses the com- putation of the project duration, which is the objective func- tion of the RCPSP. Equation [2] takes into consideration the precedence relations between each pair of activities (i, j), where i immediately precedes j. This constraint states that the difference between the starting times of successor activ- ities and those of predecessor activities should be equal to or greater than the duration of the connecting activity. Equation [3] limits the total resource usage within each period to the available amount. This constraint indicates that the sum of all available resource units allocated to different activities on the same day should not exceed the total number of units available on that day. Finally, eq. [4] states that the fitness value, which is the finish time of an activity i of an individ- ual schedule is always equal to or greater than zero.

Improved elitist genetic algorithm This section presents a permutation-based elitist GA to

search for an optimal solution to the resource-constrained scheduling of large projects by implementing the improved parallel schedule generation scheme as a decoding proce- dure. Figure 1 illustrates the main procedure of the proposed algorithm. The permutation-based elitist GA was developed using four basic operators: (i) elite selection; (ii) roulette wheel selection; (iii) one-point crossover; and (iv) uniform mutation. The initial population of possible solutions to the RCPSP was created to apply the algorithm in the first step

of global search. A fitness value of an individual in the ini- tial population was calculated using the improved parallel schedule generation scheme. The improved parallel schedule generation scheme is the extended process composed of the parallel scheme and the transformation method, which is one of the unique characteristics for the proposed algorithm. The selection of the parent individuals was made through the elitist roulette wheel selection operator for the next genera- tion, which is another for the algorithm. The elitist roulette wheel selection operator combines using the elite selection and the roulette wheel selection. Using the parent individu- als obtained from the selection operator, one-point crossover operator performs by exchanging parent individual segments and then recombining them to produce two resulting off- spring individuals. The uniform mutation operator plays the role of a random local search.

Encoding and decoding procedure This section presents an encoding and decoding procedure

for the proposed algorithm. Hartmann (1998) proposed three encodings: (i) a permutation-based GA; (ii) a priority value- based GA similar to the work of Lee and Kim (1996); and (iii) a priority rule-based GA similar to the work of Dorn- dorf and Pesch (1995). Table 2 tabulates three different types of individuals for encoding that were used for compar- ison purpose. The permutation-based encoding GA was shown to outperform the two other encoding algorithms. The writer adopts a permutation-based encoding procedure. A solution for the resource-constrained scheduling is repre- sented in a chromosome that illustrates an activity sequence for the problem. Each gene in a chromosome stands for an activity number. An activity has a lower priority than all preceding activities in the sequence and a higher priority than all succeeding activities. Thus, an individual becomes a precedence feasible permutation of the set of activities. An activity cannot come after the position of one of its suc- cessors (predecessors) in the list used for the generation of an individual. Precedence feasible individuals were gener- ated using the random number generator (Kim 2006). The random number generator simply provides precedence feasi- ble solutions, but does not give the fitness value (the project duration), a possible starting and finishing time of an activ- ity, and the feasibility of resource constraints. The random number generator, for example, generates an individual {2, 7, 1, 6, 4, 3, 8, 9, 5, 11, 10} for 11 nondummy activities.

Improved parallel schedule generation scheme This section presents the improved parallel schedule gen-

eration scheme to calculate the fitness value of an individ- ual. The improved parallel schedule generation scheme is the extended process composed of the parallel scheme and the transformation method. A new parameter, named trans- formation power, is created within the transformation method of the improved parallel scheme for the accurate in- dividual selection process. Applying the improved parallel scheme into the individuals in a population enables us to ob- tain accurate schedules that show the resource profile and the project duration. A uniquely determined schedule (phe- notype) computed using the improved parallel scheme can be related to more than one individual (genotype). As shown in Fig. 2, a uniquely determined schedule means that it is

Kim 1019

Published by NRC Research Press

possible for several individuals to have the same fitness value that is equal to the project duration, but their starting time should be totally different. The unique schedules as genotypes in the search space may be related to the same schedule, which is the project duration for the RCPSP.

The parallel scheme consists of J stages in each of which a set of activities is scheduled. A unique feature of the par- allel scheme is that each stage n is associated with a sched- ule time tn, where tm £ tn for m £ n holds. On account of this schedule time, the set of scheduled activities is divided into the following two subsets: (i) activities which were sched- uled and are completed up to the schedule time are in the complete set (Cn); and (i) activities which were scheduled, but which are still active at the schedule time, are in the ac- tive set (An).

Also the decision set (Dn) exists like the serial schedule generation scheme. In contrast to the serial scheme, the par- allel scheme contains all as yet unscheduled activities that are available for scheduling with regard to precedence and resource constraints. The partial schedule of each stage is made by the activities in the complete set and the active set. The schedule time of a stage is equal to the earliest comple- tion time of activities in the active set of the previous stage. Each stage is made up of two steps: First, the new schedule time is determined and activities with a finish time equal to the (new) schedule time are removed from the active set and put into the complete set. This, in turn, may place a number of activities into the decision set. Second, one activity from the decision set is selected according to the order of the ac- tivity list representation and scheduled to start at the current schedule time. Afterwards, this activity is removed from the

decision set and put into the active set. The second proce- dure is repeated until the decision set is empty; i.e., activ- ities were scheduled or are no longer available for scheduling with regard to resource constraints. The parallel scheme terminates when all activities are in the complete set or active set.

As a sequential process, the proposed algorithm performs the transformation of the fitness values. As the objective function for the RCPSP is to minimize the fitness function, a transformation from minimization to maximization was needed to ensure that the individual selection process per- forms correctly. Various transformation methods can be used to transform an original objective function value to a fitness value. For example, a fitness value can be obtained either by subtracting the objective function value from an arbitrary large constant or by taking the reciprocal of the ob- jective function value. Thetransformation method proposed by Lee and Kim (1996) was modified by adding a new pa- rameter, named transformation power (TP), to their trans- formed objective function to emphasize low fitness values, as shown in eq. [5]:

½5� bf ðiÞ¼ exp

� �h�fðiÞTP

�

where, bf ðiÞis a transformed fitness value, f(i) is an original fitness value obtained from the application of the parallel schedule generation scheme, h is a parameter to be chosen to make the fitness value lie in a particular range between 0 and 1 and set to 0.004, and TP is a transformation power set to 1.6 based on trial and error. The addition of the transfor- mation power showed how much the transformed fitness va-

Fig. 1. Main procedure of the proposed algorithm.

Table 2. Comparison of the individuals used in three genetic algorithms.

Encoding Individual I Example Permutation-based encoding I = {j1I,. . .. . .. . ., jJI} I = {2, 4, 6, 1, 3, 5} Priority value-based encoding I = {pv1I,. . .. . .. . ., pvJI} I = {0.58, 0.64, 0.31, 0.87, 0.09, 0.34} Priority rule-based encoding I = {pr1I, . . .. . .. . ., prJI} I = {LFT, LST, MTS, MSLK, WRUP, GRPW}

1020 Can. J. Civ. Eng. Vol. 36, 2009

Published by NRC Research Press

lues can be emphasized by making the original fitness va- lues low.

Genetic operators This section presents the genetic operators that were used

in the development of the proposed algorithm. The selec- tion operation generally plays the role of choosing parent chromosomes for crossover. The concept of the selection was to determine selection probability for each individual proportional to the fitness value. The proposed algorithm first employs the elitist strategy that keeps copying the best chromosome to the new population while the rest of the population remains as normal. It then selects parent chro- mosomes using the roulette wheel selection method. Figure 3 illustrates the individuals in the population of the last generation to show the selection process of the elitist indi- vidual. The selection by elitism enables the proposed algo- rithm to increase the performance of the GA rapidly because it prevents a loss of the best found solution. Among all the individuals from previous generations, the best individual, elite, does not always pass to a new popu- lation.

The goal of a crossover operator is to combine pieces of information coming from different individuals in the popula- tion. Both preserving good building blocks and maintaining randomness and population diversity are important for searching nonredundant solutions. The order of the first sev- eral activities is the key to preserving the whole individual, providing the basis for the remaining activities, and deciding how good the order of the remaining activities will be to a certain degree. Good activity combinations are likely to be among the first several activities. It is less variable if the starting times for schemata is fixed early in the genotype be- cause there are only a limited number of activities that can be scheduled to start at time t = 0 based on precedence rela- tionships. On the other hand, many more potential activities can be scheduled to start at a much later point in time. For example, schema of the genotypes {1, 2, *, *, *, *, *, *, *, *, *} or {2, 1, *, *, *, *, *, *, *, *, *} will be likely to schedule at the same starting time if they do not violate the resource constraints. A schema defined later in the genotype such as {*, *, *, *, *, *, *, *, *, 9, 11} is likely to represent

many different starting times for activities 9 and 11 based on the ordering of the unfixed positions.

Two different types of crossover operators, union cross- over operator 3 (UX3) (Leu and Yang 1999) and one-point crossover (Hartmann 1998), were identified as good meth- ods for the permutation-based encoding for the solution to the RCPSP. They were developed to deal with this type of ordering problem that occurred due to crossover operation. The performance of the UX3 operator was reduced as it caused significant change to the individual representations of the parent individuals by disrupting potential building blocks and high fitness schema at each generation (Zhuang and Yassine 2004). Their findings are reasonable because if better solutions were found with UX3, it is not due to the recombination theories fundamental to the GA, but to the randomization of UX3. The major characteristic of the UX3 operator is that it must change gene positions more fre- quently than the one-point crossover operator. It is notable that the same issue can be raised when applying the one- point crossover operator, but one-point crossover preserves the good schemas by keeping the first half of activities in- tact (Reeves 1995; Hartmann 1998). For this reason, the one-point crossover operator was selected for the permuta- tion-based encoding to the RCPSP. Figure 4 illustrates the operation of one-point crossover that produces new offspring individuals. The one-point crossover operator is capable of preserving schemata in a more effective manner because it

Fig. 2. Uniquely determined schedules.

Fig. 3. Individuals in the population of the last generation.

Kim 1021

Published by NRC Research Press

keeps the first half of both parents intact and is less random than UX3.

The goal of the uniform mutation is to exchange two neighboring genes without violating the precedence relation- ship to create an individual that could not have been pro- duced by the crossover operator. The uniform mutation operator was performed in two steps: (i) the operator gener- ates a real random number for each individual from a gener- ation; and (ii) it swaps an activity after a pivot point with the activity at a pivot point if a random number is equal to or less than the mutation probability. Figure 5 illustrates the operation of uniform mutation that produces a new offspring individual. This operator could be ineffective because the genes in neighboring individual positions could be switched while still representing the same schedule. Therefore, it is important to note that a mutation on an individual does not necessarily change the related schedule because interchang- ing two activities that have the same start time in the activ- ity sequence is likely to change the individual, but not the related schedule.

Experimental results and analysis The permutation-based elitist GA using the improved par-

allel schedule generation scheme was programmed and tested using the Java programming language on a Pentium 4 CPU 3.06 GHz processor and 448 MB of RAM under the Windows XP operating system. Microsoft Office Excel 2003 was selected as the representation and analysis tool for the data. The parameters of the developed algorithm in- clude population size, transformation power, crossover prob- ability, and mutation probability for global search. Three different types of termination conditions can be determined to stop the run of the algorithm. They include the number of generations, timeout, and the number of unique schedules. After preliminary studies, the parameter configurations were determined to obtain the best performance from the algo- rithm because the population size and various parameters were the critical elements for optimal performance. The next section consists of two parts: (i) sensitivity analysis that examines the effects of genetic operators used in the proposed algorithm; and (ii) implementation aspects that in- clude multiple renewable resources and large-sized projects.

Sensitivity analysis This section presents the effects of the elitist roulette se-

lection operator, the one-point crossover operator, and the uniform mutation operator on the performance of the devel- oped algorithm. A case example of a construction project schedule was selected from the work of Shanmuganayagam (1989). Figure 6 shows the precedence diagram for the case example of 11 nondummy activities associated with multiple resources. The diagram also includes activity name, dura- tion, and resource requirements. The developed algorithm on the case example was tested using a single resource to demonstrate the robustness of the current approach. The de- fault set of the parameters is as follows: the population size, transformation power, crossover and mutation probability were set to 30, 1.6, 0.5, and 0.03, respectively. The algo- rithm was terminated with 100 generations using the im- proved parallel schedule generation scheme.

Using the elitist roulette selection operator, the developed algorithm first preserves the best individual generated up to generation t into the current generation t+1, as the fitness value of an individual in the current population is larger than that of every individual in the current population. Fig- ure 7 shows the profile of the schedule obtained from the elitist individual, which was produced from the top of the individuals in the last generation of 100. The project dura- tion was found at 38 d, which is the same as one produced by GA-scheduler (Chan et al. 1996) to the case example problem.

To examine the effects of the one-point crossover and the uniform mutation operators, two runs associated with differ- ent probabilities were conducted for each operator. Figure 8a shows the convergence behaviors of standard deviation fitness values between two different crossover probabilities of 0 and 0.5 to illustrate the difference due to the crossover operation. It is notable that when no crossover occurred, the algorithm could not reach the optimal fitness value (38 d) with fluctuation of standard deviation values. The mean fit- ness values with the crossover probability of zero did not converge to the single value, as opposed to that with the crossover probability of 0.5. The one-point crossover per- formed well overall with consistent standard deviation val- ues after 35 generations. Figure 8b shows the convergence behaviors of standard deviation fitness values between two different mutation probabilities of 0 and 0.03 to illustrate the difference due to the mutation operation. It is notable that when no mutation occurred, the algorithm could reach the optimal fitness value (38 d) with the consistent standard deviation values after 22 generations. It seems likely to show the premature convergence, which is the disadvantage of the mutation operator. The mean fitness values with the mutation probability of 0.03 did converge to the single value later than the mutation probability of zero, as opposed to the

Fig. 4. New offspring individuals produced by crossover operation. Fig. 5. New offspring individual produced by mutation operation.

1022 Can. J. Civ. Eng. Vol. 36, 2009

Published by NRC Research Press

result of the crossover operation. This result means that the uniform mutation works well to avoid the premature conver- gence, because when the mutation occurred in a certain de- gree, the solution space is more explored than when it did not occur.

Implementation aspects This section presents the implementation aspects of the

developed algorithm using two experiments: (i) multiple re- newable resources; and (ii) large-sized projects. The first ex- periment was run to take into account multiple resources using the same case example. Three different types of re- sources were considered. When multiple resources are re- quired, project duration will vary depending on the resource availability and requirements. The resource availabilities are constant over the project duration for this experiment. The resource availabilities of three resources are assumed to be

8, 1, and 1, for R1, R2, and R3, respectively. After many trials, the population size, transformation power, crossover rate, and mutation rate were set to 50, 1.6, 0.5, and 0.03, re- spectively. The overall fitness value, which is the project duration of the individual considered, was obtained for mul- tiple resources using the improved parallel schedule genera- tion scheme. Figure 9 shows the result of scheduling the case example with multiple resources. The project duration was 54 d, which is longer than the one obtained for a single resource due to resource conflicts. It was found that activity 9 was delayed for two days due to conflict with R2. It was also found that activities 3 and 10 were postponed for six and ten days due to resource conflicts with R3, respectively.

The second experiment was conducted for large-sized projects to verify the performance of the developed algo- rithm using the improved parallel schedule generation scheme. Ninety instance projects were selected from the

Fig. 6. Precedence diagram of case example. ES, early start; EF, early finish; LS, late start; LF, late finish; TF, total float; Act, activity; Dur, duration.

Fig. 7. Profile of the schedule produced by the elitist.

Kim 1023

Published by NRC Research Press

project scheduling problem library (PSPLIB) for this experi- ment (Kolisch and Sprecher 1997). The projects consist of 30 problems for each of 30, 60, and 120 activities. Each problem instance has four renewable resources. The overall performance of the developed algorithm was measured by the means of finding the best fitness values, which are com- pared with the optimal and lower bound solutions. The opti- mal solutions for the projects with 30 activities are known. Only heuristic solutions, which are lower bound solutions, are known for the projects with 60 and 120 activities. The

input parameter values for the algorithm are as follows: Ini- tial population size, transformation power, crossover proba- bility, mutation probability were set to 50, 1.6, 0.5, and 0.03, respectively. To obtain the required computational re- sults, the termination condition was set to the maximum number of 100 unique schedules for each of ninety projects. The moment when the best solution was found for the first time is considered an optimal and (or) near optimal solution because their standard deviations converge to zero.

Table 3 shows the comparison results with well-known

Fig. 8. Convergence behaviors of standard deviation: (a) one-point crossover; (b) uniform mutation. Cp, crossover probability; Mp, mutation probability.

1024 Can. J. Civ. Eng. Vol. 36, 2009

Published by NRC Research Press

Fig. 9. Scheduling result with multiple resources.

Table 3. Comparison results with well-known optimality. (Bold numbers indicate that solutions from proposed algorithm exactly match optimal and lower bound solutions.)

Project size 30-Activity 60-Activity 120-Activity

Test ID Optimality Improved GA Lower bound Improved GA Lower bound Improved GA 1 59 59 78 78 79 79 2 67 67 78 78 88 88 3 65 65 79 79 100 100 4 64 64 71 71 71 71 5 57 57 82 87 81 84 6 59 59 87 87 102 102 7 59 59 75 75 93 93 8 58 58 72 73 77 77 9 49 49 60 65 86 86

10 55 55 79 84 103 103 11 58 58 75 75 70 74 12 59 59 66 66 107 107 13 55 55 69 69 91 95 14 49 49 76 76 75 75 15 47 47 87 87 74 74 16 53 53 76 76 85 90 17 66 66 68 68 81 81 18 48 48 71 71 90 90 19 65 65 76 76 79 79 20 60 60 66 66 77 77 21 63 63 71 71 92 92 22 54 54 87 87 80 80 23 50 50 84 84 72 72 24 57 57 62 62 97 97 25 58 58 101 101 77 77 26 58 58 66 66 88 88 27 55 55 77 77 84 84 28 44 44 88 88 78 78 29 59 59 82 82 106 106 30 54 54 70 70 92 92

Kim 1025

Published by NRC Research Press

optimal and lower bound solutions. The writer measured the minimum fitness values for each of 30 problems by project size. Bold numbers in Table 3 indicate that the solutions found from the proposed algorithm exactly match with the optimal and lower bound solutions. The proposed algorithm found 30 optimal solutions out of 30 problems associated with 30 activities, while it produced 24 suboptimal solutions out of 30 problems associated with both 60 and 120 activ- ities. The algorithm also produced the average deviation from the optimal and lower bound solutions of 0.00%, 0.74%, and 0.66% for the projects associated with 30, 60, and 120 activities, respectively. The algorithm performed well overall for the large-sized projects associated with mul- tiple renewable resources. The algorithm converges to a sin- gle point across the number of generations as it searches for the solution space.Note: GA, genetic algorithm.

Conclusions A schedule generation scheme is essential in most heuris-

tic solution procedures for the resource-constrained project scheduling problem. The computation of a fitness value is a vital mechanism in the meta-heuristic approaches to the re- source-constrained scheduling. As an attempt to address the lack of an efficient algorithm using the parallel schedule gen- eration scheme, this paper presented an improved elitist GA for resource-constrained scheduling of large projects. The improved parallel schedule generation scheme was well in- corporated in the proposed algorithm. The new parameter, named transformation power, performed accurately for the individual selection process. The elitist individual, which is produced from the top of the individuals in the last genera- tion, provided the same project duration as the one obtained from the other GA method. The performances of the genetic operators used in the algorithm showed their capability to search for the solution. Extensive computational results using large-sized multiple resource-constrained project scheduling problems showed that the proposed algorithm demonstrated its performance and accuracy through the comparisons with optimal and lower bound solutions. Additional studies are being conducted to investigate the computation time for the algorithm as well as to incorporate other local search algo- rithms to search for an optimal solution that the GA cannot explore. In addition, a user friendly interface of the algorithm is under development for running numerous resource-con- strained project scheduling problems at the same time.

Acknowledgements The writer would like to thank Dr. Anurag Agarwal at the

Department of Information Systems and Operations Man- agement, University of Florida for providing me with the optimal and lower bound solutions to the problems. I am grateful to anonymous referees for their critical and con- structive comments that improved the quality of this paper.

References Alcaraz, J., and Maroto, C. 2001. A robust genetic algorithm for

resource allocation in project scheduling. Annals of Operations Research, 102(1-4): 83–109. doi:10.1023/A:1010949931021.

Baar, T., Brucker, P., and Knust, S. 1999. Tabu-search algorithms and lower bounds for the resource-constrained project schedul-

ing problem. In Meta-heuristics: Advances and trends in local search paradigms for optimization. Edited by S. Voss, S. Mar- tello, I. Osman, and C. Roucairol. Kluwer Academic Publishers, Boston, Mass. pp. 1–18.

Boctor, F.F. 1996. Resource-constrained project scheduling by si- mulated annealing. International Journal of Production Research, 34(8): 2335–2351. doi:10.1080/00207549608905028.

Bouleimen, K., and Lecocq, H. 2003. A new efficient simulated an- nealing algorithm for the resource-constrained project schedul- ing problem and its multiple modes version. European Journal of Operational Research, 149(2): 268–281. doi:10.1016/S0377- 2217(02)00761-0.

Chan, W., Chua, D.K.H., and Kannan, G. 1996. Construction re- source scheduling with genetic algorithms. Journal of Construc- tion Engineering and Management, 122(2): 125–132. doi:10. 1061/(ASCE)0733-9364(1996)122:2(125).

Dorndorf, U., and Pesch, E. 1995. Evolution based learning in a job shop scheduling environment. Computers & Operations Re- search, 22(1): 25–40. doi:10.1016/0305-0548(93)E0016-M.

Goldberg, D.E. 1989. Genetic algorithms in search, optimization, and machine learning. Addison-Wesley Publishing Company, Inc., Reading, Mass.

Hartmann, S. 1998. A competitive genetic algorithm for resource- constrained project scheduling. Naval Research Logistics, 45(7): 733–750. doi:10.1002/(SICI)1520-6750(199810)45:7<733::AID- NAV5>3.0.CO;2-C.

Hartmann, S. 2002. A self-adapting genetic algorithm for project scheduling under resource constraints. Naval Research Logistics, 49(5): 433–448. doi:10.1002/nav.10029.

Hegazy, T. 1999. Optimization of resource allocation and leveling using genetic algorithms. Journal of Construction Engineering and Management, 125(3): 167–175. doi:10.1061/(ASCE)0733- 9364(1999)125:3(167).

Herroelen, W. 2004. Project scheduling-theory and practice. Pro- duction and Operations Management, 14(4): 413–432.

Herroelen, W., and Leus, R. 2005. Identification and illumination of popular misconceptions about project scheduling and time buffering in a resource-constrained environment. The Journal of the Operational Research Society, 56(1): 102–109. doi:10.1057/ palgrave.jors.2601813.

Hindi, K.S., Yang, H., and Fleszar, K. 2002. An evolutionary algo- rithm for resource-constrained project scheduling. IEEE Trans- actions on Evolutionary Computation, 6(5): 512–518. doi:10. 1109/TEVC.2002.804914.

Holland, J.K. 1975. Adaptation in neural and artificial systems. University of Michigan Press, Ann Arbor, Mich.

Kim, J.-L. 2006. A multiheuristic approach to resource constrained project scheduling: an adaptive hybrid genetic algorithm. Ph.D. dissertation, Department of Civil and Coastal Engineering, Uni- versity of Florida, Gainesville, Fla.

Kim, J.-L., and Ellis, R.D. 2008. Permutation-based elitist genetic algorithm for optimization of large-sized resource-constrained project scheduling. Journal of Construction Engineering and Management, 134(11): 904–913. doi:10.1061/(ASCE)0733- 9364(2008)134:11(904).

Kohlmorgen, U., Schmeck, H., and Haase, K. 1999. Experiences with fine-grained parallel genetic algorithms. Annals of Opera- tions Research, 90: 203–219. doi:10.1023/A:1018912715283.

Kolisch, R., and Sprecher, A. 1997. PSPLIB - a project scheduling problem library. European Journal of Operational Research, 96(1): 205–216. doi:10.1016/S0377-2217(96)00170-1.

Lee, J.-K., and Kim, Y.-D. 1996. Search heuristics for resource- constrained project scheduling. The Journal of the Operational Research Society, 47(5): 678–689. doi:10.2307/3010018.

1026 Can. J. Civ. Eng. Vol. 36, 2009

Published by NRC Research Press

Leu, S., and Yang, C. 1999. GA-based multicriteria optimal model for construction scheduling. Journal of Construction Engineering and Management, 125(6): 420–427. doi:10.1061/(ASCE)0733- 9364(1999)125:6(420).

Pinson, E., Prins, C., and Rullier, F. 1994. Using tabu search for solving the resource-constrained project scheduling problem. In Proceedings of the 4th International Workshop on Project Man- agement and Scheduling, Leuven, Belgium. pp. 102–106.

Reeves, C.R. 1995. Genetic algorithms and combinatorial optimiza- tion. Applications of Modern Heuristic Methods. Edited by V.J. Rayward-Smith. Alfred Waller, Henley-on-Thames, UK. pp. 111–125.

Shanmuganayagam, V. 1989. Current float techniques for resource scheduling. Journal of Construction Engineering and Manage- ment, 115(3): 401–411. doi:10.1061/(ASCE)0733-9364(1989) 115:3(401).

Toklu, Y.C. 2002. Application of genetic algorithms to construction scheduling with or without resource constraints. Canadian Jour- nal of Civil Engineering, 29(3): 421–429. doi:10.1139/l02-034.

Valls, V., Quintanilla, S., and Ballestin, F. 2003. Resource-con- strained project scheduling: a critical activity reordering heuris- tic. European Journal of Operational Research, 149(2): 282–301. doi:10.1016/S0377-2217(02)00768-3.

Valls, V., Ballestin, F., and Quintanilla, S. 2005. Justification and RCPSP: a technique that pays. European Journal of Operational Research, 165(2): 375–386. doi:10.1016/j.ejor.2004.04.008.

Zhuang, M., and Yassine, A.A. 2004. Task scheduling of parallel development projects using genetic algorithm. In Proceedings of ASME 2004 International Design Engineering Technical Con- ferences and Computers and Information in Engineering Confer- ence, Salt Lake City, Utah USA, September 28-October 2, 2004. pp. 1–11.

Kim 1027

Published by NRC Research Press