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

June 2005

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

Authors:

N. Policella, A. Cesta, A. Oddi, and S. F. Smith

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.
@workshop{Policella-2005-120525,
author = {N. Policella And A. Cesta And A. Oddi And S. F. Smith},
title = {Schedule Robustness through Solve-and-Robustify: Generating Flexible Schedules from Different Fixed-Times Solutions},
booktitle = {Proceedings of ICAPS '05 Workshop on Constraint Programming for Planning and Scheduling},
year = {2005},
month = {June},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.