Maximizing the net present value of a project under uncertainty

Abstract

We address the maximization of a project’s expected net present value when the activity durations and cash flows are described by a discrete set of alternative scenarios with associated occurrence probabilities. In this setting, the choice of scenario-independent activity start times frequently leads to infeasible schedules or severe losses in revenues. We suggest to determine an optimal target processing time policy for the project activities instead. Such a policy prescribes an activity to be started as early as possible in the realized scenario, but never before its (scenario-independent) target processing time. We formulate the resulting model as a global optimization problem and present a branch-and-bound algorithm for its solution. Extensive numerical results illustrate the suitability of the proposed policy class and the runtime behavior of the algorithm.

Introduction

Project scheduling is concerned with the temporal coordination of the various tasks of a project. Admissible schedules must obey constraints such as precedence relations (a task cannot start unless some other tasks have been completed) and resource restrictions (labor, machines, etc. are scarce resources with limited capacities). In the following, we assume that projects are given in activity-on-node representation. That is, a project is treated as a directed graph $G=(V\text{,}E)$, where the nodes $V=\{1\text{,}\dots \text{,}n\}$ represent the activities (e.g., ‘conduct market research’ or ‘develop prototype’) and the arcs, $E\subseteq V\times V$, denote temporal precedences between the activities (e.g., ‘the prototype cannot be developed before the market research has been completed’). Unless otherwise stated, we consider project graphs with a unique source $1\in V$ and a unique sink $n\in V$; this can always be achieved by introducing dummy nodes and/or arcs. We furthermore assume that activities give rise to cash flows. Positive cash flows denote cash inflows (e.g., received payments), whereas negative cash flows represent cash outflows (e.g., accrued costs). An introduction to project scheduling can be found in [7].

Most of the literature on project scheduling focuses on arranging activities in such a way that the project makespan, that is, the time required to complete all tasks, is minimized. This objective may be unsuitable for capital-intensive IT and construction projects, where large amounts of money are invested over long periods of time. In such environments, the wise coordination of cash in- and outflows crucially affects the profitability of a project. This suggests that in such situations, financial aspects should be at the center of the decision maker’s attention. A project’s financial benefit is measured by its net present value (NPV), which is determined by discounting all arising cash flows (at some internal rate of return) to the start time of the project. As such, the NPV can be regarded as the ‘cash equivalent’ of undertaking the project.

In this paper, we present a formulation which maximizes the expected NPV of a project when the activity durations and cash flows are described by a discrete set of alternative scenarios with associated occurrence probabilities [23]. Since cash flows can be positive or negative, the early start policy (‘start every activity as early as possible’) known from makespan minimization does not yield an optimal solution. Similarly, the choice of scenario-independent activity start times frequently leads to infeasible schedules or severe losses in revenues. The search for truly adaptive schedules that react to the uncertainties revealed over time, on the other hand, becomes severely intractable since the underlying stochastic process is decision-dependent [13], [21]. To overcome this difficulty, we suggest to determine an optimal (scenario-independent) target processing time (TPT) policy for the project activities. In case activity $i\in V$ could be started earlier than its TPT in the realized scenario, it will be postponed to its TPT. If, on the other hand, activity i cannot be started at its TPT (because preceding activities finish late), it will be started as soon as possible thereafter. The class of TPT policies is a strict subset of the class of non-anticipative scheduling decisions. By restricting ourselves to this class, we can solve the NPV maximization problem for projects of non-trivial size. Our model accommodates generalized precedence relations [10], [11] but disregards resource restrictions. We discuss these assumptions in Section 3.

The remainder of this paper is organized as follows. In the next section we summarize related literature. Section 3 introduces our problem formulation, while Section 4 describes the components of a branch-and-bound solution procedure. Section 5 presents and interprets the results of an extensive numerical study. We conclude in Section 6.