TY - JOUR AU - Bercher, Pascal AU - Olz, Conny PY - 2020/04/03 Y2 - 2024/03/29 TI - POP ≡ POCL, Right? Complexity Results for Partial Order (Causal Link) Makespan Minimization JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 34 IS - 06 SE - AAAI Technical Track: Planning, Routing, and Scheduling DO - 10.1609/aaai.v34i06.6530 UR - https://ojs.aaai.org/index.php/AAAI/article/view/6530 SP - 9785-9793 AB - <p>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 <em>deordering</em>) is <em>NP-complete</em>. We provide a series of further results on special cases and implications, such as <em>reordering</em>, where orderings can be changed arbitrarily.</p> ER -