From Precedence Constraint Posting to Partial Order Schedules: A CSP Approach to Robust Scheduling

Nicola Policella, Amedeo Cesta, Angelo Oddi, and Stephen Smith
AI Communications, Special Issue on Constraint Programming for Planning and Scheduling, 20 (3): 163-180, 2007., May, 2007.


Download
  • Adobe portable document format (pdf) (309KB)
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
Constraint-based approaches to scheduling have typically formulated the problem as one of finding a consistent as-signment of start times for each goal activity. In contrast, we are pursuing an approach that operates with a prob-lem formulation more akin to least-commitment frameworks, where the objective is to post sufficient additional prece-dence constraints between pairs of activities contending for the same resources to ensure feasibility with respect to time and resource constraints. One noteworthy characteristic of this Precedence Constraint Posting (PCP) approach, is that solutions generated in this way generally encapsulate a set of feasible schedules (i.e., a solution contains the sets of activ-ity start times that remain consistent with posted sequencing constraints). Such solutions can offer advantages when there is temporal uncertainty associated with executing activities. In this paper, we consider the problem of generating tem-porally flexible schedules that possess good robustness prop-erties. We first introduce the concept of a Partial Order Schedule (P O S ), a type of temporally flexible schedule in which each embedded temporal solution is also guaranteed to be resource feasible, as a target class of solutions that ex-ploit flexibility in a robust way. We then present and an-alyze two PCP-based methods for generating P O S s. The first method uses a pure least commitment approach, where the set of all possible time-feasible schedules is successively winnowed into a smaller resource-feasible set. The second method alternatively utilizes a focused analysis of one pos-sible solution, and first generates a single, resource-feasible, fixed-times schedule. This point solution is then transformed into a P O S in a second post processing phase. Somewhat surprisingly, this second method is found to be a quite effec-tive means of generating robust schedules.

Keywords
Scheduling, Robustness, Constraint Programming.

Notes

Text Reference
Nicola Policella, Amedeo Cesta, Angelo Oddi, and Stephen Smith, "From Precedence Constraint Posting to Partial Order Schedules: A CSP Approach to Robust Scheduling," AI Communications, Special Issue on Constraint Programming for Planning and Scheduling, 20 (3): 163-180, 2007., May, 2007.

BibTeX Reference
@inproceedings{Policella_2007_7056,
   author = "Nicola Policella and Amedeo Cesta and Angelo Oddi and Stephen Smith",
   title = "From Precedence Constraint Posting to Partial Order Schedules: A CSP Approach to Robust Scheduling",
   booktitle = "AI Communications, Special Issue on Constraint Programming for Planning and Scheduling, 20 (3): 163-180, 2007.",
   month = "May",
   year = "2007",
   number= "CMU-RI-TR-",
}