On the Complexity of Global Scheduling Constraints under Structural Restrictions

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

On the Complexity of Global Scheduling Constraints under Structural Restrictions

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

Download BibTeX Cite

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.

Geoffrey Chu, Serge Gaspers, Nina Narodytska, Andreas Schutt, and Toby Walsh. 2013. On the Complexity of Global Scheduling Constraints under Structural Restrictions. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 503–508. https://ijcai.org/proceedings/2013/82

@inproceedings{ijcai2013p82,
  title     = {On the Complexity of Global Scheduling Constraints under Structural Restrictions},
  author    = {Chu, Geoffrey and Gaspers, Serge and Narodytska, Nina and Schutt, Andreas and Walsh, Toby},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {503--508},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/82},
}

TY  - CPAPER
TI  - On the Complexity of Global Scheduling Constraints under Structural Restrictions
AU  - Chu, Geoffrey
AU  - Gaspers, Serge
AU  - Narodytska, Nina
AU  - Schutt, Andreas
AU  - Walsh, Toby
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 503
EP  - 508
UR  - https://ijcai.org/proceedings/2013/82
ER  -