Partial Order Scheduling Procedures

Research in constraint-based scheduling has typically formulated the problem as one of finding a consistent assignment of start times for each goal activity. In contrast, we are investigating approaches to scheduling that operate with a problem formulation more akin to least-commitment planning frameworks, where the goal is to post sufficient additional precedence constraints between pairs of activities contending for the same resources to ensure feasibility with respect to time and capacity constraints. Solutions generated in this way generally represent a set of feasible schedules (i.e., the sets of activity start times that remain consistent with posted sequencing constraints), as opposed to a single assignment of start times.

There are several advantages to this approach over so-called “fixed-times” scheduling. From the standpoint of solution use, generation of sets of feasible schedules provides a measure of robustness against executional uncertainty, allowing actual activity start time decisions to be delayed and minimizing the need for solution revision. From the standpoint of solution development, a constraint posting formulation of the problem can provide a more convenient search space in which to operate. During schedule generation, alternatives are not unnecessarily pruned by the need to (over) commit to specific start times. When the need for schedule revision becomes apparent, modifications can often be made much more directly and efficiently through simple adjustment of posted constraints.