A polyhedral approach to the single row facility layout problem

被引:60
作者
Amaral, Andre R. S. [1 ]
Letchford, Adam N. [2 ]
机构
[1] Univ Fed Espirito Santo, Dept Informat, BR-29060900 Vitoria, ES, Brazil
[2] Univ Lancaster, Dept Management Sci, Lancaster LA1 4YX, England
基金
英国工程与自然科学研究理事会;
关键词
Facility layout; Polyhedral combinatorics; Branch-and-cut; DIMENSIONAL SPACE ALLOCATION; FLEXIBLE MANUFACTURING SYSTEMS; LINEAR ARRANGEMENT; LOWER BOUNDS; ALGORITHM;
D O I
10.1007/s10107-012-0533-z
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
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.
引用
收藏
页码:453 / 477
页数:25
相关论文
共 32 条
[1]   An exact approach to the one-dimensional facility layout problem [J].
Amaral, Andre R. S. .
OPERATIONS RESEARCH, 2008, 56 (04) :1026-1033
[2]   A new lower bound for the single row facility layout problem [J].
Amaral, Andre R. S. .
DISCRETE APPLIED MATHEMATICS, 2009, 157 (01) :183-190
[3]   On the exact solution of a facility layout problem [J].
Amaral, ARS .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 173 (02) :508-518
[4]  
Anjos M.F., 2005, HDB SEMIDEFINITE CON
[5]  
Anjos M.F., 2005, Discrete Optimization, V2, P113, DOI [10.1016/j.disopt.2005.03.001., DOI 10.1016/J.DISOPT.2005.03.001]
[6]   Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes [J].
Anjos, Miguel F. ;
Vannelli, Anthony .
INFORMS JOURNAL ON COMPUTING, 2008, 20 (04) :611-617
[7]   Provably near-optimal solutions for very large single-row facility layout problems [J].
Anjos, Miguel F. ;
Yen, Ginger .
OPTIMIZATION METHODS & SOFTWARE, 2009, 24 (4-5) :805-817
[8]  
[Anonymous], 1952, Psychometrika
[9]   Stronger linear programming relaxations of max-cut [J].
Avis, D ;
Umemoto, J .
MATHEMATICAL PROGRAMMING, 2003, 97 (03) :451-469
[10]   Decorous Lower Bounds for Minimum Linear Arrangement [J].
Caprara, Alberto ;
Letchford, Adam N. ;
Salazar-Gonzalez, Juan-Jose .
INFORMS JOURNAL ON COMPUTING, 2011, 23 (01) :26-40