Affiliations: ISTC-CNR โ Institute for Cognitive Science and Technology, National Research Council of Italy, Italy. E-mails: {name.surname}@istc.cnr.it | The Robotics Institute, Carnegie Mellon University, USA. E-mail: sfs@cs.cmu.edu
Abstract: Constraint-based approaches to scheduling have typically formulated the problem as one of finding a consistent assignment of start times for each goal activity. In contrast, we are pursuing an approach that operates with a problem formulation more akin to least-commitment frameworks, where the objective is to post sufficient additional precedence 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 activity 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 temporally flexible schedules that possess good robustness properties. We first introduce the concept of a Partial Order Schedule (๐ซ๐ช๐ฎ), 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 exploit flexibility in a robust way. We then present and analyze two PCP-based methods for generating ๐ซ๐ช๐ฎ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 possible solution, and first generates a single, resource-feasible, fixed-times schedule. This point solution is then transformed into a ๐ซ๐ช๐ฎ in a second post-processing phase. Somewhat surprisingly, this second method is found to be a quite effective means of generating robust schedules.
