---
title: "On the Complexity of Global Scheduling Constraints under Structural Restrictions"
authors:
  - "Geoffrey Chu"
  - "Serge Gaspers"
  - "Nina Narodytska"
  - "Andreas Schutt"
  - "Toby Walsh"
doi: ""
url: "https://ijcai.org/proceedings/2013/82"
pdf: "https://ijcai.org/proceedings/2013/0082.pdf"
venue: "Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence"
year: 2013
pages: "503-508"
track: ""
keywords:
---

# On the Complexity of Global Scheduling Constraints under Structural Restrictions

Geoffrey Chu, Serge Gaspers, Nina Narodytska, Andreas Schutt, Toby Walsh

*Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence*, pages 503-508.

## Abstract

We investigate the computational complexity of two global constraints, CUMULATIVE and INTERDISTANCE. These are key constraints in modeling and solving scheduling problems. Enforcing domain consistency on both is NP-hard. However, restricted versions of these constraints are often sufficient in practice. Some examples include scheduling problems with a large number of similar tasks, or tasks sparsely distributed over time. Another example is runway sequencing problems in air-traffic control, where landing periods have a regular pattern. Such cases can be characterized in terms of structural restrictions on the constraints. We identify a number of such structural restrictions and investigate how they impact the computational complexity of propagating these global constraints. In particular, we prove that such restrictions often make propagation tractable.