Hybrid Variable Neighborhood and Simulated Annealing Heuristic Algorithm to Solve RCPSP

Juan Carlos Rivera; Ana Josefina Celín

doi:10.17533/udea.redin.14675

Autores/as

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

DOI:

https://doi.org/10.17533/udea.redin.14675

Palabras clave:

algoritmos heurísticos, búsqueda en vecindarios variables (VNS), justificación, RCPSP, programación de producción, recocido simulado

Resumen

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.

|Resumen

= 147 veces | PDF

= 69 veces|

Descargas

Los datos de descargas todavía no están disponibles.

Biografía del autor/a

Juan Carlos Rivera, Universidad Eafit

Departamento de Ciencias Básicas.

Ana Josefina Celín, Universidad de Antioquia

Facultad de Ingeniería.

Citas

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. DOI: https://doi.org/10.1287/mnsc.44.5.714

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. DOI: https://doi.org/10.1016/j.ejor.2005.06.014

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. DOI: https://doi.org/10.1016/j.ejor.2004.04.008

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. DOI: https://doi.org/10.1016/j.amc.2005.11.160

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. DOI: https://doi.org/10.1016/0166-218X(83)90012-4

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. DOI: https://doi.org/10.1109/TEVC.2002.802450

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. DOI: https://doi.org/10.1287/opre.18.2.263

S. Gorenstein. “An Algorithm for Project Sequencing with Resource Constraints”. Operations Research. Vol. 20. 1972. pp. 835-850. DOI: https://doi.org/10.1287/opre.20.4.835

M. Fisher. “Optimal Solution of Scheduling Problems Using Lagrange Multipliers. Part I”. Operations Research. Vol. 21. 1973. pp. 1114-1127. DOI: https://doi.org/10.1287/opre.21.5.1114

J. Patterson, W. Huber. “A Horizon-Varying, ZEROOne Approach to Project Scheduling”. Management Science. Vol. 20. 1974. pp. 990-998. DOI: https://doi.org/10.1287/mnsc.20.6.990

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

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. DOI: https://doi.org/10.1287/mnsc.24.11.1163

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. DOI: https://doi.org/10.1287/mnsc.38.12.1803

W. Simpson, J. Patterson. “A multiple-tree search procedure for the resource-constrained project scheduling problem”. EJOR. Vol. 89. 1996. pp. 525-542. DOI: https://doi.org/10.1016/0377-2217(94)00247-9

E. Demeulemeester, W. Herroelen. “New benchmark results for the resource-constrained project scheduling problem”. Management Science. Vol. 43. 1997. pp. 1485-1492. DOI: https://doi.org/10.1287/mnsc.43.11.1485

A. Sprecher, S. Hartmann, A. Drexl. “An exact algorithm for project scheduling with multiple modes”. OR Spektrum. Vol. 19. 1997. pp. 195 - 203. DOI: https://doi.org/10.1007/BF01545587

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. DOI: https://doi.org/10.1016/S0377-2217(97)00335-4

A. Sprecher. “Scheduling resource-constrained projects competitively at modest resource requirements”. Management Science. Vol. 46. 2000. pp. 710-723. DOI: https://doi.org/10.1287/mnsc.46.5.710.12044

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. DOI: https://doi.org/10.1016/j.ejor.2006.09.052

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. DOI: https://doi.org/10.1007/s11227-007-0158-9

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. DOI: https://doi.org/10.1126/science.220.4598.671

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. DOI: https://doi.org/10.1063/1.1699114

L. Moreno, J. Rivera, J. Diaz, G. Peña. “Análisis comparativo entre dos algoritmos heurísticos para resolver el problema de planeación de tareas con restricción de recursos (RCPSP)”. Dyna. Vol. 74. 2007. pp. 171-183.

K. Bouleimen, H. Lecocq. “A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multi mode version”. European Journal of Operational Research. Vol. 149. 2003. pp. 268-281. DOI: https://doi.org/10.1016/S0377-2217(02)00761-0

J. Cho, Y. Kim. “A simulated annealing algorithm for resource constrained project scheduling problems”. Journal of the Operational Research Society. Vol.48. 1997. pp. 736-744. DOI: https://doi.org/10.1038/sj.jors.2600416

F. Boctor. “Resource-constrained project scheduling by simulated annealing”. International Journal of Production Research. Vol. 34. 1996. pp. 2335-2351. DOI: https://doi.org/10.1080/00207549608905028

J. Lee, Y. Kim. “Search heuristics for Resource Constrained Project Scheduling”. LG-EDS Corporation y Korea Advanced Institute of Science and Technology. Journal of the Operational Research Society. Vol. 47. 1996. pp. 678-689. DOI: https://doi.org/10.1057/jors.1996.79

C. Koulamas, S. Anthony, R. Jean. “A survey of simulated annealing applications to operations research problems”. Omega. Vol. 22. 1994. pp. 41-56. DOI: https://doi.org/10.1016/0305-0483(94)90006-X

P. Hansen, N. Mladenovic. “Variable Neighborhood Search”. Search Methodologies. Introductory tutorials in optimization and decision support techniques. Ed. Springer. New York. 2005. pp. 221-238.

K. Fleszar, K. Hindi. “Solving the resource-constrained project scheduling problem by a variable neighbourhood search”. European Journal of Operational Research. Vol. 155. 2004. pp. 402-413. DOI: https://doi.org/10.1016/S0377-2217(02)00884-6

J. Wiest. “Some properties of schedules for large projects with limited resources”. Operations Research. Vol. 12. 1964. pp. 395-418. DOI: https://doi.org/10.1287/opre.12.3.395

D. Debels, B. De Reyck, R. Leus, M. Vanhoucke. “A hybrid scatter search / Electromagnetism meta–heuristic for project scheduling”. European Journal of Operational Research. Vol. 169. 2006. pp. 638-653. DOI: https://doi.org/10.1016/j.ejor.2004.08.020

E. Buffa, S. Edwood S. Sarin, K. Rakesh. Administración de la producción y de las operaciones. Ed. Limusa. México D. F. 1992. pp. 381-406.

T. Baar, P. Brucker, S. Knust. “Tabu-Search Algorithms and lower bounds for the Resource-Constrained Project Scheduling Problem”. In: S. Voss, S. Martello, I. Osman, C. Roucairol. (editors) Meta-heuristics: Advances and trends in local search paradigms for optimization. Ed. Kluwer Academic Publishers. Boston. 1998. pp. 1-18. DOI: https://doi.org/10.1007/978-1-4615-5775-3_1

J. Stinson, E. Davis, B. Khumawala. “Multiple Resource-Constrained Scheduling Using Branch and Bound”. AIIE Transactions. Vol. 10. 1978. pp. 252.259. DOI: https://doi.org/10.1080/05695557808975212

R. Kolisch, C. Schwindt, A. Sprecher. “Benchmark instances for project scheduling problems”. Project Scheduling – Recent Models, Algorithms and Applications. J. Weglarz (editor). Kluwer Academic Publishers. Boston. 1999. pp. 197-212. DOI: https://doi.org/10.1007/978-1-4615-5533-9_9

R. Kolisch, R. Hartmann. “Experimental Investigation of Heuristics for Resource-Constrained Project Scheduling: An Update”. European Journal of Operational Research. Vol. 174. 2006. pp. 23-37. DOI: https://doi.org/10.1016/j.ejor.2005.01.065