A Two-Phase Algorithm for a Resource Constrained Project Scheduling Problem with Discounted Cash Flows

Marcin Klimek, Piotr Łebkowski


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.


resource-constrained project scheduling, discounted cash flows, milestones, heuristics

Full Text:



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), 209-27.

Błażewicz J., Lenstra J., Kan A. R., 1983. Scheduling subject to resource constraints – classification and complexity. Discrete Applied Mathematics, 5, 11-24.

Boctor F.F., 1996. Resource-constrained project scheduling by simulated annealing. International Journal of Operational Research, 34(8), 2335-2351.

Bouleimen K., Lecocq H., 2003. A new efficient simulated annealing algorithm for the resource constrained project scheduling problem and its multiple version. European Journal of Operational Research, 149, 268-281.

Deblaere F., Demeulemeester E.L., Herroelen W.S., Van De Vonder S., 2006. Proactive resource allocation heuristics for robust project scheduling. Working Paper KBI_0608, Leuven.

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), 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, 2000, 394-407.

He Z. W., Xu Y., 2008. Multi-mode project payment scheduling problems with bonus penalty structure. European Journal of Operational Research, 189, 1191-1207.

Herroelen W., Reyck B. D., Demeulemeester E., 1997. Project network models with discounted cash flows: A guided tour through recent developments. European Journal of Operational Research, 100, 97-121.

Kimms A., 2001. Maximizing the net present value of a project using a Lagrangian relaxation based heuristic with tight upper bounds. Annals of Operations Research, 102, 221-236.

Kirkpatrick S., Gelatt C.D., Vecchi M.P., 1983. Optimization by simulated annealing, Science, 220, 671-680.

Klimek M., 2010. Predyktywno-reaktywne harmonogramowanie produkcji z ograniczoną dostępnością zasobów (Predictive-Reactive Scheduling of Production with Limited Availability of resources). Ph.D. thesis at AGH, Kraków, Poland.

Klimek M., Łebkowski P., 2010. Resource allocation for robust project scheduling. Bulletin of the Polish Academy of Sciences Technical Sciences, Vol. 59, No. 1, 51-55.

Kolisch R., 1996. Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. European Journal of Operational Research, 90, 320-333.

Kolisch R., Padman R., 2001. An integrated survey of deterministic project scheduling. OMEGA The International Journal of Management Science, 29, 249-272.

Kolisch R., Sprecher A., 1997. PSPLIB – a project scheduling library. European Journal of Operational Research, 96, 205-216.

Leus R., 2003. The generation of stable project plans. PhD thesis at K.U.Leuven, Belgium.

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), 639-668.

Policella N., Oddi A., Smith S., Cesta A., 2004. Generating robust partial order schedules, In Proceedings of CP2004, Toronto, Canada.

Policella N., 2005. Scheduling with Uncertainty – A Proactive Approach using Partial Order Schedules. Ph.D. thesis at La Sapienza Universita, Rome.

Russell A.H., 1970. Cash flows in networks. Management Science, 16, 357-373.

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, 130-148.

Ulusoy G., Özdamar L., 1995. A heuristic scheduling algorithm for improving the duration and net present value of a project. International Journal of Operations and Production Management, 15, 89-98.

Ulusoy G., Sivrikaya-Serifoglu F., Sahin S., 2001. Four Payment Models for the Multi-Mode Resource Constrained Project Scheduling Problem with Discounted Cash Flows, Annals of Operations Research, 102, 237-261

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), 3159-3181.

Vanhoucke M., 2006. A scatter search procedure for maximizing the net present value of a resource-constrained project with fixed activity cash flows, Working Paper 2006/417, Gent, 1-23.

Węglarz J. (editor), 1999. Project Scheduling: Recent Models, Algorithms and Applications. Kluwer Academic Publishers.

DOI: https://doi.org/10.7494/dmms.2013.7.1.51


  • There are currently no refbacks.