Deterministic Estimation of the Expected Makespan of a POS Under Duration Uncertainty

Abstract

This paper is about characterizing the expected makespan of a Partial Order Schedule (POS) under duration uncertainty. Our analysis is based on very general assumptions about the uncertainty: in particular, we assume that only the min, max, and average durations are known. This information is compatible with a whole range of values for the expected makespan. We prove that the largest of these values and the corresponding “worst-case” distribution can be obtained in polynomial time and we present an $O(n^3)$ computation algorithm. Then, using theoretical and empirical arguments, we show that such expected makespan is strongly correlated with certain global properties of the POS, and we exploit this correlation to obtain a linear-time estimator. The estimator provides accurate results under a very large variety of POS structures, scheduling problem types, and uncertainty models. The algorithm and the estimator may be used during search by an optimization approach, in particular one based on Constraint Programming: this allows to tackle a stochastic problem by solving a dramatically simpler (and yet accurate) deterministic approximation.