2 Search Results for "Garraffa, Michele"

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 Author
  • 2 Garraffa, Michele
  • 1 Armstrong, Eddie
  • 1 Della Croce, Federico
  • 1 O'Sullivan, Barry
  • 1 Shang, Lei
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Planning and scheduling
  • 1 Software and its engineering → Constraints

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

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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