Disregarding Duration Uncertainty in Partial Order Schedules? Yes, we can!

Abstract. In the context of Scheduling under uncertainty, Partial Order Schedules (POS) provide a convenient way to build flexible solutions. A POS is obtained from a Project Graph by adding precedence constraints so that no resource conflict can arise, for any possible assignment of the activity durations. In this paper, we use a simulation approach to eval-uate the expected makespan of a number of POSs, obtained by solving scheduling benchmarks via multiple approaches. Our evaluation leads us to the discovery of a striking correlation between the expected makespan and the makespan obtained by simply fixing all durations to their aver-age. The strength of the correlation is such that it is possible to disregard completely the uncertainty during the schedule construction and yet ob-tain a very accurate estimation of the expected makespan. We provide a thorough empirical and theoretical analysis of this result, showing the existence of solid ground for finding a similarly strong relation on a broad class of scheduling problems of practical importance.