Solve-and-robustify: Synthesizing partial order schedules by chaining

Nicola Policella, Amedeo Cesta, Angelo Oddi, and Stephen Smith
Journal of Scheduling, 12(3), 2009., May, 2009.


Download
  • Adobe portable document format (pdf) (549KB)
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.

Abstract
Goal separation is often a fruitful approach when solving complex problems. It provides a way to focus on relevant aspects in a stepwise fashion and hence bound the problem solving scope along a specific direction at any point. This work applies goal separation to the problem of synthesizing robust schedules. The problem is addressed by separating the phase of problem solution, which may pursue a standard optimization criterion (e.g., minimal makespan), from a subsequent phase of solution robustification in which a more flexible set of solutions is obtained and compactly represented through a temporal graph, called a Partial Or-der Schedule (POS ). The key advantage of a POS is that it provides the capability to promptly respond to temporal changes (e.g., activity duration changes or activity start-time delays) and to hedge against further changes (e.g., new ac-tivities to perform or unexpected variations in resource ca-pacity). On the one hand, the paper focuses on specific heuris-tic algorithms for synthesis of POS s, starting from a pre-existing schedule (hence the name Solve-and-Robustify). Different extensions of a technique called chaining, which progressively introduces temporal flexibility into the rep-resentation of the solution, are introduced and evaluated. These extensions follow from the fact that in multi-capaci-tated resource settings more than one POS can be derived from a specific fixed-times solution via chaining, and carry out a search for the most robust alternative. On the other hand, an additional analysis is performed to investigate the performance gain possible by further broadening the search process to consider multiple initial seed solutions. A detailed experimental analysis using state-of-the-art RCPSP/max benchmarks is carried out to demonstrate the performance advantage of these more sophisticated solve and robustify procedures, corroborating prior results ob-tained on smaller problems and also indicating how this leverage increases as problem size is increased.

Keywords
Iterative improvement techniques, Scheduling under uncertainty, Constraint-based scheduling

Notes

Text Reference
Nicola Policella, Amedeo Cesta, Angelo Oddi, and Stephen Smith, "Solve-and-robustify: Synthesizing partial order schedules by chaining," Journal of Scheduling, 12(3), 2009., May, 2009.

BibTeX Reference
@inproceedings{Policella_2009_7054,
   author = "Nicola Policella and Amedeo Cesta and Angelo Oddi and Stephen Smith",
   title = "Solve-and-robustify: Synthesizing partial order schedules by chaining",
   booktitle = "Journal of Scheduling, 12(3), 2009.",
   month = "May",
   year = "2009",
   number= "CMU-RI-TR-",
}