DROPS

Document

DOI: 10.4230/LIPIcs.CP.2023.19

An Efficient Constraint Programming Approach to Preemptive Job Shop Scheduling

Authors: Carla Juvin, Emmanuel Hebrard, Laurent Houssin, and Pierre Lopez

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract

Constraint Programming has been widely, and very successfully, applied to scheduling problems. However, the focus has been on uninterruptible tasks, and preemptive scheduling problems are typically harder for existing constraint solvers. Indeed, one usually needs to represent all potential task interruptions thus introducing many variables and symmetrical or dominated choices. In this paper, building on mostly known results, we observe that a large class of preemptive disjunctive scheduling problems do not require an explicit model of task interruptions. We then introduce a new constraint programming approach for this class of problems that significantly outperforms state-of-the-art dedicated approaches in our experimental results.

Cite as

Carla Juvin, Emmanuel Hebrard, Laurent Houssin, and Pierre Lopez. An Efficient Constraint Programming Approach to Preemptive Job Shop Scheduling. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{juvin_et_al:LIPIcs.CP.2023.19,
  author =	{Juvin, Carla and Hebrard, Emmanuel and Houssin, Laurent and Lopez, Pierre},
  title =	{{An Efficient Constraint Programming Approach to Preemptive Job Shop Scheduling}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.19},
  URN =		{urn:nbn:de:0030-drops-190568},
  doi =		{10.4230/LIPIcs.CP.2023.19},
  annote =	{Keywords: Constraint Programming, Scheduling, Preemptive Resources}
}

Search Results

Documents authored by Lopez, Pierre

An Efficient Constraint Programming Approach to Preemptive Job Shop Scheduling

Abstract

Cite as

Thanks for your feedback!

Could not send message