Abstract
This paper presents a new genetic algorithm for the resource-constrained project scheduling problem (RCPSP). The algorithm employs a standardized random key (SRK) vector representation with an additional gene that determines whether the serial or parallel schedule generation scheme (SGS) is to be used as the decoding procedure. The iterative forward-backward improvement as the local search procedure is applied upon all generated solutions to schedule the project three times and obtain an SRK vector, which is reserved into population. Several evolutionary strategies are implemented including the elitist selection (the high quality solution set), and the selection of parents used in crossover operator. The computational experiments on 1 560 standard instances show that the proposed algorithm outperforms the current state-of-the-art heuristic algorithms for J30 and J60, and ranks the third for J120 with 50 000 schedules; it ranks the second for J30 and J60, and ranks the fifth for J120 with 5 000 schedules; it ranks the third, second, and fifth for J30, J60 and J120 with 1 000 schedules, respectively. It is demonstrated that the proposed algorithm is competitive for RCPSP, especially for larger number of schedules.
Similar content being viewed by others
References
Hartmann S, Kolisch R. Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem[J]. European Journal of Operational Research, 2000, 127(2): 394–407.
Kolisch R, Hartmann S. Experimental investigation of heuristics for resource-constrained project scheduling: An update[J]. European Journal of Operational Research, 2006, 174(1): 23–37.
Brucker P, Drexl A, Möhring R et al. Resource-constrained project scheduling: Notation, classification, models, and methods[J]. European Journal of Operational Research, 1999,112(1): 3–41.
Blazewicz J, Lenstra J, Rinnooy Kan A. Scheduling subject to resource constraints: Classification and complexity[ J]. Discrete Applied Mathematics, 1983, 5(1): 11–24.
Davis E W, Patterson J H. A comparison of heuristic and optimum solutions in resource-constrained project scheduling[J]. Management Science, 1975, 21(8): 944–955.
Kolisch R. Efficient priority rules for the resource-constrained project scheduling problem[J]. Journal of Operations Management, 1996, 14(3): 179–192.
Boctor F F. Some efficient multi-heuristic procedures for resource-constrained project scheduling[J]. European Journal of Operational Research, 1990, 49(1): 3–13.
Özdamar L, Ulusoy G. A note on an iterative forward/backward scheduling technique with reference to a procedure by Li and Wills[J]. European Journal of Operational Research, 1996, 89(2): 400–407.
Kolisch R, Drexl A. Adaptive search for solving hard project scheduling problem[J]. Naval Research Logistics, 1996, 43(1): 23–40.
Lee J K, Kim Y D. Search heuristics for resource constrained project scheduling[J]. Journal of Operational Research Society, 1996, 47(5): 678–689.
Alcaraz J, Maroto C, Ruiz R. Improving the performance of genetic algorithm for the RCPS problem[C]. In: Proceedings of the Ninth International Workshop on Project Management and Scheduling. Nancy, France, 2004. 40–43.
Hartmann S. A competitive genetic algorithm for resource-constrained project scheduling[J]. Naval Research Logistics, 1998, 45(7): 733–750.
Hartmann S. A self-adapting genetic algorithm for resource-constrained under project scheduling[J]. Naval Research Logistics, 2002, 49(5): 433–448.
Valls V, Ballestin F, Quintanilla S. A hybrid genetic algorithm for the resource-constrained project scheduling problem[ J]. European Journal of Operational Research, 2008, 185(2): 495–508.
Mendes J J, Goncalves J F, Resende M G C. A random key based genetic algorithm for the resource constrained project scheduling problem[J]. Computers & Operations Research, 2009, 36(1): 92–109.
Debels D, Vanhoucke M. A decomposition-based genetic algorithm for the resource-constrained project scheduling problem[J]. Operations Research, 2007, 55(3): 457–469.
Bouleimen K, Lecocq H. A new efficient simulated annealing algorithm for solving resource constrained project scheduling problem and its multiple modes version[J]. European Journal of Operational Research, 2003, 149(2): 268–281.
Nonobe K, Ibaraki T. Formulation and tabu search algorithm for the resource constrained project scheduling problem[C]. In: Essays and Surveys in Metaheuristics. Kluwer Academic Publishers, 2002. 557–588.
Merkle D, Middendorf M, Schemeck H. Ant colony optimization for resource-constrained project scheduling[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(4): 333–346.
Debels D, de Reyck B, Leus R et al. A hybrid scatter search/electromagnetism meta-heuristic for project scheduling[ J]. European Journal of Operational Research, 2006, 169(2): 638–653.
Ranjbar M. Solving the resource-constrained project scheduling problem using filter-and-fan approach[J]. Applied Mathematics and Computation, 2008, 201(1/2): 313–318.
Tormos P, Lova A. A competitive heuristic solution technique for resource-constrained project scheduling[J]. Annals of Operations Research, 2001, 102(1–4): 65–81.
Kochetov Y, Stolyar A. Evolutionary local search with variable neighborhood for the resource constrained project scheduling problem[C]. In: Proceedings of the 3rd International Workshop of Computer Science and Information Technologies. Russia, 2003.
Palpant M, Artigues C, Michelon P. LSSPER: Solving the resource-constrained project scheduling problem with large neighborhood search[J]. Annals of Operations Research, 2004, 131(1–4): 237–257.
Chambers L D. Practical Handbook of Genetic Algorithms: Applications[M]. CRC Press, Floride, 1995.
Kolisch R, Sprecher A. PSPLIB—A project scheduling problem library[J]. European Journal of Operational Research, 1996, 96(1): 205–216.
Author information
Authors and Affiliations
Corresponding author
Additional information
WANG Hong, born in 1973, female, Dr, associate Prof.
Rights and permissions
About this article
Cite this article
Wang, H., Li, T. & Lin, D. Efficient genetic algorithm for resource-constrained project scheduling problem. Trans. Tianjin Univ. 16, 376–382 (2010). https://doi.org/10.1007/s12209-010-1495-y
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12209-010-1495-y