Optimization of Temporal Networks under Uncertainty

We define a temporal network as a directed, acyclic graph G=(V,E) whose nodes \(V = \left \{1,\ldots,n\right \}\) represent the network tasks and whose arcs E⊆V ×V describe the temporal precedences between the tasks. This convention is known as activity-on-node notation; an alternative activity-on-arc notation is discussed in [DH02]. In our notation, an arc (i,j)∈E signalizes that task j must not be started before task i has been completed. For ease of exposition, we assume that 1∈V represents the unique source and n∈V the unique sink of the network. This can always be achieved by introducing dummy nodes and/or arcs. We assume that the processing of each task requires a nonnegative amount of time. Depending on the problem under consideration, the tasks may also 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). Figure 1.1 illustrates a temporal network with cash flows.

We start with a review of deterministic optimization problems in temporal networks.We then discuss three popular methodologies to model and solve generic optimization problems under uncertainty.We close with an overview of the issues that arise when these methodologies are applied to temporal networks, and we provide a survey of the relevant literature.More specific reviews of related work are provided in the Chaps.3–6.

This chapter studies a temporal network whose tasks 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). We present a method that maximizes the network’s net present value (NPV), which is defined as the discounted sum of all arising cash flows. NPV maximization problems arise in project management, process scheduling and several other application areas. For example, in capital-intensive IT and construction projects, large amounts of money are invested over long periods of time, and the wise coordination of cash in- and outflows crucially affects the profitability of such projects. In this context, the NPV can be regarded as the “cash equivalent” of undertaking a project.

In this chapter, we study an optimization problem that is defined on a temporal network and that aims to simultaneously optimize several conflicting objectives: the network’s makespan, the resource costs, as well as the availability and reliability of the network. The availability and reliability of the network will be expressed as decision-dependent probabilities, whereas the network’s makespan and the associated resource costs will be modeled as decision-dependent random variables. The model minimizes the conditional value-at-risk (CVaR) of the makespan and resource costs while imposing constraints on the availability and reliability of the network.

In this chapter, we consider temporal networks whose task durations are functions of a resource allocation that can be chosen by the decision maker. The goal is to find a feasible resource allocation that minimizes the network’s makespan. We focus on non-renewable resources, that is, the resources are not replenished, and specified resource budgets must be met. The resource allocation model presented in this chapter is primarily suited for project scheduling problems, and for ease of exposition we will use project scheduling terminology throughout this chapter. In project scheduling, it is common to restrict attention to non-renewable resources and disregard the per-period consumption quotas that exist for renewable and doubly constrained resources, see Sect. 2.1. Apart from computational reasons, this may be justified by the fact that resource allocation decisions are often drawn at an early stage of a project’s lifecycle at which the actual resource availabilities (which are unpredictable due to staff holidays, illness and other projects) are not yet known. Thus, the goal of such resource allocation models is to decide on a rough-cut plan which will be refined later.

In this chapter we study a robust resource allocation problem that minimizes the worst-case makespan. As in the previous chapters, we assume that the resource allocation is a here-and-now decision, whereas the task start times are modeled as a wait-and-see decision that may depend on random parameters affecting the task durations. In the terminology of Sect. 2.2.2, we therefore study a two-stage robust optimization problem. In contrast to its stochastic counterpart, the complexity of the robust resource allocation problem has been unknown for a long time [Hag88]. The majority of the solution approaches presented in the literature determine suboptimal solutions without bounding the incurred optimality gap.