Single-row equidistant facility layout as a special case of single-row facility layout

Abstract

In this paper we discuss two particular layout problems, namely the Single-Row Equidistant Facility Layout Problem (SREFLP) and the Single-Row Facility Layout Problem (SRFLP). Our aim is to consolidate the two respective branches in the layout literature. We show that the SREFLP is not only a special case of the Quadratic Assignment Problem but also a special case of the SRFLP. This new connection is relevant as the strongest exact methods for the SRFLP outperform the best approaches specialised to the SREFLP. We describe and compare the exact approaches for the SRFLP, the SREFLP and Linear Arrangement that is again a special case of the SREFLP. In a computational study we showcase that the strongest exact approach for the SRFLP clearly outperforms the strongest exact approach tailored to the SREFLP on medium and large benchmark instances from the literature.

Keywords:

• single-row facility layout
• space allocation
• machine location
• quadratic ordering problem
• quadratic assignment problem
• semidefinite optimisation

Notes

Helmberg (2000) shows that one can easily switch between the and formulations of bivalent problems so that the resulting bounds remain the same and structural properties are preserved.

For exact numbers of the speed differences see http://www.cpubenchmark.net/.