A polyhedral approach to the single row facility layout problem
A polyhedral approach to the single row facility layout problem
复制标题
DOI：
10.1007/s10107-012-0533-z
复制
发表时间：
2013-10
影响因子：
2.7
通讯作者：
André R. S. Amaral;Adam N. Letchford
中科院分区：
文献类型：
--
作者：
André R. S. Amaral;Adam N. Letchford
单行设施布局问题是在一条直线上布置设施，同时使设施对之间的距离加权和最小的NP-难问题。在本文中，详细的多面体研究的SRFLP，并导出了几个巨大的类的有效和小平面诱导不等式。提出了一些分离算法，沿着一个原始的启发式基于多维缩放。最后给出了一个分支切割算法，并给出了一些令人鼓舞的计算结果。
The single row facility layout problem (SRFLP) is theNP-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.