Abstract
The resource-constrained project scheduling problem (RCP- SP) is one of the most challenging problems in project scheduling. During the last couple of years many heuristic procedures have been developed for this problem, but still these procedures often fail in finding near-optimal solutions for more challenging problem instances. In this paper, we present a new genetic algorithm (GA) that, in contrast of a conventional GA, makes use of two separate populations. This bi-population genetic algorithm (BPGA) operates on both a population of left-justified schedules and a population of right-justified schedules in order to fully exploit the features of the iterative forward/backward scheduling technique. Comparative computational results reveal that this procedure can be considered as today’s best performing RCPSP heuristic.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alcaraz, J., Maroto, C.: A robust genetic algorithm for resource allocation in project scheduling. Annals of Operations Research 102, 83–109 (2001)
Baar, T., Brucker, P., Knust, S.: Tabu-search algorithms and lower bounds for the resource-constrained project scheduling problem. Meta-heuristics: Advances and trends in local search paradigms for optimization, 1–8 (1998)
Bouleimen, K., Lecocq, H.: A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. European Journal of Operational Research 149, 268–281 (2003)
Coelho, J., Tavares, L.: Comparative analysis of meta-heuricstics for the resource constrained project scheduling problem. Technical report, Department of Civil Engineering, Instituto Superior Tecnico, Portugal (2003)
Debels, D., De Reyck, B., Leus, R., Vanhoucke, M.: A scatter-search meta-heuristic for the resource-constrained project scheduling problem. European Journal of Operational Research (forthcoming)
Hartmann, S.: A competitive genetic algorithm for the resource-constrained project scheduling. Naval Research Logistics 45, 733–750 (1998)
Hartmann, S.: A self-adapting genetic algorithm for project scheduling under resource constraints. Naval Research Logistics 49, 433–448 (2002)
Hartmann, S., Kolisch, R.: Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. European Journal of Operational Research 127, 394–407 (2000)
Herroelen, W., Demeulemeester, E., De Reyck, B.: A classification scheme for project scheduling. In: Weglarz, J. (ed.) Project Scheduling - Recent Models, Algorithms and Applications. International Series in Operations Research and Management Science, vol. 14, pp. 77–106. Kluwer Academic Publishers, Boston (1998)
Holland, J.H.: Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor (1975)
Kochetov, Y., Stolyar, A.: Evolutionary local search with variable neighbourhood for the resource constrained project scheduling problem. In: Proceedings of the 3rd International Workshop of Computer Science and Information Technologies (2003)
Kolisch, R., Drexl, A.: Adaptive search for solving hard project scheduling problems. Naval Research Logistics 43, 23–40 (1996)
Kolisch, R., Hartmann, S.: Heuristic algorithms for solving the resource-constrained project scheduling problem: classification and computational analysis. In: Weglarz, J. (ed.) Project Scheduling - Recent Models, Algorithms and Applications, pp. 147–178. Kluwer Academic Publishers, Boston (1999)
Kolisch, R., Hartmann, S.: Experimental investigation of Heuristics for resourceconstrained project scheduling: an update, working paper, Technical University of Munich (2004)
Kolisch, R., Sprecher, A.: PSPLIB - A project scheduling library. European Journal of Operational Research 96, 205–216 (1996)
Kolisch, R.: Project scheduling under resource constraints - Efficient heuristics for several problem classes. Physica (1995)
Kolisch, R.: Serial and parallel resource-constrained project scheduling methods revisited: theory and computation. European Journal of Operational Research 43, 23–40 (1996)
Kolisch, R.: Efficient priority rules for the resource-constrained project scheduling problem. Journal of Operations Management 14, 179–192 (1996)
Leon, V.J., Ramamoorthy, B.: Strength and adaptability of problem-space based neighbourhoods for resource-constrained scheduling. OR Spektrum 17, 173–182 (1995)
Li, K.Y., Willis, R.J.: An iterative scheduling technique for resource-constrained project scheduling. European Journal of Operational Research 56, 370–379 (1992)
Merkle, D., Middendorf, M., Schmeck, H.: Ant colony optimization for resource constrained project scheduling. IEEE Transaction on Evolutionary Computation 6(4), 333–346 (2002)
Nonobe, K., Ibaraki, T.: Formulation and tabu search algorithm for the resource constrained project scheduling problem (RCPSP). In: Ribeiro, C.C., Hansen, P. (eds.) Essays and Surveys in Meta-heuristics, pp. 557–588. Kluwer Academic Publishers, Boston (2002)
Schirmer, A.: Case-based reasoning and improved adaptive search for project scheduling. Naval Research Logistics 47, 201–222 (2000)
Tormos, P., Lova, A.: A competitive heuristic solution technique for resourceconstrained project scheduling. Annals of Operations Research 102, 65–81 (2001)
Tormos, P., Lova, A.: An efficient multi-pass heuristic for project scheduling with constrained resources. International Journal of Production Research 41, 1071–1086 (2003)
Tormos, P., Lova, A.: Integrating heuristics for resource constrained project scheduling: One step forward, Technical report, Department of Statistics and Operations Research, Universidad Politecnica de Valencia (2003)
Valls, V., Ballestin, F., Quintanilla, S.: A hybrid genetic algorithm for the Resourceconstrained project scheduling problem with the peak crossover operator. In: Eighth International Workshop on Project Management and Scheduling, pp. 368–371 (2002)
Valls, V., Quintanilla, S., Ballestin, F.: Resource-constrained project scheduling: a critical activity reordering heuristic. European Journal of Operational Research 149, 282–301 (2003)
Valls, V., Ballestin, F., Quintanilla, S.: A population-based approach to the resource-constrained project scheduling problem. Annals of Operations Research 131, 305–324 (2004)
Valls, V., Ballestin, F., Quintanilla, S.: Justification and RCPSP: A technique that pays. European Journal of Operational Research (Forthcoming)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Debels, D., Vanhoucke, M. (2005). A Bi-population Based Genetic Algorithm for the Resource-Constrained Project Scheduling Problem. In: Gervasi, O., et al. Computational Science and Its Applications – ICCSA 2005. ICCSA 2005. Lecture Notes in Computer Science, vol 3483. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11424925_41
Download citation
DOI: https://doi.org/10.1007/11424925_41
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25863-6
Online ISBN: 978-3-540-32309-9
eBook Packages: Computer ScienceComputer Science (R0)