A polyhedral approach to the single row facility layout problem

• 成果类型: Article
• 署名作者: Amaral, Andre R. S.; Letchford, Adam N.
• 署名单位: Universidade Federal do Espirito Santo; Lancaster University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0533-z
• 发表日期: 2013
• 页码: 453-477
• 关键词: dimensional space allocation; flexible manufacturing systems; linear arrangement; Lower bounds; algorithm

摘要

The single row facility layout problem (SRFLP) is the NP-hard problem of arranging facilities on a line, while minimizing a weighted sum of the distances between facility pairs. In this paper, a detailed polyhedral study of the SRFLP is performed, and several huge classes of valid and facet-inducing inequalities are derived. Some separation heuristics are presented, along with a primal heuristic based on multi-dimensional scaling. Finally, a branch-and-cut algorithm is described and some encouraging computational results are given.