Minimizing a Makespan Under Uncertainty

1 Introduction andMotivation

Temporal Constraint Networks (TCN) represent relations between dates of events and also allow to express constraints on the possible durations of activities from intervals of values [Dechter et al., 1991]. TCN have been extended to take into account uncertainty of durations of some tasks in realistic applications. A distinction is made between so-called contingent constraints (for example, when the duration of a task cannot be known before its execution) and controllable ones (for example a time interval to be chosen between starting times of two tasks). The resulting network (Simple Temporal Network with Uncertainty) becomes a decisionmaking problem under uncertainty, and notions of consistency must be refined so as to ensure controllability, that is, ensured consistency despite uncertainty [Morris et al., 2001; Khatib et al., 2001]. As far as we know, the TCN community has extensively worked on the controllability of a network, but the question of optimizing the total duration of set of tasks described by a STPU has not been studied. Nevertheless, not all solutions to an STPU are equally valuable, and solutions minimizing the makespan are of obvious practical interest.

This paper provides a full picture of the complexity of the makespan minimization problem under interval-based uncertainty. It is shown that the only NP-hard problem is the one of finding the greatest lower bound of the float, which is closely related to asserting the possible criticality of a task. All other problems turn out to be polynomial. The fact that the two problems of asserting if an arc is necessary critical or possibly critical do not have the same complexity is rather unexpected.

Didier Dubois

UPS, IRIT, 118 route de Narbonne, 31062 Toulouse, France dubois@irit.fr

2 Preliminaries

An activity network is classically defined as a set of activities (or tasks) with given duration times, related to each other by means of precedence constraints. When there are no resource constraints, it can be represented by a directed, connected and acyclic graph. Of major concern, is to minimize the ending time of the last task, also called the makespan of the network. For each task, three quantities have practical importance for the management of the activity network: The earliest starting time esti j of an activity ✭i❀ j✮ is the date before which the activity cannot be started without violation of a precedence constraint. The latest starting time lsti j of an activity ✭i❀ j✮ is the date after which the activity cannot be started without delaying the end of the project. The float fi j of an activity ✭i❀ j✮ is the difference between the latest starting time lsti j and the earliest starting time esti j . An activity is critical if and only if its float is equal to zero.

Now, activity durations (weights of the arcs) ✭i❀ j✮ ✷ A are only known to belong to time intervals Di j ❂ ❬d a0 i j ❀d ✰ i j ❪, d a0 i j ✕ 0. We define a configuration as a precise instantiation of the duration of each task ✭i❀ j✮ ✷ A. Ω denotes a configuration, while di j✭Ω✮ denotes the duration of activity ✭i❀ j✮ in configuration Ω. G✭i❀ j✮ is the subgraph of G composed of nodes succeeding i and preceding j.

