Basic Concept
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.

General Solution Procedures
We have developed a family of constraint-posting scheduling procedures, each derived from a basic constraint satisfaction search model called PCP (Precedence Constraint Posting). Similar to previous work in opportunistic scheduling, PCP utilizes look-ahead analysis to dynamically direct (and redirect) an incremental search process. However, the "variables" in PCP's problem formulation are ordering decisions O(i,j,r) (for activities i and j contending for resource r) with two possible "values": i before j or j before i. The insight underlying PCP is that simple, computationally inexpensive measures of sequencing flexibility can provide powerful look-ahead guidance in this "sequencing" search space. With the basic PCP procedure we have demonstrated problem solving performance comparable to other, currently dominant constraint satisfaction scheduling techniques with order of magnitude reduction in computational cost.

More recent work has investigated the use of PCP in more frequently encountered, optimization-based scheduling contexts. We have developed extended PCP-based procedures for scheduling under several common objective criteria. With respect to makespan minimization, we have produced solutions competitive with the best OR approximation algorithms currently known on large, previously published benchmark problems with less computational expense. We have also developed PCP-based solution improvement procedure for minimizing weighted tardiness; experiments here have demonstrated an ability to efficiently produce job-shop schedules that substantially improve on those generated by a complex of dispatch-based solutions designed for tardiness minimization across a range of different shop conditions. Finally, we have developed generalizations of the basic PCP procedure's look-ahead heuristics and pruning criteria that enable efficient scheduling under a range of complex, quantitative temporal constraints that are difficult to handle within traditional, "fixed times" scheduling approaches (e.g., imprecise durations, activity separation constraints, sequence-dependent setups).

Scheduling Experiments in an Automated Chemistry Workstation
Other research has recently applied constraint-posting scheduling concepts to the problem of scheduling experiments for an automated robotic chemistry workstation (resident in the Chemistry Department at CMU). This problem is dominated by the presence of finite temporal separation constraints between successive steps of individual experimental plans (e.g., a chemical reaction must be sampled by the robot 2 hours after the last sample taken), and the overall objective is to maximize parallel experimentation. By developing a constraint-posting variant of the existing ``fixed-times'' scheduling procedure and introducing the capability to support flexibility in constraint specification, the utilization of the workstation was almost doubled. A version of this scheduler has been operational since September, 1993. Our current focus here is on development of complementary mechanisms for exploiting the temporal flexibility inherent in a constraint-posting schedule at execution time, in this case to reactively manage workstation plans in response to feedback on the progress of various experiments.

back to top