1

Vietnam Journal of Mathematics 35:4(2007) 387-398

Models and Algorithms for Robust PERT Scheduling with Time-dependent Task Durations

Michel Minoux

Abstract. This paper investigates models and solution algorithms for solving PERT scheduling problems under uncertainty on task processing times. The proposed uncertainty model is very general in that it is capable of representing situations in which various distinct sources of uncertainty have to be considered ; and realistic in that it is consistent with the idea that situations featuring simultaneous occurrence of worst-case values for all (or a majority of) the task processing times do not have to be taken into account in the robustness analysis. From the computational point-of-view, a major interest of this uncertainty model is to provide very compact representations of potentially huge uncertainty sets, thus leading to efficient solution algorithms. We address both the standard case (where processing times do not depend on actual starting dates) and the case of time-dependent task durations.