Net Present Value

The Net Present Value

Optimizing cash flows in project scheduling

Optimizing cash flows in project scheduling has been a topic for decades, and started at the OR&S scheduling group since 1996. On this webpage, you can find information on net present value optimization for unconstrained and resource-constrained project scheduling problems. You can download some of the executables (windows) for various types of project scheduling problem. The specific details of the algorithms for the different problems can be found in the references mentioned at the bottom of each subsection. Whenever new data is used in these research papers that is mentioned as freely available for download, a link is posted on this page.

1. The unconstrained project scheduling problem with discounted cash flows (max-npv problem)

This problem type schedules project activities with a known duration and cash flows (either positive or negative) within the pre-specified precedence relations such that the net present value is maximized. The technological precedence relations can be minimal precedence relations (the max-npv problem) or a mix of minimal and maximal relations (the max-npv-gpr problem, with gpr an abbreviation for generalized precedence relations).

Reference:

  • Vanhoucke, M., 2006, "An efficient hybrid search procedure for various optimization problems", Lecture Notes on Computer Science, 3906, 272-283.

2. The resource-constrained project scheduling problem with discounted cash flows (RCPSPDC)

The RCPSPCD schedules project activities with a known duration and cash flows (either positive or negative) within the pre-specified minimal precedence relations and within the presence of limited renewable resource constraints such that the net present value is maximized.

2.1 An exact branch-and-bound procedure (2001)

An exact branch-and-bound procedure has been developed and published in 2001 in Management Science. The procedure is based on the branching scheme of Icmeli et Erenguc (1996) and extended with the subset dominance rule originally proposed by De Reyck and Herroelen (1998). The problem instances of the Management Science paper contain 10, 20, 30, 40 and 50 activities and has been used in the Vanhoucke et al. (2001) reference below

Reference:

  • Vanhoucke, M., Demeulemeester, E. and Herroelen, W., 2001, "On maximizing the net present value of a project under renewable resource constraints", Management Science, 47, 1113-1121.

2.2 A heuristic scatter search procedure (2010)

In 2006, a scatter search procedure to solve the RCPSPDC has been developed in order to solve larger sized problem instances. The scatter search procedure has been tested on a new problem set containing networks with 25, 50, 75 and 100 instances. Each network has been extended with cash flows (both positive and negative) as displayed in the cash flow files and a project deadline. All data instances, an information file and solutions can be downloaded from this page. More information can be found in Vanhoucke (2010).

Reference:

  • Vanhoucke, M., 2010, “A scatter search heuristic for maximising the net present value of a resource-constrained project with fixed activity cash flows”, International Journal of Production Research, 48, 1983-2001.

2.3 A heuristic genetic algorithm (2015)

A new genetic algorithm to solve the RCPSPDC has been developed in order to get improved solutions compared to the scatter search method presented in 2.2. By using a fast search in subnetworks, the cash flows are moved forward or backward in time, leading to an improved net present value. A detailed comparison between the scatter search results and the new genetic algorithm results is made.

Reference

  • Leyman, P. and Vanhoucke, M., 2015, “A new scheduling technique for the resource–constrained project scheduling problem with discounted cash flows”, International Journal of Production Research, 53 (9), 2771-2786.

3. Other cash flow models

The cash flow model used in previous sections can be easily extended to various other models. Below you find an overview of models that have been used in our research. This part of the study is still under construction since new research is coming your way.

3.1 Progress payments

  • Vanhoucke, M., Demeulemeester, E. and Herroelen, W., 2003, “Progress payments in project scheduling problems”, European Journal of Operational Research, 148, 604-620.

3.2 Linear time-dependent cash flows

  • Vanhoucke, M., Demeulemeester, E. and Herroelen, W., 2001, "Maximizing the net present value of a project with linear time-dependent cash flows", International Journal of Production Research, 39, 3159-3181.

3.3 A comparison between three cash flow models

In a recent paper that is currently under submission, an evaluation is made of the single– and multi–mode resource–constrained project scheduling problem with discounted cash flows and three payment models. The first model is known as "Payments at activities’ completion times" and is identical to the RCPSPDC problem mentioned on this website. The second model is known as "progress payments" and is the same than the model of section 3.1, but now extended with renewable resources. A third model is an extension of the second model and is known as "Payments at event occurrences". 

Reference

  • Leyman, P. and Vanhoucke, M., 2015, “Payment models and net present value optimization for resource–constrained project scheduling, currently under submission
3.4 Capital constraints in project scheduling
 
A recent paper, which is currently under revision, discusses capital constraints in project scheduling. We study the capital–constrained project scheduling problem with discounted cash flows (CCPSPDC) and the capital– and resource–constrained project scheduling problem with discounted cash flows (CRCPSPDC). The objective of both problems is to maximize the project net present value. Both problems include capital constraints, which force the project to always have a positive cash balance. 
Reference:
  • Leyman, P. & Vanhoucke, M. (2016). Capital- and resource-constrained project scheduling with net present value optimization. Under submission.