A graph-pair representation and MIP-model-based heuristic for the unequal-area facility layout problem
Owing to its theoretical as well as practical significance, the facility layout problem with unequal-area departments has been studied for several decades, with a wide range of heuristic and a few exact solution procedures developed by numerous researchers. In one of the exact procedures, the facility layout problem is formulated as a mixed-integer programming (MIP) model in which binary (0/1) variables are used to prevent departments from overlapping with one another. Obtaining an optimal solution to the MIP model is difficult, and currently only problems with a limited number of departments can be solved to optimality. Motivated by this situation, we developed a heuristic procedure which uses a “graph pair” to determine and manipulate the relative location of the departments in the layout. The graph-pair representation technique essentially eliminates the binary variables in the MIP model, which allows the heuristic to solve a large number of linear programming models to construct and improve the layout in a comparatively short period of time. The search procedure to improve the layout is driven by a simulated annealing algorithm. The effectiveness of the proposed graph-pair heuristic is demonstrated by comparing the results with those reported in recent papers. Possible extensions to the graph-pair representation technique are discussed at the end of the paper.
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Koulamas, C & Antony, SR & Jaen, R, 1994. "A survey of simulated annealing applications to operations research problems," Omega, Elsevier, vol. 22(1), pages 41-56, January.
- Gordon C. Armour & Elwood S. Buffa, 1963. "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science, INFORMS, vol. 9(2), pages 294-309, January.
- Komarudin & Wong, Kuan Yew, 2010. "Applying Ant System for solving Unequal Area Facility Layout Problems," European Journal of Operational Research, Elsevier, vol. 202(3), pages 730-746, May.
- Scholz, Daniel & Petrick, Anita & Domschke, Wolfgang, 2009. "STaTS: A Slicing Tree and Tabu Search based heuristic for the unequal area facility layout problem," European Journal of Operational Research, Elsevier, vol. 197(1), pages 166-178, August.
- van Camp, Drew J. & Carter, Michael W. & Vannelli, Anthony, 1992. "A nonlinear optimization approach for solving facility layout problems," European Journal of Operational Research, Elsevier, vol. 57(2), pages 174-189, March.
- Scholz, Daniel & Petrick, Anita & Domschke, Wolfgang, 2009. "STaTS: A Slicing Tree and Tabu Search based heuristic for the unequal area facility layout problem," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 39430, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
- Heragu, Sunderesh S. & Kusiak, Andrew, 1991. "Efficient models for the facility layout problem," European Journal of Operational Research, Elsevier, vol. 53(1), pages 1-13, July.
When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:218:y:2012:i:2:p:382-391. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Zhang, Lei)
If references are entirely missing, you can add them using this form.