Schedule Robustness through Solve-and-Robustify: Generating Flexible Schedules from Different Fixed-Times Solutions

Abstract

In previous works the authors have defined Solve-and-Robustify an original two-step procedure to generate flexible solutions, or partial order schedules, for scheduling problems. The partition in two steps — first find a solution then make it robust — not only represents a way to generate flexible, robust schedules but is also an alternative to achieve good quality solutions. This paper extends the analysis of this paradigm investigating the effects of using different start solutions as a baseline to generate partial order schedules. Two approaches are compared: the first based on the construction of flexible schedules after performing an iterative improvement phase focused on makespan optimization, the second that selects the best partial order schedule considering different fixed-time schedules as starting points. The paper experimentally shows how the characteristics of the fixed-time solutions may lower the robustness of the final partial order schedules and discusses motivations for such behavior.