Optimization Online


New Exact Approaches to Row Layout Problems

Anja Fischer (anja.fischer***at***mathematik.uni-goettingen.de)
Frank Fischer (frank.fischer***at***uni-kassel.de)
Philipp Hungerländer (philipp.hungerlaender***at***aau.at)

Abstract: Given a set of departments, a number of rows and pairwise connectivities between these departments, the multi-row facility layout problem (MRFLP) looks for a non-overlapping arrangement of these departments in the rows such that the weighted sum of the center-to-center distances is minimized. As even small instances of the (MRFLP) are rather challenging, several special cases have been considered in the literature. In this paper we present new mixed-integer linear programming formulations for the (space-free) multi-row facility layout problem with given assignment of the departments to the rows that combine distance and betweenness variables. Using these formulations instances with up to 25 departments can be solved to optimality (within at most six hours) for the first time. Furthermore we are able to reduce the running times for instances with up to 23 departments significantly in comparison to the literature. Later on we use these formulations in an enumeration scheme for solving the (space-free) double-row facility layout problem. In particular, we test all possible row assignments, where some assignments are excluded due to our new combinatorial investigations. For the first time this approach enables us to solve instances with up to 16 departments to optimality in reasonable time.

Keywords: Double-Row Layout Problem, Facility Layout, Integer Programming, Combinatorial Bounds

Category 1: Applications -- Science and Engineering (Facility Planning and Design )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: Technical Report, Alpen-Adria Universitaet Klagenfurt, Mathematics, Optimization Group, TR-ARUK-M-O-15-10, 2015.

Download: [PDF]

Entry Submitted: 10/27/2015
Entry Accepted: 10/27/2015
Entry Last Modified: 11/03/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society