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

来源：

MATHEMATICAL PROGRAMMING | 2013年 / 141卷 / 1-2期

基金：

英国工程与自然科学研究理事会;

关键词：

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

← 1 2 3 4 →