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

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.