Groupe d’études et de recherche en analyse des décisions


A continuous formulation for facility layout on rows with rectilinear distance


The facility layout problem is concerned with finding an arrangement of non-overlapping indivisible departments within a facility so as to minimize the total expected flow cost. For typical applications of layout, this flow cost is a measure of the quantity that one wishes to optimize, and it is proportional to the rectilinear distance between each pair of departments. In this paper we consider the special case of multi-row layout in which all the departments are to be placed in two or more rows, as occurs for example in the context of flexible manufacturing and in the design of application-specific integrated circuits. We propose a new mixed integer linear optimization formulation that is continuous in both dimensions \(x\) and \(y\), where \(x\) represents the position within rows and \(y\) returns the row assigned to each department. We prove the interesting property that under mild assumptions, the optimal solutions achieve integer values of \(y\), even though \(y\) is a continuous variable. Our computational results show that the proposed formulation improves on earlier linear and semidefinite formulations for instances of
multi-row layout formulated using the pairwise rectilinear distance.

, 15 pages