A Two-Phase Algorithm for a Resource Constrained Project Scheduling Problem with Discounted Cash Flows
DOI:
https://doi.org/10.7494/dmms.2013.7.1.51Keywords:
resource-constrained project scheduling, discounted cash flows, milestones, heuristicsAbstract
This paper presents a Resource-Constrained Project Scheduling Problem (RCPSP) settled by contractual milestones. The criterion analysed here is the maximisation of aggregate discounted cash flows from the contractor’s perspective, known as an RCPSP problem with Discounted Cash Flows (RCPSPDCF). The cash flows analysed here cover the contractor’s cash outflows (negative cash flows), related to the commencement of individual activities, and cash inflows (positive cash flows) after the fulfilment of individual milestones. The authors propose a two-phase algorithm for solving the problem defined. In the first phase, the simulated annealing metaheuristics is used, designed to identify a forward schedule with as high total DCF as possible. In the second phase, the best first-phase schedule is improved by right shifts of activities. To this end, the procedure which iteratively shifts tasks by one unit is applied, with a view to maximising the objective function. Activity shifts take into consideration precedence and resource constraints, and they are performed for a specified resource allocation to activities. This paper also includes an analysis of the problem for a sample project. The results of computational experiments are then analysed. The experiments were run with the use of standard test problems from the Project Scheduling Problem LIBrary (PSPLIB), with additionally defined cash flows and contractual milestones.
References
Baroum S.M. & Patterson J.H. (1996). The development of cash flow weight procedures for maximizing the net present value of a project. Journal of Operations Management, 14(3), pp. 209–227. DOI: http://doi.org/10.1016/0272-6963(96)00005-8.
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: http://doi.org/10.1016/0166-218X(83)90012-4.
Boctor F.F. (1996). Resource-constrained project scheduling by simulated annealing. International Journal of Production Research, 34(8), pp. 2335–2351. DOI: http://doi.org/10.1080/00207549608905028.
Bouleimen K. & Lecocq H. (2003). A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. European Journal of Operational Research, 149(2), pp. 268–281. DOI: http://doi.org/10.1016/S0377-2217(02)00761-0.
Deblaere F., Demeulemeester E.L., Herroelen W.S. & Van de Vonder S. (2006). Proactive Resource Allocation Heuristics for Robust Project Scheduling. Research Report KBI 0608. Leuven: Katholieke Universiteit Leuven.
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: http://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: http://doi.org/10.1016/S0377-2217(99)00485-3.
He Z. & Xu Y. (2008). Multi-mode project payment scheduling problems with bonus–penalty structure. European Journal of Operational Research, 189(3), pp. 1191–1207. DOI: http://doi.org/10.1016/j.ejor.2006.07.053.
He Z., Wang N., Jia T. & Xu Y. (2009). Simulated annealing and tabu search for multi-mode project payment scheduling. European Journal of Operational Research, 198(3), pp. 688–696. DOI: http://doi.org/10.1016/j.ejor.2008.10.005.
He Z., Liu R. & Jia T. (2012). Metaheuristics for multi-mode capital-constrained project payment scheduling. European Journal of Operational Research, 223(3), pp. 605–613. DOI: http://doi.org/10.1016/j.ejor.2012.07.014.
Herroelen W.S., Van Dommelen P. & Demeulemeester E.L. (1997). Project network models with discounted cash flows: A guided tour through recent developments. European Journal of Operational Research, 100(1), pp. 97–121. DOI: http://doi.org/10.1016/S0377-2217(96)00112-9.
Icmeli O. & Erengüç S.S. (1996). The resource constrained time/cost tradeoff project scheduling problem with discounted cash flows. Journal of Operations Management, 14(3), pp. 255–275. DOI: http://doi.org/10.1016/0272-6963(95)00025-9.
Kimms A. (2001). Maximizing the net present value of a project under resource constraints using a Lagrangian relaxation based heuristic with tight upper bounds. Annals of Operations Research, 102, pp. 221–236. DOI: http://doi.org/10.1023/A:1010962300979.
Kirkpatrick S., Gelatt C.D. Jr. & Vecchi M.P. (1983). Optimization by simulated annealing. Science, 220(4598), pp. 671–680. DOI: http://doi.org/10.1126/science.220.4598.671.
Klimek M. (2010). Predyktywno-reaktywne harmonogramowanie produkcji z ograniczoną dostępnością zasobów [PhD Dissertation]. Kraków: AGH University of Science and Technology.
Klimek M. & Łebkowski P. (2011). Resource allocation for robust project scheduling. Bulletin of the Polish Academy of Sciences: Technical Sciences, 59(1), pp. 51–55. DOI: http://doi.org/10.2478/v10175-011-0008-z.
Kolisch R. (1996). Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. European Journal of Operational Research, 90(2), pp. 320–333. DOI: http://doi.org/10.1016/0377-2217(95)00357-6.
Kolisch R. & Padman R. (2001). An integrated survey of deterministic project scheduling. Omega, 29(3), pp. 249–272. DOI: http://doi.org/10.1016/S0305-0483(00)00046-3.
Kolisch R. & Sprecher A. (1997). PSPLIB – A project scheduling library. European Journal of Operational Research, 96(1), pp. 205–216. DOI: http://doi.org/10.1016/S0377-2217(96)00170-1.
Leus R. (2003). The Generation of Stable Project Plans [PhD Dissertation]. Leuven: Katholieke Universiteit Leuven.
Mika M., Waligóra G. & Węglarz J. (2005). Simulated annealing and tabu search for multi-mode resource-constrained project scheduling with positive discounted cash flows and different payment models. European Journal of Operational Research, 164(3), pp. 639–668. DOI: http://doi.org/10.1016/j.ejor.2003.10.053.
Pinder J.P. & Marucheck A.S. (1996). Using discounted cash flow heuristics to improve project net present value. Journal of Operations Management, 14(3), pp. 229–240. DOI: http://doi.org/10.1016/0272-6963(96)00003-4.
Policella N. (2005). Scheduling with Uncertainty: A Proactive Approach Using Partial Order Schedules [PhD Dissertation]. Rome: Sapienza University of Rome.
Policella N., Oddi A., Smith S.F. & Cesta A. (2004). Generating robust partial order schedules. In: Wallace M. (Ed.), Principles and Practice of Constraint Programming – CP 2004. Lecture Notes in Computer Science, 3258, pp. 496–511. Berlin–Heidelberg: Springer. DOI: http://doi.org/10.1007/978-3-540-30201-8_37.
Russell A.H. (1970). Cash flows in networks. Management Science, 16(5), pp. 357–373. DOI: http://doi.org/10.1287/mnsc.16.5.357.
Selle T. & Zimmermann J. (2003). A bidirectional heuristic for maximizing the net present value of large-scale projects subject to limited resources. Naval Research Logistics, 50(2), pp. 130–148. DOI: http://doi.org/10.1002/nav.10052.
Ulusoy G. & Özdamar L. (1995). A heuristic scheduling algorithm for improving the duration and net present value of a project. International Journal of Operations & Production Management, 15(1), pp. 89–98. DOI: http://doi.org/10.1108/01443579510077241.
Ulusoy G., Sivrikaya-Şerifoğlu F. & Şahin Ş. (2001). Four payment models for the multi-mode resource constrained project scheduling problem with discounted cash flows. Annals of Operations Research, 102, pp. 237–261. DOI: http://doi.org/10.1023/A:1010914417817.
Vanhoucke M. (2010). A scatter search procedure for maximising the net present value of a resource-constrained project with fixed activity cash flows. International Journal of Production Research, 48(7), pp. 1983–2001. DOI: http://doi.org/10.1080/00207540802010781.
Vanhoucke M., Demeulemeester E. & Herroelen W. (2001). Maximizing the net present value of a project with linear time-dependent cash flows. International Journal of Production Research, 39(14), pp. 3159–3181. DOI: http://doi.org/10.1080/00207540110056919.
Węglarz J. (Ed.). (1999). Project Scheduling: Recent Models, Algorithms and Applications. Boston, MA: Springer. DOI: http://doi.org/10.1007/978-1-4615-5533-9.
