POP ≡ POCL, right? Complexity Results for Partial Order (Causal Link) Makespan Minimization

Pascal Bercher, Conny Olz

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

    Abstract

    We study PO and POCL plans with regard to their makespan the execution time when allowing the parallel execution of causally independent actions. Partially ordered (PO) plans are often assumed to be equivalent to partial order causal link (POCL) plans, where the causal relationships between actions are explicitly represented via causal links. As a first contribution, we study the similarities and differences of PO and POCL plans, thereby clarifying a common misconception about their relationship: There are PO plans for which there does not exist a POCL plan with the same orderings. We prove that we can still always find a POCL plan with the same makespan in polynomial time. As another main result we prove that turning a PO or POCL plan into one with minimal makespan by only removing ordering constraints (called deordering) is NP-complete. We provide a series of further results on special cases and implications, such as reordering, where orderings can be changed arbitrarily.
    Original languageEnglish
    Title of host publicationAAAI-20 Technical Tracks 6
    EditorsVincent Conitzer and Fei Sha
    Place of PublicationCalifornia
    PublisherPKP Publishing Services
    Pages9785-9793
    ISBN (Print)978-1-57735-835-0
    DOIs
    Publication statusPublished - 2020
    EventThe 34th AAAI Conference on Artificial Intelligence - New York, United States
    Duration: 1 Jan 2020 → …

    Conference

    ConferenceThe 34th AAAI Conference on Artificial Intelligence
    Country/TerritoryUnited States
    Period1/01/20 → …
    Other7-12 February

    Fingerprint

    Dive into the research topics of 'POP ≡ POCL, right? Complexity Results for Partial Order (Causal Link) Makespan Minimization'. Together they form a unique fingerprint.

    Cite this