Planning and scheduling systems that handle tasks with uncertain durations might use an extension of the Simple Temporal Network with a distinction between controllable and contingent variables and constraints. Temporal consistency is then redefined in terms of Dynamic Controllability, which means the ability to decide the precise timing of tasks only at execution time, depending on observations made, and still satisfying all constraints. This property has been recently proven to be checkable in polynomial time through a simple path-consistency-like algorithm. In this paper, we are interested in using such a model in scheduling applications, in which tasks may compete for the same resource, and should thus be sequenced. Such constraints make the problem NP-hard, and cannot be directly expressed in an STN. In the presence of uncertainty, one might also wish to postpone task sequencing until execution time. This paper provides the characterization of such a Dynamic Sequencing ability. Then we propose an incomplete checking method still relying on the STNU for the sake of temporal reasoning efficiency, adding further filtering techniques to account for sequencing constraints.

Online Copy

Available as PDF (94 KiB)

BibTeX Entry

@InProceedings{VB01, author = {Thierry Vidal and Julien Bidot}, title = {Dynamic Sequencing of Tasks in Simple Temporal Networks with Uncertainty}, year = 2001, booktitle = "Lecture Notes of the CP'01 Constraints and Uncertainty Workshop", month = "Nov" }