Decorous combinatorial lower bounds for row layout problems

Mirko Dahlbeck, Anja Fischer and Frank Fischer

European Journal of Operational Research, 2020, vol. 286, issue 3, 929-944

Abstract: In this paper we consider the Double-Row Facility Layout Problem (DRFLP). Given a set of departments and pairwise transport weights between them the DRFLP asks for a non-overlapping arrangement of the departments along both sides of a common path such that the weighted sum of the center-to-center distances between the departments is minimized. Despite its broad applicability in factory planning, only small instances can be solved to optimality in reasonable time. Apart from this even deriving good lower bounds using existing integer programming formulations and branch-and-cut methods is a challenging problem. We focus here on deriving combinatorial lower bounds which can be computed very fast. These bounds generalize the star inequalities of the Minimum Linear Arrangement Problem. Furthermore we exploit a connection of the DRFLP to some parallel identical machine scheduling problem. Our lower bounds can be further improved by combining them with a new distance-based mixed-integer linear programming model, which is not a formulation for the DRFLP, but can be solved close to optimality quickly. We compare the new lower bounds to some heuristically determined upper bounds on medium-sized and large DRFLP instances. Special consideration is given to the case when all departments have the same length. Furthermore we show that the lower bounds that we derive using adapted variants of our approaches for the Parallel Row Ordering Problem, a DRFLP variant where the row assignment of the departments is given in advance and spaces between neighboring departments are not allowed, are even better with respect to the gaps.

Keywords: Facilities planning and design; Integer programming; Row layout problem; Lower bounds (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172030343X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:286:y:2020:i:3:p:929-944

DOI: 10.1016/j.ejor.2020.04.010

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().