Çok katlı tesis yerleşim problemi için iki aşamalı yaklaşım: Benders ayrıştırma algoritması

Karateke, Huseyin; Miller-Van Wieren, Leila

doi:10.17341/gazimmfd.734297

Çok katlı tesis yerleşim problemi için iki aşamalı yaklaşım: Benders ayrıştırma algoritması

Hüseyin Karateke, (Gazi Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Ankara, Türkiye)

Leila Miller-Van WİEREN (Gazi Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Ankara, Türkiye)

Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi

16 3

Yıl: 2021 Cilt: 36 Sayı: 2 Sayfa Aralığı: 953 - 970 Metin Dili: Türkçe DOI: 10.17341/gazimmfd.734297 İndeks Tarihi: 29-07-2022

Çok katlı tesis yerleşim problemi için iki aşamalı yaklaşım: Benders ayrıştırma algoritması

Öz:

Yüksek arazi maliyetleri ve sınırlı alanlar sebebiyle, çok katlı tesislerin kullanımı günümüzde oldukça yaygındır. Ancak toplam taşıma maliyetleri, kat edilen mesafe ve çalışan hareketleri düşünüldüğünde, tesis içerisindeki bölümlerin hangi kata atanacağı ve kat içerisindeki konumları önem kazanmaktadır. Bölümlerin hangi kata atanacağı ve kat içerisindeki konumlarının belirlendiği problem çok katlı tesis yerleşim problemi (ÇKTYP) olarak adlandırılmaktadır. Asansör sayısı, asansörlerin konumları, kat sayısı, bölüm sayısı vb. karar değişkenleri ÇKTYP’nin karmaşıklığını arttırmakta ve çözümünü zorlaştırmaktadır. Bu çalışmada, ÇKTYP’nin çözümü için iki aşamadan oluşan bir yöntem önerilmiştir. Önerilen algoritmanın ilk aşamasında bölümlerin katlara atamaları yapılırken, ikinci aşamada ise, bölümler arasındaki toplam taşıma maliyetlerini minimize edecek şekilde bölümlerin kat içindeki yerleri belirlemek için Benders ayrıştırma algoritması kullanılmıştır. Çalışmanın literatüre katkısı, ÇKTYP’nin çözümü için Benders ayrıştırma algoritmasının ilk olarak bu çalışmada kullanılmış olmasıdır. Önerilen Benders ayrıştırma algoritması literatürden alınan 4 adet problem üzerinde test edilmiştir. Ayrıca bu çalışmada ÇKTYP olarak uyarlanan büyük boyutlu 3 adet problemin çözümü yapılmıştır. Sonuçlar incelendiğinde,önerilen Benders ayrıştırma algoritmasının literatürden alınan 4 problem için %0,1234 ile %5,3385 oranında maliyette iyileştirmeler yaptığı görülmüştür.

Anahtar Kelime: Tesis Yerleşim Problemi Benders Ayrıştırma Algoritması Çok Katlı Tesis Yerleşimi Problemi

A two-stage approach for the multi-floor facility layout problem: Benders decomposition algorithm

Öz:

Today, the use of multi-floor facilities is quite common due to the high land costs and limited areas. However, the locations of the departments on the floor and floor to which departments are assigned become important when considering the total material handling costs, distance traveled and employee movements. The problem where the departments are assigned to which floor and their locations within the floor are determined is called as a multi-floor facility layout problem (MFLP). Different decision variables such as the number of elevators, the location of elevator, the number of floors, and the number of departments increase the complexity of the MFLP. In this study, a two-stage approach is proposed for the solution of MFLP. In the first stage of the proposed approach, the departments are assigned to floors, while in the second stage, the Benders decomposition algorithm is used to determine the locations of departments within the floor in a way to minimize the total material handling costs between the departments. The contribution of the study to the literature is that it is the first study which employs the Benders decomposition algorithm to solve the MFLP. The proposed Benders decomposition algorithm was tested on five problems taken from the literature. In addition, in this paper, three large-scale problems adapted as MFLP were solved. When the results are analyzed, it is seen that the proposed Benders decomposition algorithm was conducted cost improvements ranging 0.12% to 7.64% for five problems taken from the literature.

Anahtar Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık

