Modeling and solving project scheduling with calendars

Stefan Kreter, Andreas Schutt, Peter J. Stuckey

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

7 Citations (Scopus)

Abstract

Resource-constrained project scheduling with the objective of minimizing project duration (RCPSP) is one of the most studied scheduling problems. In this paper we consider the RCPSP with general temporal constraints and calendar constraints. Calendar constraints make some resources unavailable on certain days in the scheduling period and force activity execution to be delayed while resources are unavailable. They arise in practice from, e.g., unavailabilities of staff during public holidays and weekends. The resulting problems are challenging optimization problems. We develop not only four different constraint programming (CP) models to tackle the problem, but also a specialized propagator for the cumulative resource constraints taking the calendar constraints into account. This propagator includes the ability to explain its inferences so it can be used in a lazy clause generation solver. We compare these models, and different search strategies on a challenging set of benchmarks using a lazy clause generation solver. We close 83 of the open problems of the benchmark set, and show that CP solutions are highly competitive with existing Mip models of the problem.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publication21st International Conference, CP 2015 Cork, Ireland, August 31 – September 4, 2015 Proceedings
EditorsGilles Pesant
Place of PublicationCham Switzerland
PublisherSpringer
Pages262-278
Number of pages17
ISBN (Electronic)9783319232195
ISBN (Print)9783319232188
DOIs
Publication statusPublished - 2015
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 2015 - Cork, Ireland
Duration: 31 Aug 20154 Sep 2015
Conference number: 21st
https://web.archive.org/web/20150810094235/http://booleconferences.ucc.ie/cp2015

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9255
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2015
Abbreviated titleCP 2015
CountryIreland
CityCork
Period31/08/154/09/15
Internet address

Cite this