Scheduling optional tasks with explanation

Andreas Schutt, Thibaut Feydy, Peter J. Stuckey

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

11 Citations (Scopus)


Many scheduling problems involve reasoning about tasks which may or may not actually occur, so called optional tasks. The state-of-the-art approach to modelling and solving such problems makes use of interval variables which allow a start time of indicating the task does not run. In this paper we show we can model interval variables in a lazy clause generation solver, and create explaining propagators for scheduling constraints using these interval variables. Given the success of lazy clause generation on many scheduling problems, this combination appears to give a powerful new solving approach to scheduling problems with optional tasks. We demonstrate the new solving technology on well-studied flexible job-shop scheduling problems where we are able to close 36 open problems.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming - 19th International Conference, CP 2013, Proceedings
Number of pages17
ISBN (Print)9783642406263
Publication statusPublished - 22 Oct 2013
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 2013 - Uppsala, Sweden
Duration: 16 Sep 201320 Sep 2013
Conference number: 19th

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8124 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceInternational Conference on Principles and Practice of Constraint Programming 2013
Abbreviated titleCP 2013
Internet address

Cite this