Computing earliest starting dates is not a difficult issue. Here we solve four problems, stated in [Chanas et al., 2002]: 1) determining the widest intervals LSTkl (bounds) of possible values of the latest starting times lstkl of a given activity ✭k❀ l✮ ✷ A, i.e. the interval LSTkl ❂ ❬lst a0 kl ❀ lst ✰ kl ❪ defined by lst a0 kl ❂minlstkl✭Ω✮ and lst ✰ kl ❂maxlstkl✭Ω✮; the problem of computing lst a0 kl (resp. lst ✰ kl ) is denoted GLBLST (resp. LUBLST); 2) determining the widest intervals Fkl of possible values of floats (total floats) fkl of a given activity ✭k❀ l✮ ✷ A, i.e. the interval Fkl ❂ ❬ f a0 kl ❀ f ✰ kl ❪ bounded by f a0 kl ❂min fkl✭Ω✮ and f ✰ kl ❂max fkl✭Ω✮. The problem of computing f a0 kl (resp. f ✰ kl ) is denoted GLBF (resp. LUBF). In both problems minimization and maximization are taken over all possible configurations. The solutions to problems GLBLST, LUBLST, LUBF and GLBF come down to finding an extreme configuration [Dubois et al., 2005] where such bounds are attained. As there are 2 n extreme configurations, it explains the potentially exponential nature of the problem. GLBLST, LUBLST and GLBF have recently been solved in [Chanas

H´el`ene Fargier

UPS, IRIT, 118 route de Narbonne, 31062 Toulouse, France fargier@irit.fr and Zieli ´nski, 2002; Zieli ´nski, 2005], and only GLBF is NPhard. In this paper, we recall the solutions of these three problems, and present the solution to the last one LUBF, thus providing a full picture of the makespan minimization problem under incomplete information.

3 Evaluating Necessary Criticality

This section presents a new method which can decide if a given task ✭k❀ l✮ is necessary critical.

First, under the assumption that the durations of the predecessors of task ✭k❀ l✮ are precisely known, we already know an algorithm that asserts if ✭k❀ l✮ is necessary critical. It constitutes the basis for computing the LUB and GLB of the latest starting dates in polynomial time in [Zieli´nski, 2005]. We have extended these results and can provide a general algorithm which asserts if ✭k❀ l✮ is necessary critical in a network G in polynomial time without any consideration of the durations of tasks preceding ✭k❀ l✮.

Suppose that ✭k❀ l✮ is necessary critical in the sub-network G✭i❀n✮, then we proved that we can fix the duration of tasks preceding node i at their lower bounds, without changing the necessary criticality of ✭k❀ l✮ in G. On the contrary, if ✭k❀ l✮ is not necessary critical in G✭i❀n✮, then we proved that we can fix the duration of tasks preceding node i at their upper bounds. Applying this idea on networks G✭i❀n✮ for i from k down to 1, for each network, tasks preceding ✭k❀ l✮ have always precise duration in G✭i❀ n✮, and so we can easily assert the necessary criticality in polynomial time. The resulting algorithm requires O✭mn✮ steps to assert if ✭k❀ l✮ is necessary critical in G.

4 Computing the Least Upper Bound on the Floats

To compute the LUB of the floats, we are going to increase step by step the duration of ✭k❀ l✮ from Dkl ❂ d a0 kl until ✭k❀ l✮ becomes necessary critical with a duration d a0 kl ✰ f ✄ . We proved that the value f ✄ is the LUB of the float of ✭k❀ l✮.

If we assume that activities preceding ✭k❀ l✮ have precise durations, then f ✰ kl ❂ lst ✰ kl a0 est ✰ kl . So at each step of the computation, we can easily compute f ✰ i representing the float of ✭k❀ l✮ in network G✭i❀n✮. After initialization of durations in the network by the algorithm which asserts if ✭k❀ l✮ is necessary critical, if ✭k❀ l✮ is not necessary critical, we have to increase the duration of ✭k❀ l✮ by the minimal non-null f ✰ i for i preceding k, then go back to the test of asserting necessary criticality. When ✭k❀ l✮ becomes necessary critical, we have found f ✰ kl . At each iteration, ✭k❀ l✮ becomes necessary critical in at least one new network G✭i❀n✮, and so the resulting algorithm is polynomial and takes O✭n 3 m✮.

The following table summarizes the complexity of the different problems of the PERT/CPM on intervals:

In this table we give the complexity of the theoretically best known algorithm which computes the quantity of interest. In particular, the path algorithm [Dubois et al., 2005] which computes the GLB and LUB of floats and latest starting dates runs in O✭✭n✰m✮❥P❥✮ time , where ❥P❥ is the number of path of the graph G. The real complexity thus depends of the topology of the network.

5 Conclusion

This paper proposes a complete solution to the criticality analysis of a network of activities when durations of tasks are ill-known. It is shown that moving from precise to imprecise durations radically changes the complexity of the problem, ruining the traditional critical path method. Part of the problem, pertaining to the GLB of the float, becomes NPhard, the other questions remaining polynomial, although not straightforwardly so. These complexity results shed light on reasons why the more familiar stochastic counterparts to this basic scheduling problem are so difficult to handle, part of the difficulty being already present in the interval analysis. The proposed algorithms can be of obvious relevance to practical predictive project scheduling problems where durations of tasks are not known in advance. Clearly, due to the basic nature of the addressed problem, several lines of research can be envisaged for future research. For instance one may assume that part of the tasks durations are controllable and additional constraints relating durations and starting or ending times may be available. Then one obtains a makespan minimization problem in the more general setting of STPU's.