Algoritmo heurístico híbrido con múltiples vecindarios y recocido simulado para resolver el RCPSP

  • Juan Carlos Rivera Universidad Eafit
  • Ana Josefina Celín Universidad de Antioquia

Abstract

En este artículo se presenta un algoritmo heurístico híbrido para resolver el Problema de Programación de Proyectos con Recursos Limitados (RCPSP). El algoritmo diseñado combina elementos de Recocido Simulado y Búsqueda en Múltiples Vecindarios. Adicionalmente, utiliza el método denominado Justificación, el cual es un método diseñado específicamente para el RCPSP. Para evaluar el desempeño del algoritmo se realizó un análisis estadístico para el ajuste de parámetros. Los resultados se comparan con los reportados en la literatura científica.
|Abstract
= 20 veces | PDF (ESPAÑOL (ESPAÑA))
= 18 veces|

Downloads

Download data is not yet available.

References

A. Mingozzi, V. Maniezzo, S. Ricciardelli, L. Bianco. “An exact Algorithm for the Resource Constrained Project Scheduling Problem Based on a New Mathematical Formulation”. Management Science. Vol. 44. 1998. pp. 714-729.

L. Tseng, S. Chen. “A hybrid metaheuristic for the resource-constrained project scheduling problem”. European Journal of Operational Research. Vol. 175. 2006. pp. 707-721.

V. Valls, F. Ballestín, S. Quintanilla. “Justification and RCPSP: a technique that pays European Journal of Operational Research. Vol. 165. 2005. pp. 375-386.

B. Abbasi, S. Shadrokh, J. Arkat. “Bi-objective resource-constrained project scheduling with robustness and makespan criteria”. Applied mathematics and computation. Vol. 180. 2006. pp. 146-152.

J. Blazewicz, J. Lenstra, A. Rinnooy Kan. “Scheduling Projects Subject to Resource Constraints: Classification and Complexity”. Discrete Applied Mathematics. Vol. 5. 1983. pp. 11-24.

D. Merkle, M. Middendorf, H. Schmeck. “Ant colony optimization for resource-constrained project scheduling”. IEEE Transactions on Evolutionary Computation. Vol. 6. 2002. pp. 333-346.

E. Balas. “Project Scheduling with Resource Constraints”. In: E. M. L. Beale (editor). Application of Mathematical Programming Techniques. Ed. Elsevier. New York. 1970. pp. 187-200.

L. Schrage. “Solving Resource-Constrained Network problems by Implicit Enumeration – Non-preemptive Case”. Operations Research. Vol. 18. 1971. pp. 225- 235.

S. Gorenstein. “An Algorithm for Project Sequencing with Resource Constraints”. Operations Research. Vol. 20. 1972. pp. 835-850.

M. Fisher. “Optimal Solution of Scheduling Problems Using Lagrange Multipliers. Part I”. Operations Research. Vol. 21. 1973. pp. 1114-1127.

J. Patterson, W. Huber. “A Horizon-Varying, ZEROOne Approach to Project Scheduling”. Management Science. Vol. 20. 1974. pp. 990-998.

J. Patterson, G. Roth. “Scheduling a Project under Multiple Resource Constraints: a Zero-One Programming Approach”. AIIE Transactions. Vol. 8. 1976. pp. 449-455.

F. Talbot, J. Patterson. “An Efficient integer programming Algorithm with Network Cuts for Solving Resource-Constrained Scheduling problems”. Management Science. Vol. 24. 1978. pp. 1163-1174.

E. Demeulemeester, W. Herroelen. “A Branch and Bound Procedure for the Multiple Resource- Constrained project Scheduling Problem”. Management Science. Vol. 38. 1992. pp. 1803-1818.

W. Simpson, J. Patterson. “A multiple-tree search procedure for the resource-constrained project scheduling problem”. EJOR. Vol. 89. 1996. pp. 525-542.

E. Demeulemeester, W. Herroelen. “New benchmark results for the resource-constrained project scheduling problem”. Management Science. Vol. 43. 1997. pp. 1485-1492.

A. Sprecher, S. Hartmann, A. Drexl. “An exact algorithm for project scheduling with multiple modes”. OR Spektrum. Vol. 19. 1997. pp. 195 - 203.

P. Brucker, S. Knust, A. Schoo, O. Thiele. “A branch & bound algorithm for the resource-constrained project scheduling problem”. European Journal of Operacional Research. Vol. 107. 1998. pp. 272-288.

A. Sprecher. “Scheduling resource-constrained projects competitively at modest resource requirements”. Management Science. Vol. 46. 2000. pp. 710-723.

J. Damay, A. Quilliot, E. Sanlaville. “Linear programming based algorithms for preemptive and non-preemptive RCPSP”. European Journal of Operational Research. Vol. 182. 2007. pp. 1012-1022.

M. Sabzehparvar, S. Seyed Hosseini. “A mathematical model for the multi-mode resource-constrained project scheduling problem with mode dependent time lags”. The Journal of Supercomputing. Vol. 44. 2008. pp. 257-273.

R. Martí. “Procedimientos metaheurísticos en optimización combinatoria”. Matemátiques. Vol. 1. 2003. pp. 3-62.

Z. Michalewicz, D. Fogel. How to solve it: modern heuristics. Ed. Springer. New York. 2002. pp. 117-125.

S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi. “Optimization by simulated annealing”. Science, Vol. 220. 1983. pp. 671-680.

N. Metropolis, A. Rosenbluth, A. Teller, E. Teller. “Equations of state calculations by fast computing machines”. The journal of chemical physics. Vol. 21. 1953. 1087-1092.

Published
2013-02-28
How to Cite
Rivera J. C., & Celín A. J. (2013). Algoritmo heurístico híbrido con múltiples vecindarios y recocido simulado para resolver el RCPSP. Revista Facultad De Ingeniería Universidad De Antioquia, (56), 256-267. Retrieved from https://revistas.udea.edu.co/index.php/ingenieria/article/view/14675