Analytic and Heuristic Methodologies for Solving the Resource Constrained Project Scheduling Problem (RCPSP): a Review. Part 2
Main Article Content
Keywords
Task scheduling, metaheuristic methods, sequence generating schemes, exact method.
Abstract
This paper exposes and details 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 significant papers published in the academic literature on this topic is carried out. Initially, several metaheuristic methods of solution are shown, especially those that have been implemented for sequencing problems, and their main characteristics, advantages and disadvantages are explained. Furthermore, the so-called sequence generating schemes and the complexity indices most commonly used are presented. Finally, the test library PSPLIB, used in most academic papers related to such problems is considered.
MSC:90B35
Downloads
Download data is not yet available.
References
[1] 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.
[2] 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
[3] 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.
[4] F. Glover and M. Laguna, “Tabu search,” Boston: Kluwer Academic Publishers, 1997.
[5] 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.
[6] 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.
[7] 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.
[8] R. Klein, “Project scheduling with time-varying resource constraints,” International Journal of Production Research, vol. 38, no. 16, pp. 3937–3952, Nov. 2000.
[9] H. J. Holland, “Adaptation in Natural and Artificial Systems,” Unversity of Michigand. Press, Ann Arbor, 1975.
[10] 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.
[11] 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.
[12] V. Valls, F. Ballestin, and S. Quintanilla, “Justification and RCPSP: A technique that pays,” European Journal of Operational Research, vol. 165, no. 2, pp. 375–386, Sep. 2005.
[13] 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.
[14] L. J. Fogel, A. J. Owens, and M. J. Walsh, Artificial Intelligence through Simulated Evolution. NY: John Wiley & Sons, 1966.
[15] X. Yao, Y. Liu, and G. Lin, “Evolutionary Programming Made Faster,” Evolutionary Computation, IEEE Transactions on., vol. 3, no. 2, pp. 82–102, 1999.
[16] 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.
[17] M. G. C. Resende and C. C. Ribeiro, “Greedy randomized adaptive search procedures,” Handbook of Metaheuristics. Kluwer Academic Publishers., pp. 219–249, 2003.
[18] 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.
[19] M. Laguna and R. Marti, Scatter Search: Methodology and Implementations in C. Publishers Kluwer Academic, Springer US, Dec. 2002.
[20] F. G. Ballestin, “Nuevos Métodos de Resolución del Problema de Secuenciación de Proyectos con Recursos Limitados,” Ph.D. dissertation, Universidat de Valencia, 2002.
[21] 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.
[22] M. Dorigo, “Optimization, Learning and Natural Algorithms,” Ph.D. dissertation, Politecnico di Milano, Italy, in Italian, 1992.
[23] C. Blum, “Ant colony optimization: Introduction and recent trends,” Physics of Life Reviews, vol. 2, no. 4, pp. 353–373, Dec. 2005.
[24] 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.
[25] 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.
[26] 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.
[27] E. G. Talbi, “A Taxonomy of Hybrid Metaheuristics,” Journal of Heuristics, Kluwer Academic Publishers., vol. 8, no. 1, pp. 541–564, 2002.
[28] V. Valls, F. Ballestin, 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.
[29] 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.
[30] 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.
[31] L. F. Moreno, “Desarrollo de una herramienta analítica - heurística para resolver el problema de la programación de tareas (scheduling),” Informe de año Sabático, Universidad Nacional de Colombia - Sede Medellín., 2005.
[32] 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.
[33] 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.
[34] 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.
[35] 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.
[36] R. Kolisch and A. Sprecher, “PSPLIB - A project scheduling library,” European Journal of Operational Research, vol. 96, pp. 205–216, 1996.
[37] M. Cervantes, “Nuevos Métodos Meta Heurísticos para la Asignación Eficiente, Optimizada y Robusta de Recursos Limitados,” Tesis doctoral, Universidad Politécnica de Valencia, 2009.
[2] 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
[3] 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.
[4] F. Glover and M. Laguna, “Tabu search,” Boston: Kluwer Academic Publishers, 1997.
[5] 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.
[6] 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.
[7] 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.
[8] R. Klein, “Project scheduling with time-varying resource constraints,” International Journal of Production Research, vol. 38, no. 16, pp. 3937–3952, Nov. 2000.
[9] H. J. Holland, “Adaptation in Natural and Artificial Systems,” Unversity of Michigand. Press, Ann Arbor, 1975.
[10] 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.
[11] 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.
[12] V. Valls, F. Ballestin, and S. Quintanilla, “Justification and RCPSP: A technique that pays,” European Journal of Operational Research, vol. 165, no. 2, pp. 375–386, Sep. 2005.
[13] 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.
[14] L. J. Fogel, A. J. Owens, and M. J. Walsh, Artificial Intelligence through Simulated Evolution. NY: John Wiley & Sons, 1966.
[15] X. Yao, Y. Liu, and G. Lin, “Evolutionary Programming Made Faster,” Evolutionary Computation, IEEE Transactions on., vol. 3, no. 2, pp. 82–102, 1999.
[16] 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.
[17] M. G. C. Resende and C. C. Ribeiro, “Greedy randomized adaptive search procedures,” Handbook of Metaheuristics. Kluwer Academic Publishers., pp. 219–249, 2003.
[18] 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.
[19] M. Laguna and R. Marti, Scatter Search: Methodology and Implementations in C. Publishers Kluwer Academic, Springer US, Dec. 2002.
[20] F. G. Ballestin, “Nuevos Métodos de Resolución del Problema de Secuenciación de Proyectos con Recursos Limitados,” Ph.D. dissertation, Universidat de Valencia, 2002.
[21] 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.
[22] M. Dorigo, “Optimization, Learning and Natural Algorithms,” Ph.D. dissertation, Politecnico di Milano, Italy, in Italian, 1992.
[23] C. Blum, “Ant colony optimization: Introduction and recent trends,” Physics of Life Reviews, vol. 2, no. 4, pp. 353–373, Dec. 2005.
[24] 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.
[25] 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.
[26] 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.
[27] E. G. Talbi, “A Taxonomy of Hybrid Metaheuristics,” Journal of Heuristics, Kluwer Academic Publishers., vol. 8, no. 1, pp. 541–564, 2002.
[28] V. Valls, F. Ballestin, 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.
[29] 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.
[30] 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.
[31] L. F. Moreno, “Desarrollo de una herramienta analítica - heurística para resolver el problema de la programación de tareas (scheduling),” Informe de año Sabático, Universidad Nacional de Colombia - Sede Medellín., 2005.
[32] 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.
[33] 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.
[34] 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.
[35] 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.
[36] R. Kolisch and A. Sprecher, “PSPLIB - A project scheduling library,” European Journal of Operational Research, vol. 96, pp. 205–216, 1996.
[37] M. Cervantes, “Nuevos Métodos Meta Heurísticos para la Asignación Eficiente, Optimizada y Robusta de Recursos Limitados,” Tesis doctoral, Universidad Politécnica de Valencia, 2009.