1. Durmaz E.D., Şahin R., NSGA-II and goal programming approach for the multi-objective single row facility layout problem, Journal of the Faculty of Engineering and Architecture of Gazi University, 32 (3), 941-955, 2017.
2. Şahin R., A simulated annealing heuristic for the dynamic facility layout problem, Journal of the Faculty of Engineering and Architecture of Gazi University, 23 (4), 863-870, 2008.
3. Tompkins J.A., White J.A., Bozer Y.A. ve Tanchoco, J. M., Facilities Planning, John Wiley & Sons, ABD., 2010.
4. Bozer Y.A., Meller R.D., Erlebacher S.J., An Improvement-Type Layout Algorithm for Single and Multiple- Floor Facilities. Manage. Sci., 40 (7), 918– 932, 1994.
5. Öztürkoğlu O., Hoşer D., A new warehouse design problem and a proposed polynomial-time optimal order picking algorithm, Journal of the Faculty of Engineering and Architecture of Gazi University, 33 (4), 1569-1588, 2018.
6. Niroomand S., Hadi-Vencheh A., Şahin R., Vizvári B., Modified migrating birds optimization algorithm for closed loop layout with exact distances in flexible manufacturing systems, Expert Syst. Appl., 42 (19), 6586-6597, 2015.
7. Pourvaziri H., Naderi B., A hybrid multi-population genetic algorithm for the dynamic facility layout problem, Appl. Soft Comput., 24, 457-469, 2014.
8. Vitayasak S., Pongcharoen P., Hicks C., A tool for solving stochastic dynamic facility layout problems with stochastic demand using either a Genetic Algorithm or modified Backtracking Search Algorithm, Int. J. Prod. Econ., 190, 146-157, 2017.
9. Şahinkoç M., Bilge Ü., Facility layout problem with QAP formulation under scenario-based uncertainty, INFOR: Information Systems and Operational Research, 56 (4), 406-427, 2018.
10. Tosun U., Dökeroğlu T., Coşar A., A robust island parallel genetic algorithm for the quadratic assignment problem, Int. J. Prod. Res., 51 (14), 4117–4133, 2013.
11. Akça M., Şahin R., Multi objective mixed integer facility layout problem and application at military facility, Pamukkale University Journal of Engineering Sciences, 24 (1), 117-123, 2018.
12. Palomo-Romero J.M., Salas-Morera L., GarciaHernandez L., An island model genetic algorithm for unequal area facility layout problems, Expert Syst. Appl., 68, 151-162, 2017.
13. Amaral A.R.S., Letchford A.N., A polyhedral approach to the single row facility layout problem, Math. Program., 141 (1-2), 453-477, 2013.
14. Hungerländer P., Anjos M.F., A semidefinite optimization-based approach for global optimization of multi-row facility layout, Eur. J. Oper. Res., 245 (1), 46- 61, 2015.
15. Safarzadeh S., Koosha H., Solving an extended multirow facility layout problem with fuzzy clearances using GA, Appl. Soft Comput., 61, 819-831, 2017.
16. Besbes M., Zolghadri M., Affonso R.C., Masmoudi F., Haddar M., A methodology for solving facility layout problem considering barriers: genetic algorithm coupled with A* search, J. Intell. Manuf., 31 (3), 615-640, 2020.
17. Izadinia N., Eshghi K., Salmani M.H., A robust model for multi-floor layout problem. Comput. Ind. Eng., 78, 127–134, 2014.
18. Matsuzaki K., Irohara T., Yoshimoto K., Heuristic algorithm to solve the multi-floor layout problem with the consideration of elevator utilization. Comput. Ind. Eng., 36 (2), 487–502, 1999.
19. Khaksar-Haghani F., Kia R., Mahdavi I., Kazemi M., A genetic algorithm for solving a multi-floor layout design model of a cellular manufacturing system with alternative process routings and flexible configuration. Int. J. Adv. Manuf. Technol., 66 (5–8), 845–65, 2013.
20. Drira A., Pierreval H., Hajri-Gabouj S., Facility layout problems: A survey. Annu. Rev. Control, 31 (2), 255– 267, 2007.
21. Singh S.P., Sharma R.R.K., A review of different approaches to the facility layout problems. Int. J. Adv. Manuf. Technol., 30 (5–6), 425–433, 2006.
22. Anjos M.F., Vieira M.V.C., Mathematical optimization approaches for facility layout problems: The state-ofthe-art and future research directions. Eur. J. Oper. Res., 261 (1), 1–16, 2017.
23. Johnson R.V., SPACECRAFT for multi-floor layout planning. Manage. Sci., 28 (4), 407–417, 1982.
24. Meller R.D., Bozer Y.A., A new simulated annealing algorithm for the facility layout problem. Int. J. Prod. Res., 34 (6), 1675-1692, 1996.
25. Meller R.D., Bozer Y.A., Alternative approaches to solve the multi-floor facility layout problem. J. Manuf. Syst., 16 (3), 192–203, 1997.
26. Abdinnour-Helm S., Hadley S.W., Tabu Search Based Heuristics for Multi-floor Facility Layout. Int. J. Prod. Res., 38 (2), 365–383, 2000.
27. Lee K.Y., Roh M.I., Jeong H.S., An Improved Genetic Algorithm for Multi-floor Facility Layout Problems Having Inner Structure Walls and Passages. Comput. Oper. Res., 32 (4), 879–899, 2005.
28. Chang C.H., Lin J.L., Lin H.J., Multiple-floor facility layout design with aisle construction. Ind. Eng. Manage. Syst., 5 (1), 1–10, 2006.
29. Goetschalckx M., Irohara T., Efficient formulations for the multi-floor facility layout problem with elevators. Optim. Online, 1–23, 2007.
30. Bernardi S., Anjos M.F., A two-stage mathematicalprogramming method for the multi-floor facility layout problem. J. Oper. Res. Soc., 64 (3), 352–364, 2013.
31. Ghadikolaei Y.K., Shahanaghi K., Multi-floor Dynamic Facility Layout: A Simulated Annealing-based Solution. Int. J. Oper. Res., 16 (4), 375–389, 2013.
32. Hathhorn J., Şişikoglu E., Sir M.Y., A Multi Objective Mixed-integer Programming Model for a Multi-floor Facility Layout. Int. J. Prod. Res., 51 (14), 4223–4239, 2013.
33. Kia R., Khaksar-Haghani F., Javadian N., TavakkoliMoghaddam R., Solving a Multi-floor Layout Design Model of a Dynamic Cellular Manufacturing System by an Efficient Genetic Algorithm. J. Manuf. Syst., 33 (1), 218–232, 2014.
34. Neghabi H., Ghassemi Tari F., An optimal approach for maximizing the number of adjacencies in multi floor layout problem. Int. J. Prod. Res., 53 (11), 3462-3474, 2015.
35. Ahmadi A., Jokar M.R.A., An efficient multiple-stage mathematical programming method for advanced single and multi-floor facility layout problems.” Appl. Math. Modell., 40, 5605-5620, 2016.
36. Che A., Zhang Y., Feng J., Bi-objective optimization for multi-floor facility layout problem with fixed inner configuration and room adjacency constraints. Comput. Ind. Eng., 105, 265-276, 2017.
37. Guan C., Zhang Z., Li Y., A flower pollination algorithm for the double-floor corridor allocation problem. Int. J. Prod. Res., 57 (20), 6506–6527, 2019.
38. Ahmadi A., Pishvaee M.S., Jokar M.R.A., A Survey on Multi-floor Facility Layout Problem. Comput. Ind. Eng., 107, 158-170, 2017.
39. Conejo, A.J., Castillo, E., Minguez, R., GarciaBertrand, R. Decomposition Techniques in Mathematical Programming. Springer-Verlag Berlin Heidelberg, Germany, 2006.
40. Benders J.F., Partitioning procedures for solving mixedvariables programming problems. Numerische Mathematik, 4 (1), 238–252, 1962.
41. Rahmaniani R., Crainic T.G., Gendreau M., Rei W., The Benders decomposition algorithm: A literature review. Eur. J. Oper. Res., 259 (3), 801–817, 2017.
42. You F., Grossmann I.E., Multicut Benders decomposition algorithm for process supply chain planning under uncertainty. Ann. Oper. Res., 210, 191– 211, 2013.
43. Bazaraa, M.S., Jarvis, J.J. ve Sherali, H.D., Linear Programming and Network Flows (4th Edition), John Wiley & Sons, New York, A.B.D., 2010.
44. Winston, W.L., Oper. Res., Applications and Algorithms (3rd Edition), Belmont: Duxbury Press, California, A.B.D., 1994.
45. Meller R.D., Chen W., Sherali H.D., Applying the sequence-pair representation to optimal facility layout designs. Oper. Res. Lett., 35, 651–659, 2007.
46. Bozer Y.A., Meller R.D., Erlebacher S.J., An improvement type layout algorithm for multiple-floor facilities. Technical Report 91-11, Department of Industrial & Operations Engineering, University of Michigan, 1991.
47. Meller R.D., Bozer Y.A., Solving the facility layout problem with simulated annealing. Technical Report 91- 20, Department of Industrial & Operations Engineering, University of Michigan, 1992.
48. Ingole S., Singh D., Unequal-area, fixed-shape facility layout problems using the firefly algorithm, Eng. Optim., 49 (7), 1097-1115, 2017.
49. Engineering Optimization Software, PLANOPT User’s Manual (Ver. 1.50). Deltona, Florida, 1996.

