Partial-order support-link scheduling

Debdeep Banerjee*, Patrik Haslum

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    3 Citations (Scopus)

    Abstract

    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.

    Original languageEnglish
    Title of host publicationICAPS 2011 - Proceedings of the 21st International Conference on Automated Planning and Scheduling
    Pages307-310
    Number of pages4
    Publication statusPublished - 2011
    Event21st International Conference on Automated Planning and Scheduling, ICAPS 2011 - Freiburg, Germany
    Duration: 11 Jun 201116 Jun 2011

    Publication series

    NameICAPS 2011 - Proceedings of the 21st International Conference on Automated Planning and Scheduling

    Conference

    Conference21st International Conference on Automated Planning and Scheduling, ICAPS 2011
    Country/TerritoryGermany
    CityFreiburg
    Period11/06/1116/06/11

    Fingerprint

    Dive into the research topics of 'Partial-order support-link scheduling'. Together they form a unique fingerprint.

    Cite this