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)

Abstract

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
PublisherSpringer
Pages628-644
Number of pages17
ISBN (Print)9783642406263
DOIs
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
http://cp2013.a4cp.org/

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

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2013
Abbreviated titleCP 2013
CountrySweden
CityUppsala
Period16/09/1320/09/13
Internet address

Cite this