Partial-order schedules are valued because they are flexible, and therefore more robust to unexpected delays. Previous work has indicated that constructing partial-order schedules by a two-stage method, in which a fixed-time schedule is first found and a partial order then lifted from it, is far more efficient than constructing them directly by a least-commitment partial-order scheduling algorithm. However, the two-stage method is limited to exploring only a fraction of the space of partial-order schedules, namely those that can be obtained from the given fixed-time schedule. We introduce a novel constraint formulation of partial-order scheduling, which establishes explicit resource-providing "links" between activities instead of detecting and eliminating potential resource conflicts. We show that this yields an algorithm that is much faster than previous (precedence constraint posting) partial-order scheduling methods, and comparable to the two-stage method in terms of the quality and robustness of the schedules it finds. This algorithm is also complete, and because it searches the entire space of partial-order schedules, can be adapted to optimising different robustness criteria.

Many potential real-world planning applications are on the border of planning and scheduling. To handle the complex choices of actions and temporal and resource constraints of these problems we need to integrate planning and scheduling techniques. Here we propose a transition-based formulation of temporal planning problems, that enables us to represent features like deadlines, time windows, release times etc. in a simple way. We describe a CSP encoding of the transition-based formulation and its potential advantages in integrating planning and scheduling techniques.