An Evolutionary Algorithm with Multi-Local Search for the Resource-Constrained Project Scheduling Problem
- 1
- 2
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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- R. Kolisch and A. Drexl, “Adaptive search for solving hard project scheduling problems,” Naval Research Logistics, Vol. 43, pp. 23–40, 1996.
- 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.
- 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.
- 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.
- 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.
- S. Hartmann, “A competitive genetic algorithm for resource-constrained project scheduling,” Naval Research, Logistics, Vol. 45, pp. 733–750, 1998.