Insertion Algorithms with Justification for Solving the Resource-Constrained Project Scheduling
DOI:
https://doi.org/10.7494/dmms.2016.10.1-2.31Keywords:
insertion algorithms, resource-constrained project scheduling problem, makespan minimisation, justification, forward scheduling, priority rulesAbstract
The paper presents the resource-constrained project scheduling problem with the makespan minimization criterion. To solve the problem, the authors propose insertion algorithms that generate schedules with the use of forward serial and parallel decoding procedures. Schedules are improved with the use of the double justification by the extremes technique (first right and then left justification). The efficiency of the procedures proposed is tested on standard test problems from the PSPLIB library.
References
Błażewicz J., Lenstra J.K. & Rinnooy Kan A.H.G. (1983). Scheduling subject to resource constraints: Classification and complexity. Discrete Applied Mathematics, 5(1), pp. 11–24. DOI: https://doi.org/10.1016/0166-218X(83)90012-4.
Brucker P., Drexl A., Möhring R.H., Neumann K. & Pesch E. (1999). Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research, 112(1), pp. 3–41. DOI: https://doi.org/10.1016/S0377-2217(98)00204-5.
Demeulemeester E. & Herroelen W. (1992). A branch-and-bound procedure for the multiple resource-constrained project scheduling problem. Management Science, 38(12), pp. 1803–1818. DOI: https://doi.org/10.1287/mnsc.38.12.1803.
Gonçalves J.F., Resende M.G.C. & Mendes J.J.M. (2011). A biased random-key genetic algorithm with forward-backward improvement for the resource constrained project scheduling problem. Journal of Heuristics, 17(5), pp. 467–486. DOI: https://doi.org/10.1007/s10732-010-9142-2.
Hartmann S. & Briskorn D. (2010). A survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 207(1), pp. 1–14. DOI: https://doi.org/10.1016/j.ejor.2009.11.005.
Hartmann S. & Kolisch R. (2000). Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. European Journal of Operational Research, 127(2), pp. 394–407. DOI: https://doi.org/10.1016/S0377-2217(99)00485-3.
Józefowska J. & Węglarz J. (Eds.). (2006). Perspectives in Modern Project Scheduling. International Series in Operations Research & Management Science, 92. New York: Springer. DOI: https://doi.org/10.1007/978-0-387-33768-5.
Klimek M. & Łebkowski P. (2010). Algorytmy wstawień dla zagadnienia harmonogramowania projektu ze zdefiniowanymi kamieniami milowymi. In: Knosala R. (red.), Komputerowo zintegrowane zarządzanie, t. 1. Opole: Oficyna Wydawnicza Polskiego Towarzystwa Zarządzania Produkcją, pp. 676–685.
Kolisch R. (1996a). Efficient priority rules for the resource-constrained project scheduling problem. Journal of Operations Management, 14(3), pp. 179–192. DOI: https://doi.org/10.1016/0272-6963(95)00032-1.
Kolisch R. (1996b). Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. European Journal of Operational Research, 90(2), pp. 320–333. DOI: https://doi.org/10.1016/0377-2217(95)00357-6.
Kolisch R. & Hartmann S. (2006). Experimental investigation of heuristics for resource-constrained project scheduling: An update. European Journal of Operational Research, 174(1), pp. 23–37. DOI: https://doi.org/10.1016/j.ejor.2005.01.065.
Kolisch R. & Padman R. (2001). An integrated survey of deterministic project scheduling. Omega, 29(3), pp. 249–272. DOI: https://doi.org/10.1016/S0305-0483(00)00046-3.
Kolisch R. & Sprecher A. (1997). PSPLIB – A project scheduling problem library: OR Software – ORSEP Operations Research Software Exchange Program. European Journal of Operational Research, 96(1), pp. 205–216. DOI: https://doi.org/10.1016/S0377-2217(96)00170-1.
Nawaz M., Enscore E.E. Jr. & Ham I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), pp. 91–95. DOI: https://doi.org/10.1016/0305-0483(83)90088-9.
Tormos P. & Lova A. (2001). A competitive heuristic solution technique for resource-constrained project scheduling. Annals of Operations Research, 102, pp. 65–81. DOI: https://doi.org/10.1023/A:1010997814183.
Tormos P. & Lova A. (2003). An efficient multi-pass heuristic for project scheduling with constrained resources. International Journal of Production Research, 41(5), pp. 1071–1086. DOI: https://doi.org/10.1080/0020754021000033904.
Valls V., Ballestín F. & Quintanilla S. (2005). Justification and RCPSP: A technique that pays. European Journal of Operational Research, 165(2), pp. 375–386. DOI: https://doi.org/10.1016/j.ejor.2004.04.008.
Valls V., Ballestín F. & Quintanilla S. (2006). Justification technique generalizations. In: Józefowska J. & Węglarz J. (Eds.), Perspectives in Modern Project Scheduling. International Series in Operations Research & Management Science, 92. Boston: Springer, pp. 205–223. DOI: https://doi.org/10.1007/978-0-387-33768-5_8.
Valls V., Ballestín F. & Quintanilla S. (2008). A hybrid genetic algorithm for the resource-constrained project scheduling problem. European Journal of Operational Research, 185(2), pp. 495–508. DOI: https://doi.org/10.1016/j.ejor.2006.12.033.
Woo H.-S. & Yim D.-S. (1998). A heuristic algorithm for mean flowtime objective in flowshop scheduling. Computers & Operations Research, 25(3), pp. 175–182. DOI: https://doi.org/10.1016/S0305-0548(97)00050-6.
