A polyhedral approach to the single row facility layout problem |
| |
Authors: | André R S Amaral Adam N Letchford |
| |
Institution: | 1. Departamento de Informática, Universidade Federal do Espírito Santo (UFES), Vitória, ES, 29060-900, Brazil 2. Department of Management Science, Lancaster University, Lancaster, LA1 4YX, UK
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|