APA	Karateke H, Miller-Van Wieren L (2021). Çok katlı tesis yerleşim problemi için iki aşamalı yaklaşım: Benders ayrıştırma algoritması. , 953 - 970. 10.17341/gazimmfd.734297
Chicago	Karateke Huseyin,Miller-Van Wieren Leila Çok katlı tesis yerleşim problemi için iki aşamalı yaklaşım: Benders ayrıştırma algoritması. (2021): 953 - 970. 10.17341/gazimmfd.734297
MLA	Karateke Huseyin,Miller-Van Wieren Leila Çok katlı tesis yerleşim problemi için iki aşamalı yaklaşım: Benders ayrıştırma algoritması. , 2021, ss.953 - 970. 10.17341/gazimmfd.734297
AMA	Karateke H,Miller-Van Wieren L Çok katlı tesis yerleşim problemi için iki aşamalı yaklaşım: Benders ayrıştırma algoritması. . 2021; 953 - 970. 10.17341/gazimmfd.734297
Vancouver	Karateke H,Miller-Van Wieren L Çok katlı tesis yerleşim problemi için iki aşamalı yaklaşım: Benders ayrıştırma algoritması. . 2021; 953 - 970. 10.17341/gazimmfd.734297
IEEE	Karateke H,Miller-Van Wieren L "Çok katlı tesis yerleşim problemi için iki aşamalı yaklaşım: Benders ayrıştırma algoritması." , ss.953 - 970, 2021. 10.17341/gazimmfd.734297
ISNAD	Karateke, Huseyin - Miller-Van Wieren, Leila. "Çok katlı tesis yerleşim problemi için iki aşamalı yaklaşım: Benders ayrıştırma algoritması". (2021), 953-970. https://doi.org/10.17341/gazimmfd.734297

