To Appear: Proceedings 14th International Conference on Automated Planning and Scheduling (ICAPS 04), Whistler CA, June 2004
Generating Robust Schedules through Temporal Flexibility
Nicola Policella(1), Stephen F. Smith(2), Amedeo Cesta (1) and Angelo Oddi(1)
(1) IP-CNR
National Research Council
Viale Marx 15
I-00137 Rome, Italy
(2)The Robotics Institute
Carnegie Mellon University
Pittsburgh, PA 15213, USA
Abstract
This paper considers the problem of generating partial order schedules (POS), schedules that retain temporal flexibility and thus provide some degree of robustness in the face of unpredictable execution circumstances. We begin by proposing a set of measures for assessing and comparing the robustness properties of alternative $\mathcal{POS}$s. Then, using a common solving framework, we develop two orthogonal procedures for constructing a POS. The first, which we call the resource envelope based approach, uses computed bounds on cumulative resource usage (i.e., a resource envelope) to identify potential resource conflicts, and progressively winnows the total set of temporally feasible solutions into a smaller set of resource feasible solutions by resolving detected conflicts. The second, referred to as the earliest start time approach, instead uses conflict analysis of a specific (i.e., earliest start time) solution to generate an initial fixed-time schedule, and then expands this solution to a set of resource feasible solutions in a post-processing step. We evaluate the relative effectiveness of these two procedures on a set of project scheduling benchmark problems. As might be expected, the second approach, by virtue of its more focused analysis, is found to be a more efficient POS generator. Somewhat counterintuitively, however, it is also found to produce POSs that are more robust.
Copyright 2004, Policella, Smith, Cesta and Oddi.
All rights reserved.
Full paper in .pdf format