IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v218y2012i2p382-391.html
   My bibliography  Save this article

A graph-pair representation and MIP-model-based heuristic for the unequal-area facility layout problem

Author

Listed:
  • Bozer, Yavuz A.
  • Wang, Chi-Tai

Abstract

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.

Suggested Citation

  • Bozer, Yavuz A. & Wang, Chi-Tai, 2012. "A graph-pair representation and MIP-model-based heuristic for the unequal-area facility layout problem," European Journal of Operational Research, Elsevier, vol. 218(2), pages 382-391.
    • Handle: RePEc:eee:ejores:v:218:y:2012:i:2:p:382-391
    DOI: 10.1016/j.ejor.2011.10.052
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221711010058
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2011.10.052?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. 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.
    2. David S. Johnson & Cecilia R. Aragon & Lyle A. McGeoch & Catherine Schevon, 1989. "Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning," Operations Research, INFORMS, vol. 37(6), pages 865-892, December.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. Hanif D. Sherali & Barbara M. P. Fraticelli & Russell D. Meller, 2003. "Enhanced Model Formulations for Optimal Facility Layout," Operations Research, INFORMS, vol. 51(4), pages 629-644, August.
    9. 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).
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Anjos, Miguel F. & Vieira, Manuel V.C., 2017. "Mathematical optimization approaches for facility layout problems: The state-of-the-art and future research directions," European Journal of Operational Research, Elsevier, vol. 261(1), pages 1-16.
    2. Mowrey, Corinne H. & Parikh, Pratik J. & Gue, Kevin R., 2018. "A model to optimize rack layout in a retail store," European Journal of Operational Research, Elsevier, vol. 271(3), pages 1100-1112.
    3. Kulturel-Konak, Sadan, 2012. "A linear programming embedded probabilistic tabu search for the unequal-area facility layout problem with flexible bays," European Journal of Operational Research, Elsevier, vol. 223(3), pages 614-625.
    4. Gonçalves, José Fernando & Resende, Mauricio G.C., 2015. "A biased random-key genetic algorithm for the unequal area facility layout problem," European Journal of Operational Research, Elsevier, vol. 246(1), pages 86-107.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Gonçalves, José Fernando & Resende, Mauricio G.C., 2015. "A biased random-key genetic algorithm for the unequal area facility layout problem," European Journal of Operational Research, Elsevier, vol. 246(1), pages 86-107.
    2. Anjos, Miguel F. & Vieira, Manuel V.C., 2017. "Mathematical optimization approaches for facility layout problems: The state-of-the-art and future research directions," European Journal of Operational Research, Elsevier, vol. 261(1), pages 1-16.
    3. Minhee Kim & Junjae Chae, 2019. "Monarch Butterfly Optimization for Facility Layout Design Based on a Single Loop Material Handling Path," Mathematics, MDPI, vol. 7(2), pages 1-21, February.
    4. Asef-Vaziri, Ardavan & Jahandideh, Hossein & Modarres, Mohammad, 2017. "Loop-based facility layout design under flexible bay structures," International Journal of Production Economics, Elsevier, vol. 193(C), pages 713-725.
    5. Kulturel-Konak, Sadan, 2012. "A linear programming embedded probabilistic tabu search for the unequal-area facility layout problem with flexible bays," European Journal of Operational Research, Elsevier, vol. 223(3), pages 614-625.
    6. 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.
    7. Mehmet Burak Şenol & Ekrem Alper Murat, 2023. "A sequential solution heuristic for continuous facility layout problems," Annals of Operations Research, Springer, vol. 320(1), pages 355-377, January.
    8. Scholz, Daniel & Jaehn, Florian & Junker, Andreas, 2010. "Extensions to STaTS for practical applications of the facility layout problem," European Journal of Operational Research, Elsevier, vol. 204(3), pages 463-472, August.
    9. Paes, Frederico Galaxe & Pessoa, Artur Alves & Vidal, Thibaut, 2017. "A hybrid genetic algorithm with decomposition phases for the Unequal Area Facility Layout Problem," European Journal of Operational Research, Elsevier, vol. 256(3), pages 742-756.
    10. Xie, Yue & Zhou, Shenghan & Xiao, Yiyong & Kulturel-Konak, Sadan & Konak, Abdullah, 2018. "A β-accurate linearization method of Euclidean distance for the facility layout problem with heterogeneous distance metrics," European Journal of Operational Research, Elsevier, vol. 265(1), pages 26-38.
    11. Mariem Besbes & Marc Zolghadri & Roberta Costa Affonso & Faouzi Masmoudi & Mohamed Haddar, 2020. "A methodology for solving facility layout problem considering barriers: genetic algorithm coupled with A* search," Journal of Intelligent Manufacturing, Springer, vol. 31(3), pages 615-640, March.
    12. Zhongwei Zhang & Lihui Wu & Zhaoyun Wu & Wenqiang Zhang & Shun Jia & Tao Peng, 2022. "Energy-Saving Oriented Manufacturing Workshop Facility Layout: A Solution Approach Using Multi-Objective Particle Swarm Optimization," Sustainability, MDPI, vol. 14(5), pages 1-28, February.
    13. Emde, Simon & Boysen, Nils, 2012. "Optimally locating in-house logistics areas to facilitate JIT-supply of mixed-model assembly lines," International Journal of Production Economics, Elsevier, vol. 135(1), pages 393-402.
    14. Bazargan-Lari, Massoud, 1999. "Layout designs in cellular manufacturing," European Journal of Operational Research, Elsevier, vol. 112(2), pages 258-272, January.
    15. Stefan Helber & Daniel Böhme & Farid Oucherif & Svenja Lagershausen & Steffen Kasper, 2016. "A hierarchical facility layout planning approach for large and complex hospitals," Flexible Services and Manufacturing Journal, Springer, vol. 28(1), pages 5-29, June.
    16. Ravi Kumar, K. & Hadjinicola, George C. & Lin, Ting-li, 1995. "A heuristic procedure for the single-row facility layout problem," European Journal of Operational Research, Elsevier, vol. 87(1), pages 65-73, November.
    17. Irawan, Chandra Ade & Song, Xiang & Jones, Dylan & Akbari, Negar, 2017. "Layout optimisation for an installation port of an offshore wind farm," European Journal of Operational Research, Elsevier, vol. 259(1), pages 67-83.
    18. 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.
    19. Liu, Jingfa & Wang, Dawen & He, Kun & Xue, Yu, 2017. "Combining Wang–Landau sampling algorithm and heuristics for solving the unequal-area dynamic facility layout problem," European Journal of Operational Research, Elsevier, vol. 262(3), pages 1052-1063.
    20. Ali Derakhshan Asl & Kuan Yew Wong & Manoj Kumar Tiwari, 2016. "Unequal-area stochastic facility layout problems: solutions using improved covariance matrix adaptation evolution strategy, particle swarm optimisation, and genetic algorithm," International Journal of Production Research, Taylor & Francis Journals, vol. 54(3), pages 799-823, February.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. 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.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.