An Evolutionary Algorithm with Multi-Local Search for the Resource-Constrained Project Scheduling Problem

Zhi-Jie Chen, Chiuh-Cheng Chyu

.

DOI: 10.4236/iim.2012.23026                

Abstract

This paper introduces a hybrid evolutionary algorithm for the resource-constrained project scheduling problem (RCPSP). Given an RCPSP instance, the algorithm identifies the problem structure and selects a suitable decoding scheme. Then a multi-pass biased sampling method followed up by a multi-local search is used to generate a diverse and good quality initial population. The population then evolves through modified order-based recombination and mutation operators to perform exploration for promising solutions within the entire region. Mutation is performed only if the current population has converged or the produced offspring by recombination operator is too similar to one of his parents. Finally the algorithm performs an intensified local search on the best solution found in the evolutionary stage. Computational experiments using standard instances indicate that the proposed algorithm works well in both computational time and solution quality.

Keywords

Resource-Constrained Project Scheduling, Evolutionary Algorithms, Local Search, Hybridization

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	J. Blazewicz, J. K. Lenstra, and A. H. G. Rinooy Kan, “Scheduling subject to resource constraints: Classification and complexity,” Discrete Applied Mathematics, Vol. 5, pp. 11–24, 1983.
[2]	P. Brucker, A. Drexl, R. Mohring, K. Neumann, and E. Pesch, “Resource-constrained project scheduling: Notation, classification, models, and methods,” European Journal of Operational Research, Vol. 112, pp. 3–41, 1999.
[3]	S. Hartmann, and R. Kolisch, “Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem,” European Journal of Operational Research, Vol. 127, pp. 394–407, 2000.
[4]	R. Kolisch, “Serial and parallel resource-constrained project scheduling problem revisited: Theory and computation,” European Journal of Operational Research, Vol. 90, pp. 320–333, 1996.
[5]	A. Minggozzi, V. Maniezzo, S. Ricciardelli, and L. Bianco, “An exact algorithm for project scheduling with resource constraints based on a new mathematical formulation,” Management Science, Vol. 44, pp. 714–729, 1998.
[6]	U. Dorndorf, E. Pesch, and T. Phan-Huy, “A branch-and- bound algorithm for the resource constrained project scheduling problem,” Mathematical Methods of Operations Research, Vol. 52, pp. 413–439, 2000.
[7]	R. Kolisch and A. Drexl, “Adaptive search for solving hard project scheduling problems,” Naval Research Logistics, Vol. 43, pp. 23–40, 1996.
[8]	A. Schirmer, “Case-based reasoning and improved adaptive search for project scheduling,” Technical Report 472, Manuskripte aus den Institute fur Betriebswirtschaftslehre der Universit?t Kiel, 1998.
[9]	R. Klein, “Bidirectional planning: Improving priority rule-based heuristics for scheduling resource-constrained projects,” European Journal of Operational Research, Vol. 127, pp. 619–638, 2000.
[10]	P. Toromos, and A. Lova, “A competitive heuristic solu- tion technique for resource-constrained project scheduling,” Annals of Operations Research, Vol. 102, pp. 65–81, 2001.
[11]	T. Barr, P. Brucker, and S. Knust, “Tabu search algorithms and lower bounds for the resource-constrained project scheduling problem,” in S. Voss, S. Martello, I. Osman, and C. Roucarion (Ed.), Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization, Norwell, Kluwer, MA, pp. 1–18, 1998.
[12]	S. Hartmann, “A competitive genetic algorithm for resource-constrained project scheduling,” Naval Research, Logistics, Vol. 45, pp. 733–750, 1998.
[13]	S. Hartmann, “A self-adapting genetic algorithm for pro- ject scheduling under resource constraints,” Naval Re- search Logistics, Vol. 49, pp. 433–448, 2002.
[14]	D. Merkle, M. Middendorf, and H. Schmeck, “Ant colony optimization for resource-constrained project scheduling,” IEEE Transactions on Evolutionary Computation, Vol. 6, pp. 333–346, 2002.
[15]	K. Bouleimen and H. Lecocq, “A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version,” European Journal of Operational Research, Vol. 149, pp. 268–281, 2003.
[16]	K. Fleszar and K. Hindi, “Solving the resource-constrained project scheduling problem by a variable neighborhood search,” European Journal of Operational Research, Vol. 155, pp. 402–413, 2004.
[17]	V. Valls, F. Ballestin, and S. Quintanilla, “A population-based approach to the resource-constrained project scheduling problem,” Annals of Operations Research, Vol. 131, pp. 305–324, 2004.
[18]	D. Debels, B. D. Reyck, R. Leus, and M. Vanhoucke, “A hybrid scatter search/electromagnetism meta-heuristic for project scheduling,” European Journal of Operational Research, Vol. 169, pp. 638–653, 2006.
[19]	V. Valls, F. Ballestin, and S. Quintanilla, “Justification and RCPSP: A technique that pays,” European Journal of Operational Research, Vol. 165, pp. 375–386, 2005.
[20]	R. Kolisch and S. Hartmann, “Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling: An update,” European Journal of Operational Research, Vol. 174, pp. 23–37, 2006.
[21]	R. Kolisch and A. Sprecher, “PSPLIB-A project scheduling problem library,” European Journal of Operational Research, Vol. 96, pp. 205–216. 1996.
[22]	K. Y. Li and R. J. Willis, “An iterative scheduling technique for resource constrained project scheduling,” European Journal of Operational Research, Vol. 56, pp. 370–379, 1992.
[23]	L. ?zdamar and G. Ulusory, “A note on an iterative forward/backward scheduling technique with reference to a procedure by Li and Willis,” European Journal of Operational Research, Vol. 89, pp. 400–407, 1996.