Journal
DISCRETE APPLIED MATHEMATICS
Volume 157, Issue 1, Pages 183-190Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.dam.2008.06.002
Keywords
Facility layout; Linear arrangement; Polyhedral combinatorics
Categories
Funding
- CNPq-Brazil [500212/02-3]
Ask authors/readers for more resources
Single row facility layout is the NP-hard problem of arranging n departments of given lengths on a line so as to minimize the weighted sum of the distances between department pairs. In this paper, we define a polytope associated to the problem and present a partial linear description whose integral points are the incidence vectors of a layout. We propose a new lower bound for the problem by optimizing a linear program over the partial description given and using some valid inequalities, which are introduced here, as cutting planes. Several instances from the literature as well as new large instances with size n = 33 and n = 35 are considered in the computational tests. For all the instances tested, the proposed lower bound achieves the cost of an optimal layout within reasonable computing time. (c) 2008 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available