Robust Buffer Allocation for Scheduling of a Project with Predefined Milestones
DOI:
https://doi.org/10.7494/dmms.2009.3.2.49Keywords:
resource-constrained project scheduling, predictive-reactive scheduling, robust buffer allocation, milestonesAbstract
The paper discusses the problem of robust buffer allocation for Resource- Constrained Project Scheduling Problem (RCPSP) with predefined milestones, for which execution deadlines have been established. To solve the problem, an algorithm is proposed supporting insertion of unit time buffers, with the simultaneous maximisation of new metrics of arrangement robustness. The presented results of experimental research speak for usability of the solutions proposed. The effectiveness is studied with use of test tasks included in the Project Scheduling Problem Library (PSPLIB) with additionally specified project milestones.
References
Al-Fawzan M.A. & Haouari M. (2005). A bi-objective model for robust resource-constrained project scheduling. International Journal of Production Economics, 96(2), pp. 175–187. DOI: https://doi.org/10.1016/j.ijpe.2004.04.002.
Aytug H., Lawley M.A., McKay K., Mohan S. & Uzsoy R. (2005). Executing production schedules in the face of uncertainties: A review and some future directions. European Journal of Operational Research, 161(1), pp. 86–110. DOI: https://doi.org/10.1016/j.ejor.2003.08.027.
Goldratt E.M. (1997). Critical Chain. Great Barrington, MA: North River Press. ISBN: 978-0-88427-153-6.
Hall N.G. & Posner M.E. (2004). Sensitivity analysis for scheduling problems. Journal of Scheduling, 7(1), pp. 49–83. DOI: https://doi.org/10.1023/B:JOSH.0000013055.31639.f6.
Herroelen W. & Leus R. (2004). Robust and reactive project scheduling: A review and classification of procedures. International Journal of Production Research, 42(8), pp. 1599–1620. DOI: https://doi.org/10.1080/00207540310001638055.
Jensen M.T. (2001). Improving robustness and flexibility of tardiness and total flow-time job shops using robustness measures. Applied Soft Computing, 1(1), pp. 35–52. DOI: https://doi.org/10.1016/S1568-4946(01)00005-9.
Klimek M. & Łebkowski P. (2007). Predictive-reactive project scheduling. In: J. Duda (Ed.), Innovation Technologies in Economics and Innovative Management. Kraków: Uczelniane Wydawnictwa Naukowo-Dydaktyczne Akademii Górniczo-Hutniczej, pp. 198–206.
Klimek M. & Łebkowski P. (2008a). Miary odporności harmonogramów. In: R. Knosala (Ed.), Komputerowo Zintegrowane Zarządzanie, Vol. 1. Opole: Oficyna Wydawnicza Polskiego Towarzystwa Zarządzania Produkcją, pp. 569–577.
Klimek M. & Łebkowski P. (2008b). Algorytmy metaheurystyczne dla problemu harmonogramowania projektu z kamieniami milowymi. Zeszyty Naukowe Politechniki Śląskiej. Seria: Automatyka, 150, pp. 63–72.
Kobylański P. & Kuchta D. (2007). A note on the paper by M.A. Al-Fawzan and M. Haouari about a bi-objective problem for robust resource-constrained project scheduling. International Journal of Production Economics, 107(2), pp. 496–501. DOI: https://doi.org/10.1016/j.ijpe.2006.07.012.
Kolisch R. & Sprecher A. (1997). PSPLIB – A project scheduling library. European Journal of Operational Research, 96(1), pp. 205–216. DOI: https://doi.org/10.1016/S0377-2217(96)00170-1.
Lambrechts O., Demeulemeester E. & Herroelen W. (2008). Proactive and reactive strategies for resource-constrained project scheduling with uncertain resource availabilities. Journal of Scheduling, 11(2), pp. 121–136. DOI: https://doi.org/10.1007/s10951-007-0021-0.
Leus R. (2003). The Generation of Stable Project Plans: Complexity and Exact Algorithms [PhD thesis]. Leuven: Katholieke Universiteit Leuven.
Policella N., Oddi A., Smith S.F. & Cesta A. (2004). Generating robust partial order schedules. In: M. Wallace (Ed.), Principles and Practice of Constraint Programming – CP 2004. Lecture Notes in Computer Science, 3258. Berlin–Heidelberg: Springer, pp. 496–511. DOI: https://doi.org/10.1007/978-3-540-30201-8_37.
Policella N. (2005). Scheduling with Uncertainty: A Proactive Approach Using Partial Order Schedules [PhD thesis]. Rome: Università degli Studi di Roma “La Sapienza”. URL: https://hdl.handle.net/20.500.14242/99690.
Van de Vonder S., Demeulemeester E., Herroelen W. & Leus R. (2005). The use of buffers in project management: The trade-off between stability and makespan. International Journal of Production Economics, 97(2), pp. 227–240. DOI: https://doi.org/10.1016/j.ijpe.2004.08.004.
Van de Vonder S., Demeulemeester E., Herroelen W. & Leus R. (2006). The trade-off between stability and makespan in resource-constrained project scheduling. International Journal of Production Research, 44(2), pp. 215–236. DOI: https://doi.org/10.1080/00207540500140914.
Van de Vonder S. (2006). Proactive-Reactive Procedures for Robust Project Scheduling [PhD thesis]. Leuven: Katholieke Universiteit Leuven. URL: https://lirias.kuleuven.be/1833509.
Vieira G.E., Herrmann J.W. & Lin E. (2003). Rescheduling manufacturing systems: A framework of strategies, policies, and methods. Journal of Scheduling, 6(1), pp. 39–62. DOI: https://doi.org/10.1023/A:1022235519958.
