License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2022.14
URN: urn:nbn:de:0030-drops-166433
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16643/
Go to the corresponding LIPIcs Volume Portal

Coppé, Vianney ; Gillard, Xavier ; Schaus, Pierre

Solving the Constrained Single-Row Facility Layout Problem with Decision Diagrams

pdf-format:
LIPIcs-CP-2022-14.pdf (0.8 MB)

Abstract

The Single-Row Facility Layout Problem is an NP-hard problem dealing with the ordering of departments with given lengths and pairwise traffic intensities in a facility. In this context, one seeks to minimize the sum of the distances between department pairs, weighted by the corresponding traffic intensities. Practical applications of this problem include the arrangement of rooms on a corridor in hospitals or offices, airplanes and gates in an airport or machines in a manufacture. This paper presents two novel exact models for the Constrained Single-Row Facility Layout Problem, a recent variant of the problem including positioning, ordering and adjacency constraints. On the one hand, the state-of-the-art mixed-integer programming model for the unconstrained problem is extended to incorporate the constraints. On the other hand, a decision diagram-based approach is described, based on an existing dynamic programming model for the unconstrained problem. Computational experiments show that both models outperform the only mixed-integer programming model in the literature, to the best of our knowledge. While the two models have execution times of the same order of magnitude, the decision diagram-based approach handles positioning constraints much better but the mixed-integer programming model has the advantage for ordering constraints.

BibTeX - Entry

@InProceedings{coppe_et_al:LIPIcs.CP.2022.14,
  author =	{Copp\'{e}, Vianney and Gillard, Xavier and Schaus, Pierre},
  title =	{{Solving the Constrained Single-Row Facility Layout Problem with Decision Diagrams}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16643},
  URN =		{urn:nbn:de:0030-drops-166433},
  doi =		{10.4230/LIPIcs.CP.2022.14},
  annote =	{Keywords: Discrete Optimization, Mixed-Integer Programming, Decision Diagrams, Constrained Single-Row Facility Layout Problem}
}

Keywords: Discrete Optimization, Mixed-Integer Programming, Decision Diagrams, Constrained Single-Row Facility Layout Problem
Collection: 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)
Issue Date: 2022
Date of publication: 23.07.2022
Supplementary Material: Software (Source Code): https://github.com/vcoppe/csrflp-dd
Software (Source Code): https://github.com/vcoppe/csrflp-mip

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI