Hybrid Variable Neighborhood and Simulated Annealing Heuristic Algorithm to Solve RCPSP

Authors

  • Juan Carlos Rivera EAFIT University
  • Ana Josefina Celín University of Antioquia

DOI:

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

Keywords:

simulated annealing, heuristic algorithms, variable neighborhoods search (VNS), justification, RCPSP, scheduling

Abstract

This paper presents a hybrid heuristic algorithm for solving the Resource Constrained Project Scheduling Problem (RCPSP). The algorithm designed combines elements of Simulated Annealing and Variable Neighborhood Search. Additionally, it uses the method called Justification, which is a method designed specifically for the RCPSP. To evaluate the performance of the algorithm, a statistical analysis for tuning the parameters has done. The results were compared with those reported in the scientific literature.

|Abstract
= 147 veces | PDF (ESPAÑOL (ESPAÑA))
= 69 veces|

Downloads

Download data is not yet available.

Author Biographies

Juan Carlos Rivera, EAFIT University

Department of Basic Sciences.

Ana Josefina Celín, University of Antioquia

Faculty of Engineering.

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. 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

Published

2013-02-28

How to Cite

Rivera, J. C., & Celín, A. J. (2013). Hybrid Variable Neighborhood and Simulated Annealing Heuristic Algorithm to Solve RCPSP. Revista Facultad De Ingeniería Universidad De Antioquia, (56), 255–267. https://doi.org/10.17533/udea.redin.14675