Analytic and Heuristic Methodologies for Solving the Resource Constrained Project Scheduling Problem (RCPSP): a review Part 1

Main Article Content

Daniel Morillo https://orcid.org/0000-0001-7731-1104
Luis Moreno
Javier Díaz

Keywords

task scheduling, constrained resources, heuristic methods, exact methods.

Abstract

This paper presents and describes the most relevant methods for the solution of the Resource Constrained Project Scheduling Problem, RCPSP. A critical review of the state of the art, based on the most signicant papers published in the academic literature on this topic is carried out. First, several exact methods of solution are shown and their main advantages and disadvantages are explained; the Branch and Bound methods, considered as the best exact algorithms for solving this problem, are described. Subsequently, several heuristic methods, especially those that have been implemented for sequencing problems, are considered.

MSC: 90B35

Downloads

Download data is not yet available.
Abstract 1250 | PDF (Español) Downloads 4330 HTML (Español) Downloads 2988

References

[1]M. W. Schäffter, “Scheduling with forbidden sets,” Discrete Applied Mathematics, vol. 72, no. 1–2, pp. 155–166, Jan. 1997.

[2] J. Blazewicz, J. K. Lenstra, and K. Rinooy, “Scheduling subject to resource constraints: classification and complexity,” Discrete Applied Mathematics - DAM, vol. 5, no. 1, pp. 11–24, 1983.

[3] A. Mingozzi, V. Maniezzo, S. Ricciardelli, and L. Bianco, “An Exact Algorithm for the Resource Constrained Project Scheduling Problem Based on a New Mathematical Formulation,” Management Science, vol. 44, no. 5, pp. 714–729, 1995.

[4] P. Brucker, A. Drexl, R. Möhring, K. Neumann, and E. Pesch, “Resourceconstrained project scheduling: Notation, classification, models, and methods,” European Journal of Operational Research, vol. 112, no. 1, pp. 3–41, 1999.

[5] P. Brucker and S. Knust, “Lower bounds for resource-constrained project scheduling problems,” European Journal of Operational Research, vol. 149, no. 2, pp. 302–313, Sep. 2003.

[6] S. E. Elmaghraby, Activity Networks: Project Planning and Control by Network Models. John Wiley & Sons Inc, 1977.

[7] W. Herroelen, B. De Reyck, and E. Demeulemeester, “Resource-constrained project scheduling: A survey of recent developments,” Computers and Operations Research, vol. 25, no. 4, pp. 279–302, 1998.

[8] R. Kolisch and R. Padman, “An integrated survey of deterministic project scheduling,” Omega, vol. 29, no. 3, pp. 249–272, Jun. 2001.

[9] E. Demeulemeester and W. Herroelen, “A Branch-and-Bound Procedure for the Multiple Resource-Constrained Project Scheduling Problem,” Management Science, vol. 38, no. 12, pp. 1803–1818, Dec. 1992.

[10] P. Brucker, S. Knust, A. Schoo, and O. Thiele, “A branch and bound algorithm for the resource-constrained project scheduling problem,” European Journal of Operational Research, vol. 107, no. 2, pp. 272–288, Jun. 1998.

[11] E. W. Davis and G. E. Heidorn, “An Algorithm for Optimal Project Scheduling under Multiple Resource Constraints,” Management Science, vol. 17, no. 12, pp. B803–B816, 1971.

[12] A. L. Gutjahr and G. L. Nemhauser, “An Algorithm for the Line Balancing Problem,” Management
Science, vol. 11, no. 2, pp. 308–315, 1964.

[13] M. Fisher, “Optimal Solution of Scheduling Problems Using Lagrange Multipliers Part1,” Operations Research, vol. 21, no. 5, pp. 1114–1127, 1973.

[14] J. P. Stinson, E. W. Davis, and B. M. Khumawala, “Multiple Resource–Constrained Scheduling Using Branch and Bound,” A I I E Transactions, vol. 10, no. 3,
pp. 252–259, Sep. 1978.

[15] N. Christofides, R. Alvarez-Valdes, and J. M. Tamarit, “Project scheduling with resource constraints: A branch and bound approach,” European Journal of Operational Research, vol. 29, no. 3, pp. 262–273, 1987.

[16] J. H. Patterson, “A Comparison of Exact Approaches for Solving the Multiple Constrained Resource, Project Scheduling Problem,” Management Science, vol. 30, no. 7, pp. 854–867, 1984.

[17] R. Kolisch, A. Sprecher, and A. Drexl, “Characterization and generation of a general class of resource-constrained project scheduling problems: Easy and hard instances,” Research report No. 301, Institut für Betriebswirtschaftslehre, Christian-Albrechts-Univerität zu Kiel.Germany., 1992.

[18] R. Kolisch and A. Sprecher, “PSPLIB - A project scheduling library,” European Journal of Operational Research, vol. 96, pp. 205–216, 1996.

[19] 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, no. 2, pp. 394–407, Dec. 2000.

