Metodologías analíticas y heurísticas para la solución del Problema de Programación de Tareas con Recursos Restringidos (RCPSP): una revisión. Parte 2
Main Article Content
Keywords
programación de tareas, métodos metaheurísticos, esquemas generadores de secuencias, métodos exactos
Resumen
En este artículo se exponen y detallan los métodos de solución metaheurísticos más relevantes para el Problema de Programación de Tareas con Recursos Restringidos, RCPSP. Se realiza una revisión crítica del estado del arte, basada en el análisis de los trabajos más signicativos publicados en la literatura académica sobre el tema. Inicialmente se presentan diversos métodos metaheurísticos, especialmente aquellos que se han implementado para problemas de secuenciación, destacando sus principales características, así como sus ventajas y desventajas. Además, se presentan los llamados Esquemas Generadores de Secuencias y los índices de complejidad más comúnmente utilizados. Finalmente, se muestra la librería de prueba PSPLIB, usada en la mayoría de trabajos académicos.
MSC:90B35
Descargas
Los datos de descargas todavía no están disponibles.
Referencias
[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.