APA	Karateke H, Miller-Van Wieren L (2021). Çok katlı tesis yerleşim problemi için iki aşamalı yaklaşım: Benders ayrıştırma algoritması. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 36(2), 953 - 970. 10.17341/gazimmfd.734297
Chicago	Karateke Huseyin,Miller-Van Wieren Leila Çok katlı tesis yerleşim problemi için iki aşamalı yaklaşım: Benders ayrıştırma algoritması. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 36, no.2 (2021): 953 - 970. 10.17341/gazimmfd.734297
MLA	Karateke Huseyin,Miller-Van Wieren Leila Çok katlı tesis yerleşim problemi için iki aşamalı yaklaşım: Benders ayrıştırma algoritması. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol.36, no.2, 2021, ss.953 - 970. 10.17341/gazimmfd.734297
AMA	Karateke H,Miller-Van Wieren L Çok katlı tesis yerleşim problemi için iki aşamalı yaklaşım: Benders ayrıştırma algoritması. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2021; 36(2): 953 - 970. 10.17341/gazimmfd.734297
Vancouver	Karateke H,Miller-Van Wieren L Çok katlı tesis yerleşim problemi için iki aşamalı yaklaşım: Benders ayrıştırma algoritması. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2021; 36(2): 953 - 970. 10.17341/gazimmfd.734297
IEEE	Karateke H,Miller-Van Wieren L "Çok katlı tesis yerleşim problemi için iki aşamalı yaklaşım: Benders ayrıştırma algoritması." Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 36, ss.953 - 970, 2021. 10.17341/gazimmfd.734297
ISNAD	Karateke, Huseyin - Miller-Van Wieren, Leila. "Çok katlı tesis yerleşim problemi için iki aşamalı yaklaşım: Benders ayrıştırma algoritması". Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 36/2 (2021), 953-970. https://doi.org/10.17341/gazimmfd.734297