[20] H. Wang, T. Li, and D. Lin, “Efficient genetic algorithm for resource-constrained project scheduling problem,” Transactions of Tianjin University, vol. 16, no. 5, pp. 376–382, Oct. 2010.

[21] J. F. Gonçalves, M. Resende, and J. Mendes, “A biased random-key genetic algorithm with forward-backward improvement for the resource constrained project scheduling problem,” Journal of Heuristics, vol. 17, no. 5, pp. 1–20, 2010.

[22] X.-G. Wang, Y.-W. W. Bai, C.-L. L. Cai, and X. Yan, “Application of Resource-Constrained Project Scheduling with a Critical Chain Method on organizational Project Management,” in 2010 International Conference On Computer Design and Applications, 2010, vol. 2, pp. V2–51–V2–54.

[23] S. Elloumi and P. Fortemps, “A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem,” European Journal of Operational Research, vol. 205, no. 1, pp. 31–41, Aug. 2010.

[24] J. R. Montoya-Torres, E. Gutierrez-Franco, and C. Pirachicán-Mayorga, “Project scheduling with limited resources using a genetic algorithm,” International Journal of Project Management, vol. 28, no. 6, pp. 619–628, Aug. 2010.

[25] V. Valls, F. Ballestín, and S. Quintanilla, “A hybrid
genetic algorithm for the resource-constrained project scheduling problem,” European Journal of Operational Research, vol. 185, no. 2, pp. 495–508, Mar. 2008.

[26] L. Deng, V. Lin, and M. Chen, “Hybrid ant colony optimization for the resource-constrained project scheduling problem,” Journal of Systems Engineering and Electronics, vol. 21, no. 1, pp. 67–71, 2010.

[27] Z. Michalewicz and D. B. Fogel, How to Solve It: Modern Heuristics. Springer, 2000, p. 570.

[28] J. Nievergelt, “Exhaustive Search , Combinatorial Optimization and Enumeration : Exploring the Potential of Raww Computing Power,” Proceedings of the 27th Conference on Current Trends in Theory and Practice of Informatics, pp. 18–35, 2000.

[29] V. Valls, F. Ballestı́n, and S. Quintanilla, “Justification and RCPSP: A technique that pays,” European Journal of Operational Research, vol. 165, no. 2, pp. 375–386, Sep. 2005.

[30] R. Bellman, “Dynamic Programming,” Princeton University Press, Princeton, N. J., 1957.

[31] R. Martí, “Procedimientos Metaheurísticos en Optimización Combinatoria,” Departament d’Estadística i Investigació Operativa, Facultat de Matemàtiques. Universitat de València, vol. 1, pp. 1–60, 2003.

[32] J. B. Santana, C. C. Rodríguez, F. C. García López, M. García Torres, B. M. Batista, J. A. Moreno Pérez, and J. M. Moreno Vega, “Metaheurísticas: Una revisión actualizada.,” Universidad de La Laguna, España: Departamento de Estadística, Investigación Operativa y Computación, 2004.

[33] F. Glover and M. Laguna, “Tabu search,” Boston: Kluwer Academic Publishers, 1997.

[34] M. Palpant, C. Artigues, and P. Michelon, “LSSPER: Solving the Resource-Constrained Project Scheduling Problem with Large Neighbourhood Search,” Annals of Operations Research, vol. 131, no. 1–4, pp. 237–257, Oct. 2004.

[35] B. Pollack-Johnson, “Hybrid structures and improving forecasting and scheduling in project management,” Journal of Operations Management, vol. 12, no. 2, pp. 101–117, Feb. 1995.

[36] A. Sprecher, “Solving the RCPSP Efficiently at Modest Memory Requiriments,” Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel., vol. 425, p. 27, 1996.

[37] C. E. Bell and J. Han, “A new heuristic solution method in resource-constrained project scheduling,” Naval Research Logistics, vol. 38, no. 3, pp. 315–331, Jun. 1991.

[38] H. E. Mausser and S. R. Lawrence, “Exploiting Block Structure to Improve Resource-Constrained Project Schedules,” in Meta-Heuristics, I. H. Osman and J. P. Kelly, Eds. 1996, pp. 203–217.

[39] M. G. C. Resende and C. C. Ribeiro, “Greedy
randomized adaptive search procedures,” Handbook of Metaheuristics. Kluwer Academic Publishers., pp. 219–249, 2003.

[40] A. Schirmer, Project Scheduling with Scarce Resources. Models, Methods, and Applications. Verlag Dr. Kovac, 2000.

[41] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing.,” Science (New York, N.Y.), vol. 220, no. 4598, pp. 671–80, May 1983.

[42] C. Artigues, P. Michelon, and S. Reusser, “Insertion techniques for static and dynamic resource-constrained project scheduling,” European Journal of Operational Research, vol. 149, no. 2, pp. 249–267, Sep. 2003.

[43] T. Baar, P. Brucker, and S. Knust, “Tabu search algorithms and lower bounds for the resource-constrained project scheduling problem,” Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pp. 1–18, 1999.

