3 Search Results for "Garraffa, Michele"

Document
DOI: 10.4230/LIPIcs.CP.2025.6
Modeling and Explaining an Industrial Workforce Allocation and Scheduling Problem

Authors: Ignace Bleukx, Ryma Boumazouza, Tias Guns, Nadine Laage, and Guillaume Poveda

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract
We present an industrial case on workforce allocation and scheduling in the aircraft manufacturing industry, where available teams need to be assigned to logistical operations. This application presents several challenges such as the scale of the problem, the need for fair workload distribution, and the need for methods for mitigating unforeseen disruptions due to technical malfunctions or incompatible weather conditions. We compare different Constraint Programming (CP) models for the allocation and scheduling problems, with extra focus on modeling the workload balancing component. Additionally, we investigate different techniques for explaining infeasibility of a disrupted schedule, such as conflict computation using Minimal Unsatisfiable Subsets (MUSes) and feasibility restoration using Minimal Correction Subsets (MCSes) or constraint relaxations. Our experimental results show that by using appropriate modeling techniques, the problem can be solved in reasonable time, thereby producing fair schedules. Additionally, we show how invalidated schedules can be explained and restored efficiently to help human operators in solving disruptions to the schedule.
Cite as

Ignace Bleukx, Ryma Boumazouza, Tias Guns, Nadine Laage, and Guillaume Poveda. Modeling and Explaining an Industrial Workforce Allocation and Scheduling Problem. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 6:1-6:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bleukx_et_al:LIPIcs.CP.2025.6,
  author =	{Bleukx, Ignace and Boumazouza, Ryma and Guns, Tias and Laage, Nadine and Poveda, Guillaume},
  title =	{{Modeling and Explaining an Industrial Workforce Allocation and Scheduling Problem}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{6:1--6:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.6},
  URN =		{urn:nbn:de:0030-drops-238670},
  doi =		{10.4230/LIPIcs.CP.2025.6},
  annote =	{Keywords: modeling, scheduling, fairness, explanations, feasibility restoration}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.16
The Hybrid Flexible Flowshop with Transportation Times

Authors: Eddie Armstrong, Michele Garraffa, Barry O'Sullivan, and Helmut Simonis

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract
This paper presents the hybrid, flexible flowshop problem with transportation times between stages, which is an extension of an existing scheduling problem that is well-studied in the literature. We explore different models for the problem with Constraint Programming, MILP, and local search, and compare them on generated benchmark problems that reflect the problem of the industrial partner. We then study two different factory layout design problems, and use the optimization tool to understand the impact of the design choices on the solution quality.
Cite as

Eddie Armstrong, Michele Garraffa, Barry O'Sullivan, and Helmut Simonis. The Hybrid Flexible Flowshop with Transportation Times. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{armstrong_et_al:LIPIcs.CP.2021.16,
  author =	{Armstrong, Eddie and Garraffa, Michele and O'Sullivan, Barry and Simonis, Helmut},
  title =	{{The Hybrid Flexible Flowshop with Transportation Times}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.16},
  URN =		{urn:nbn:de:0030-drops-153075},
  doi =		{10.4230/LIPIcs.CP.2021.16},
  annote =	{Keywords: Constraint Programming, scheduling, hybrid flowshop}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2017.28
Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem

Authors: Lei Shang, Michele Garraffa, Federico Della Croce, and Vincent T'Kindt

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Abstract
This paper proposes an exact exponential algorithm for the problem of minimizing the total tardiness of jobs on a single machine. It exploits the structure of a basic branch-and-reduce framework based on the well known Lawler's decomposition property. The proposed algorithm, called branch-and-merge, is an improvement of the branch-and-reduce technique with the embedding of a node merging operation. Its time complexity is O*(2.247^n) keeping the space complexity polynomial. The branch-and-merge technique is likely to be generalized to other sequencing problems with similar decomposition properties.
Cite as

Lei Shang, Michele Garraffa, Federico Della Croce, and Vincent T'Kindt. Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 28:1-28:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{shang_et_al:LIPIcs.IPEC.2017.28,
  author =	{Shang, Lei and Garraffa, Michele and Della Croce, Federico and T'Kindt, Vincent},
  title =	{{Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{28:1--28:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.28},
  URN =		{urn:nbn:de:0030-drops-85468},
  doi =		{10.4230/LIPIcs.IPEC.2017.28},
  annote =	{Keywords: Exact exponential algorithm, Single machine total tardiness, Branch-and-merge}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2021
  • 1 2018

  • Refine by Author
  • 2 Garraffa, Michele
  • 1 Armstrong, Eddie
  • 1 Bleukx, Ignace
  • 1 Boumazouza, Ryma
  • 1 Della Croce, Federico
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 2 Computing methodologies → Planning and scheduling
  • 1 Human-centered computing → User centered design
  • 1 Software and its engineering → Constraints
  • 1 Theory of computation → Constraint and logic programming

  • Refine by Keyword
  • 2 scheduling
  • 1 Branch-and-merge
  • 1 Constraint Programming
  • 1 Exact exponential algorithm
  • 1 Single machine total tardiness
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact