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 minimisation criterion. To solve the problem, the authors propose insertion algorithms which generate schedules with use of forward serial and parallel decoding procedures. Schedules are improved with the use of the double justification by 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., Kan A. R., 1983. Scheduling subject to resource constraints classification and complexity, Discrete Applied Mathematics, 5, pp. 11-24.
Brucker P., Drexl A., Mohring R., Neumann K., Pesch E. 1999. Resource-constrained project scheduling: Notation, classification, models, and methods, European Journal of Operational Research, 112(1), pp. 3-41.
Demeulemeester E., Herroelen W., 1992. A branch-and-bound procedure for the multiple resource-constrained project scheduling problem, Management Science, 38, pp. 1803–1818.
Goncalves J., Resende M., Mendes J., 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.
Hartmann S., Briskorn D., 2012. A Survey of Variants and Extensions of the Resource-Constrained Project Scheduling Problem, European Journal of Operational Research, 207(1), pp. 1-14.
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, pp. 394-407.
Józefowska J., Węglarz J. (eds.), 2006. Perspectives in modern project scheduling, Springer, Berlin.
Klimek M., Predyktywno-reaktywne harmonogramowanie produkcji z ograniczoną dostępnością zasobów, Praca doktorska, AGH Kraków [Predictive-Reactive Resource Constrained Production Scheduling, Ph.D. Dissertation, AGH University of Science and Technology of Kraków], 2010. (in Polish).
Klimek M., Łebkowski P., 2010. Algorytmy wstawień dla zagadnienia harmonogramowania projektu ze zdefiniowanymi kamieniami milowym [Insertion Algorithms for Scheduling Projects with Predefined Milestones], [W:] Komputerowo zintegrowane zarządzanie, T. 1, red. Ryszard Knosala [[in:] Computer Integrated Management, Vol. 1, Ryszard Knosala ed.], Opole, Oficyna Wydawnicza PTZP, pp. 676685 (in Polish).
Kolisch R., 1996a. Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation, European Journal of Operational Research, 90, pp. 320-333.
Kolisch R., 1996b. Efficient priority rules for the resource-constrained project scheduling problem, Journal of Operations Management, 14, pp. 179-192.
Kolisch R., Hartmann S., 2006. Experimental Investigation of Heuristics for Resource-Constrained Project Scheduling: An Update, European Journal of Operational Research, 74(1), pp. 23–37.
Kolisch R., Padman R., 2001. An integrated survey of deterministic project scheduling, OMEGA, 29, pp. 249-272.
Kolisch R., Sprecher A., 1997. PSPLIB – a project scheduling library, European Journal of Operational Research, 96, pp. 205–216.
Nawaz M., Enscore E., Ham I., 1983. A heuristic algorithm for the m machine, n-job flow-shop sequencing problem, OMEGA, 11, pp. 91-95.
Tormos P., Lova A., 2001. A competitive heuristic solution technique for resource-constrained project scheduling, Annals of Operations Research, 102, pp. 65–81.
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.
Valls V., Ballestin F., Quintanilla S., 2005. Justification and RCPSP: a technique that pays, European Journal of Operational Research, 165(2), pp. 375-386.
Valls V., Ballestin F., Quintanilla S., 2006. Justification technique generalisations, In: Józefowska J., and Węglarz J. (eds.): Perspectives in Modern Project Scheduling, Springer, Berlin, pp. 205-223.
Valls V., Ballestin F., Quintanilla S., 2008. A Hybrid Genetic Algorithm for the Rcpsp, European Journal of Operational Research, 185(2), pp. 495–508.
Woo D.S., Yim H.S., 1998. A heuristic algorithm for mean flowtime objective in flowshop scheduling, Computers and Operations Research, 25, pp. 175-182.
Downloads
Published
How to Cite
Issue
Section
License
Remeber to prepeare, sign and scan copyright statement
The content of the journal is freely available according to the Creative Commons License Attribution 4.0 International (CC BY 4.0)
Accepted 2017-04-04
Published 2017-12-05