[44] R. Klein, “Bidirectional planning: improving priority rule-based heuristics for scheduling resource-constrained projects,” European Journal of Operational Research, vol. 127, no. 3, pp. 619–638, Dec. 2000.

[45] H. J. Holland, “Adaptation in Natural and Artificial Systems,” Unversity of Michigand. Press, Ann Arbor, 1975.

[46] J. Lancaster and M. Ozbayrak, “Evolutionary algorithms applied to project scheduling problems—a survey of the state-of-the-art,” International Journal of Production Research, vol. 45, no. 2, pp. 425–450, Jan. 2007.

[47] S. Hartmann, “A self-adapting genetic algorithm for project scheduling under resource constraints,” Naval Research Logistics, vol. 49, no. 5, pp. 433–448, Aug. 2002.

[48] L. J. Fogel, A. J. Owens, and M. J. Walsh, Artificial Intelligence through Simulated Evolution. NY: John Wiley & Sons, 1966, p. 170.

[49] X. Yao, Y. Liu, and G. Lin, “Evolutionary Programming Made Faster,” Evolutionary Computation, IEEE Transactions on., vol. 3, no. 2, pp. 82–102, 1999.

[50] T. A. Feo and M. G. C. Resende, “A Probabilistic Heuristic for a Computationally Difficult Set Covering Problem,” Operations Research Letters, vol. 8, no. 2, pp. 67–71, 1989.

[51] F. Glover, “A Template for Scatter Search and Path Relinking,” Artificial Evolutions, Lecture Notes in Computer Science, vol. 1363, no. 1, pp. 15–53, 1998.

[52] M. Laguna and R. Marti, Scatter Search: Methodology and Implementations in C, Kluwer Aca. 2002.

[53] F. G. Ballestín, “Nuevos Métodos de Resolución del Problema de Secuenciación de Proyectos con Recursos Limitados,” Universidat de Valencia, 2002.

[54] D. Debels, B. De Reyck, R. Leus, and M. Vanhoucke, “A hybrid scatter search/electromagnetism meta-heuristic for project scheduling,” European Journal of Operational Research, vol. 169, no. 2, pp. 638–653, Mar. 2006.

[55] M. Dorigo, “Optimization, Learning and Natural Algorithms,” Politecnico di Milano, Italy, in Italian, 1992.
[56] C. Blum, “Ant colony optimization: Introduction and recent trends,” Physics of Life Reviews, vol. 2, no. 4, pp. 353–373, Dec. 2005.

[57] D. Merkle, M. Middendorf, and H. Schmeck, “Ant colony optimization for resource-constrained project scheduling,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 4, pp. 333–346, Aug. 2002.

[58] P. Larrañaga and J. A. Lozano, “Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation,” Genetic Algorithms and Evolutionary Computation, vol. 2, p. 416, 2002.

[59] P. Larrañaga, J. A. Lozano, and H. Mühlenbein, “Algoritmos de Estimación de Distribuciones en Problemas de Optimización Combinatoria,” Inteligencia Artificial. Revista Iberoamericana de Inteligencia Artificial, vol. 7, no. 19, pp. 149–168, 2003.

[60] E. G. Talbi, “A Taxonomy of Hybrid Metaheuristics,” Journal of Heuristics, Kluwer Academic Publishers., vol. 8, no. 1, pp. 541–564, 2002.

[61] P. Tormos and A. Lova, “A Competitive Heuristic Solution Technique for Resource-Constrained Project Scheduling,” Annals of Operations Research, vol. 102, no. 1–4, pp. 65–81, 2001.

[62] R. Kolisch, “Serial and parallel resource constrained project scheduling methods revisted: Theory and computation,” European Journal of Operational Research, vol. 90, no. 1, pp. 320–333, Apr. 1995.

[63] S. E. Elmaghraby and W. S. Herroelen, “On the measurement of complexity in activity networks,” European Journal of Operational Research, vol. 5, no. 4, pp. 223–234, 1980.

[64] L. F. Moreno, “DESARROLLO DE UNA HERRAMIENTA ANALiTICA¬ HEURíSTICA PARA RESOLVER EL PROBLEMA DE LA AMACiÓN DE TAREAS (SCHEDULING),” Informe de año Sabático, Universidad Nacional de Colombia - Sede Medellín., 2005.

[65] B. De Reyck and W. Herroelen, “On the use of the complexity index as a measure of complexity in activity networks,” European Journal of Operational Research, vol. 91, no. 2, pp. 347–366, Jun. 1996.

[66] W. W. Bein, J. Kamburowski, and M. F. M. Stallmann, “Optimal reduction of two-terminal directed acyclic graphs,” SIAM Journal on Computing, vol. 21, no. 6, pp. 1112–1129, 1992.

[67] M. Cervantes, “Nuevos Métodos Meta Heurísticos para la Asignación Eficiente , Optimizada y Robusta de Recursos Limitados,” Universidad Politécnica de Valencia, 2009.