DROPS

Document

DOI: 10.4230/LIPIcs.CP.2024.7

Cumulative Scheduling with Calendars and Overtime

Authors: Samuel Cloutier and Claude-Guy Quimper

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract

In project scheduling, calendar considerations can increase the duration of a task when its execution overlaps with holidays. On the other hand, the use of overtime may decrease the task’s duration. We introduce the CalendarOvertime constraint which verifies that a task follows a calendar with overtime and holidays. We also introduce the CumulativeOvertime constraint, a variant of the Cumulative constraint, that also reasons with the calendars when propagating according to the resource consumption, the overtime, and the holidays. Experimental results of a RCPSP model on the PSPLIB, BL, and PACK instances augmented with calendars and overtime show that the use of the CalendarOvertime constraint offers a speedup greater than 2.9 on the instances optimally solved and finds better solutions on more than 79% of the remaining instances when compared to a decomposition of the constraint. We also show that the use of our CumulativeOvertime constraint further improves these results.

Cite as

Samuel Cloutier and Claude-Guy Quimper. Cumulative Scheduling with Calendars and Overtime. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cloutier_et_al:LIPIcs.CP.2024.7,
  author =	{Cloutier, Samuel and Quimper, Claude-Guy},
  title =	{{Cumulative Scheduling with Calendars and Overtime}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.7},
  URN =		{urn:nbn:de:0030-drops-206927},
  doi =		{10.4230/LIPIcs.CP.2024.7},
  annote =	{Keywords: Constraint programming, Scheduling, Global constraints, Calendars, Overtime, Cumulative constraint, Time-Tabling}
}

Search Results

Documents authored by Cloutier, Samuel

Cumulative Scheduling with Calendars and Overtime

Abstract

Cite as

Thanks for your feedback!

Could not send message