Schedule Robustness Through Broader Solve and Robustify Search for Partial Order Schedules

摘要

In previous work, we have defined a two-step procedure called Solve-and-Robustify for generating flexible, partial order schedules. This partitioned problem solving approach — first find a viable solution and then generalize it to enhance robustness properties — has been shown to provide an effective basis for generating flexible, robust schedules while simultaneously achieving good quality with respect to optimization objectives. This paper extends prior analysis of this paradigm, by investigating the effects of using different start solutions as a baseline to generate partial order schedules. Two approaches are compared: the first constructs partial order schedules from a single fixed-time schedule, obtained by first performing an extended makespan optimization search phase; the second considers the search for fixed-time schedules and flexible schedules in a more integrated fashion, and constructs partial order schedules from a number of different fixed-time starting solutions. The paper experimentally shows how the characteristics of the fixed-time solutions may lower the robustness of the final partial order schedules and discusses the reasons for such behavior.