/Partial Order Scheduling Procedures

Partial Order Scheduling Procedures

Portrait of Partial Order Scheduling Procedures
Head: Stephen Smith
Contact: Stephen Smith
Associated Lab: Intelligent Coordination and Logistics Laboratory
Last Project Publication Year: 2012

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.

Displaying 1 Publications
Iterative Improvement Algorithms for the Blocking Job Shop
Angelo Oddi, Riccardo Rasconi, Amedeo Cesta and Stephen Smith

Conference Paper, Proceedings 22nd International Conference on Automated Planning and Scheduling, Atibaia, Sao Paulo, Brazil, June 2012., June, 2012

Past Project People

  • David W Hildum
  • Nicola Policella
  • Angelo Oddi
  • Amedeo Cesta
  • Riccardo Rasconi