Carnegie Mellon University
Advanced Search   
  Look in
       Title     Description
       Inactive Projects

Partial Order Scheduling Procedures
Head: Stephen Smith
Contact: Stephen Smith
Mailing address:
Carnegie Mellon University
Robotics Institute
5000 Forbes Avenue
Pittsburgh, PA 15213
Associated center(s) / consortia:
 Center for Integrated Manfacturing Decision Systems (CIMDS)
Associated lab(s) / group(s):
 Intelligent Coordination and Logistics Laboratory
This page last updated - September 2010.
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.