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


A Semidefinite Optimization Approach to Space-Free Multi-Row Facility Layout


Facility layout is a well-known operations research problem that arises in numerous areas of applications. The multi-row facility layout problem is concerned with placing departments along one or several rows so as to optimize objectives such as material handling and space usage. The particular cases of the single-row and double-row facility layout problems are of particular interest in the manufacturing context where materials flow between stations located along linear corridors. Significant progress has been made in recent years on solving single-row problems to global optimality using semidefinite optimization models. The contribution of this paper is the extension of the semidefinite programming approach to the special case of multi-row layout in which all the rows have a common left origin and no empty space is allowed between departments. We call this special case the space-free multi-row facility layout problem. Although this problem may seem overly restrictive, it is a relevant problem in several contexts such as in spine layout design. Our computational results show that for space-free double-row instances the proposed semidefinite optimization approach provides high-quality global bounds in reasonable time for instances with up to 15 departments. If the assignment of departments to rows is fixed, then bounds can be computed for instances with up to 70 departments.

, 26 pages