Research Article
BibTex RIS Cite

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

Year 2021, , 953 - 970, 05.03.2021

Hüseyin Karateke Ramazan Şahin

https://doi.org/10.17341/gazimmfd.734297

Abstract

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.

Keywords

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

References

  • 1Durmaz E.D. ve Ş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.
  • Ş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.
  • Tompkins, J. A., White, J. A., Bozer, Y. A. ve Tanchoco, J. M., Facilities Planning, John Wiley & Sons, ABD., 2010.
  • Bozer, Y.A., Meller, R.D. ve Erlebacher, S.J., An Improvement-Type Layout Algorithm for Single and Multiple- Floor Facilities. Management Science, 40 (7), 918–932, 1994.
  • Jerin Leno, I., Saravana Sankar, S. ve Ponnambalam, S.G. An elitist strategy genetic algorithm using simulated annealing algorithm as local search for facility layout design. International Journal of Advanced Manufacturing Technology, 84 (5-8), 787–799, 2016.
  • Niroomand, S., Hadi-Vencheh, A., Sahin, R. ve Vizvári, B. Modified migrating birds optimization algorithm for closed loop layout with exact distances in flexible manufacturing systems, Expert System with Applications, 42 (19), 6586-6597, 2015.
  • Pourvaziri, H. ve Naderi, B. A hybrid multi-population genetic algorithm for the dynamic facility layout problem, Applied Soft Computing, 24, 457-469, 2014.
  • Vitayasak, S., Pongcharoen, P. ve Hicks, C., A tool for solving stochastic dynamic facility layout problems with stochastic demand using either a Genetic Algorithm or modified Backtracking Search Algorithm, International Journal of Production Economics, 190, 146-157, 2017.
  • Şahinkoç, M. ve Bilge, Ü., Facility layout problem with QAP formulation under scenario-based uncertainty, INFOR: Information Systems and Operational Research, 56 (4), 406-427, 2018.
  • Tosun, U., Dokeroglu, T. ve Cosar A., A robust island parallel genetic algorithm for the quadratic assignment problem, International Journal of Production Research, 51 (14), 4117–4133, 2013.
  • Akça, M. ve Ş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.
  • Palomo-Romero, J.M., Salas-Morera, L. ve Garcia-Hernandez, L., An island model genetic algorithm for unequal area facility layout problems, Expert Systems with Applications, 68, 151-162, 2017.
  • Amaral, A.R.S. ve Letchford, A.N., A polyhedral approach to the single row facility layout problem, Mathematical Programming, 141 (1-2), 453-477, 2013.
  • Hungerländer, P. ve Anjos, M.F., A semidefinite optimization-based approach for global optimization of multi-row facility layout, European Journal of Operational Research, 245 (1), 46-61, 2015.
  • Safarzadeh, S. ve Koosha, H., Solving an extended multi-row facility layout problem with fuzzy clearances using GA, Applied Soft Computing, 61, 819-831, 2017.
  • Besbes, M., Zolghadri, M., Affonso, R.C., Masmoudi, F. ve Haddar, M., A methodology for solving facility layout problem considering barriers: genetic algorithm coupled with A* search, Journal of Intelligent Manufacturing, 31 (3), 615-640, 2020.
  • Izadinia, N., Eshghi, K. ve Salmani, M.H., A robust model for multi-floor layout problem. Computers & Industrial Engineering, 78, 127–134, 2014.
  • Matsuzaki, K., Irohara, T. ve Yoshimoto, K., Heuristic algorithm to solve the multi-floor layout problem with the consideration of elevator utilization. Computers & Industrial Engineering, 36(2), 487–502, 1999.
  • Khaksar-Haghani, F., Kia, R., Mahdavi, I. ve 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. International Journal of Advanced Manufacturing Technology 2013; 66(5–8):845–65, 2013.
  • Drira, A., Pierreval, H. ve Hajri-Gabouj, S., Facility layout problems: A survey. Annual Reviews in Control, 31(2), 255–267, 2007.
  • Singh, S.P. ve Sharma, R.R.K., A review of different approaches to the facility layout problems. The International Journal of Advanced Manufacturing Technology, 30(5–6), 425–433, 2006.
  • Anjos, M.F. ve Vieira, M.V.C., Mathematical optimization approaches for facility layout problems: The state-of-the-art and future research directions. European Journal of Operational Research, 261(1), 1–16, 2017.
  • Johnson, R.V., SPACECRAFT for multi-floor layout planning. Management Sciences, 28(4), 407–417, 1982.
  • Meller, R.D. ve Bozer, Y.A., A new simulated annealing algorithm for the facility layout problem. International Journal of Production Research, 34(6), 1675-1692, 1996.
  • Meller R.D. ve Bozer Y.A., Alternative approaches to solve the multi-floor facility layout problem. Journal of Manufacturing Systems 16(3): 192–203, 1997.
  • Abdinnour-Helm, S. ve Hadley, S.W., Tabu Search Based Heuristics for Multi-floor Facility Layout.” International Journal of Production Research 38 (2): 365–383, 2000.
  • Lee, K.Y., Roh, M.I. ve Jeong, H.S., An Improved Genetic Algorithm for Multi-floor Facility Layout Problems Having Inner Structure Walls and Passages. Computers & Operations Research 32 (4): 879–899, 2005.
  • Chang, C.H., Lin, J.L. ve Lin, H.J., Multiple-floor facility layout design with aisle construction. Industrial Engineering & Management Systems 5(1): 1–10, 2006.
  • Goetschalckx, M. ve Irohara, T., Efficient formulations for the multi-floor facility layout problem with elevators. Optimization Online, 1–23, 2007.
  • Bernardi, S., ve Anjos, M.F., A two-stage mathematical-programming method for the multi-floor facility layout problem. Journal of the Operational Research Society, 64(3), 352–364, 2013.
  • Ghadikolaei, Y.K. ve Shahanaghi, K., Multi-floor Dynamic Facility Layout: A Simulated Annealing-based Solution. International Journal of Operational Research 16 (4): 375–389, 2013.
  • Hathhorn, J., Sisikoglu, E. ve Sir, M.Y., A Multi Objective Mixed-integer Programming Model for a Multi-floor Facility Layout. International Journal of Production Research 51 (14): 4223–4239, 2013.
  • Kia, R., Khaksar-Haghani, F., Javadian, N. ve Tavakkoli-Moghaddam, R., Solving a Multi-floor Layout Design Model of a Dynamic Cellular Manufacturing System by an Efficient Genetic Algorithm. Journal of Manufacturing Systems 33 (1): 218–232, 2014.
  • Neghabi, H. ve Ghassemi Tari, F., An optimal approach for maximizing the number of adjacencies in multi floor layout problem. International Journal of Production Research, 53(11), 3462-3474, 2015.
  • Ahmadi, A. ve Jokar, M.R.A., An efficient multiple-stage mathematical programming method for advanced single and multi-floor facility layout problems.” Applied Mathematical Modelling 40: 5605-5620, 2016.
  • Che, A., Zhang, Y. ve Feng, J., Bi-objective optimization for multi-floor facility layout problem with fixed inner configuration and room adjacency constraints. Computers and Industrial Engineering 105: 265-276, 2017.
  • Guan, C., Zhang, Z., ve Li, Y. A flower pollination algorithm for the double-floor corridor allocation problem. International Journal of Production Research, 1–22, 2019.
  • Ahmadi, A., Pishvaee, M.S. ve Jokar, M.R.A., A Survey on Multi-floor Facility Layout Problem. Computers and Industrial Engineering 107 (2017) 158-170, 2017.
  • Conejo, A.J., Castillo, E., Minguez, R., Garcia-Bertrand, R. Decomposition Techniques in Mathematical Programming. Springer-Verlag Berlin Heidelberg, Germany, 2006.
  • Benders, J. F. Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), 238–252, 1962.
  • Rahmaniani, R., Crainic, T. G., Gendreau, M., & Rei, W., The Benders decomposition algorithm: A literature review. European Journal of Operational Research, 259(3), 801–817, 2017.
  • You, F. and Grossmann I.E., Multicut Benders decomposition algorithm for process supply chain planning under uncertainty. Annals of Operations Research 210, 191–211, 2013.
  • 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.
  • Winston, W.L., Operations Research, Applications and Algorithms (3rd Edition), Belmont: Duxbury Press, California, A.B.D., 1994.
  • Meller, R.D., Chen, W. ve Sherali, H.D., Applying the sequence-pair representation to optimal facility layout designs. Operations Research Letters, 35, 651–659, 2007.
  • Meller R.D. ve Bozer Y.A., Solving the facility layout problem with simulated annealing. Technical Report 91-20, Department of Industrial & Operations Engineering, University of Michigan, 1992.
  • Ingole, S. ve Singh, D., Unequal-area, fixed-shape facility layout problems using the firefly algorithm, Engineering Optimization, 49 (7), 1097-1115, 2017.
  • Engineering Optimization Software, PLANOPT User’s Manual (Ver. 1.50). Deltona, Florida, 1996.

Year 2021, , 953 - 970, 05.03.2021

Hüseyin Karateke Ramazan Şahin

https://doi.org/10.17341/gazimmfd.734297

Abstract

References

  • 1Durmaz E.D. ve Ş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.
  • Ş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.
  • Tompkins, J. A., White, J. A., Bozer, Y. A. ve Tanchoco, J. M., Facilities Planning, John Wiley & Sons, ABD., 2010.
  • Bozer, Y.A., Meller, R.D. ve Erlebacher, S.J., An Improvement-Type Layout Algorithm for Single and Multiple- Floor Facilities. Management Science, 40 (7), 918–932, 1994.
  • Jerin Leno, I., Saravana Sankar, S. ve Ponnambalam, S.G. An elitist strategy genetic algorithm using simulated annealing algorithm as local search for facility layout design. International Journal of Advanced Manufacturing Technology, 84 (5-8), 787–799, 2016.
  • Niroomand, S., Hadi-Vencheh, A., Sahin, R. ve Vizvári, B. Modified migrating birds optimization algorithm for closed loop layout with exact distances in flexible manufacturing systems, Expert System with Applications, 42 (19), 6586-6597, 2015.
  • Pourvaziri, H. ve Naderi, B. A hybrid multi-population genetic algorithm for the dynamic facility layout problem, Applied Soft Computing, 24, 457-469, 2014.
  • Vitayasak, S., Pongcharoen, P. ve Hicks, C., A tool for solving stochastic dynamic facility layout problems with stochastic demand using either a Genetic Algorithm or modified Backtracking Search Algorithm, International Journal of Production Economics, 190, 146-157, 2017.
  • Şahinkoç, M. ve Bilge, Ü., Facility layout problem with QAP formulation under scenario-based uncertainty, INFOR: Information Systems and Operational Research, 56 (4), 406-427, 2018.
  • Tosun, U., Dokeroglu, T. ve Cosar A., A robust island parallel genetic algorithm for the quadratic assignment problem, International Journal of Production Research, 51 (14), 4117–4133, 2013.
  • Akça, M. ve Ş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.
  • Palomo-Romero, J.M., Salas-Morera, L. ve Garcia-Hernandez, L., An island model genetic algorithm for unequal area facility layout problems, Expert Systems with Applications, 68, 151-162, 2017.
  • Amaral, A.R.S. ve Letchford, A.N., A polyhedral approach to the single row facility layout problem, Mathematical Programming, 141 (1-2), 453-477, 2013.
  • Hungerländer, P. ve Anjos, M.F., A semidefinite optimization-based approach for global optimization of multi-row facility layout, European Journal of Operational Research, 245 (1), 46-61, 2015.
  • Safarzadeh, S. ve Koosha, H., Solving an extended multi-row facility layout problem with fuzzy clearances using GA, Applied Soft Computing, 61, 819-831, 2017.
  • Besbes, M., Zolghadri, M., Affonso, R.C., Masmoudi, F. ve Haddar, M., A methodology for solving facility layout problem considering barriers: genetic algorithm coupled with A* search, Journal of Intelligent Manufacturing, 31 (3), 615-640, 2020.
  • Izadinia, N., Eshghi, K. ve Salmani, M.H., A robust model for multi-floor layout problem. Computers & Industrial Engineering, 78, 127–134, 2014.
  • Matsuzaki, K., Irohara, T. ve Yoshimoto, K., Heuristic algorithm to solve the multi-floor layout problem with the consideration of elevator utilization. Computers & Industrial Engineering, 36(2), 487–502, 1999.
  • Khaksar-Haghani, F., Kia, R., Mahdavi, I. ve 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. International Journal of Advanced Manufacturing Technology 2013; 66(5–8):845–65, 2013.
  • Drira, A., Pierreval, H. ve Hajri-Gabouj, S., Facility layout problems: A survey. Annual Reviews in Control, 31(2), 255–267, 2007.
  • Singh, S.P. ve Sharma, R.R.K., A review of different approaches to the facility layout problems. The International Journal of Advanced Manufacturing Technology, 30(5–6), 425–433, 2006.
  • Anjos, M.F. ve Vieira, M.V.C., Mathematical optimization approaches for facility layout problems: The state-of-the-art and future research directions. European Journal of Operational Research, 261(1), 1–16, 2017.
  • Johnson, R.V., SPACECRAFT for multi-floor layout planning. Management Sciences, 28(4), 407–417, 1982.
  • Meller, R.D. ve Bozer, Y.A., A new simulated annealing algorithm for the facility layout problem. International Journal of Production Research, 34(6), 1675-1692, 1996.
  • Meller R.D. ve Bozer Y.A., Alternative approaches to solve the multi-floor facility layout problem. Journal of Manufacturing Systems 16(3): 192–203, 1997.
  • Abdinnour-Helm, S. ve Hadley, S.W., Tabu Search Based Heuristics for Multi-floor Facility Layout.” International Journal of Production Research 38 (2): 365–383, 2000.
  • Lee, K.Y., Roh, M.I. ve Jeong, H.S., An Improved Genetic Algorithm for Multi-floor Facility Layout Problems Having Inner Structure Walls and Passages. Computers & Operations Research 32 (4): 879–899, 2005.
  • Chang, C.H., Lin, J.L. ve Lin, H.J., Multiple-floor facility layout design with aisle construction. Industrial Engineering & Management Systems 5(1): 1–10, 2006.
  • Goetschalckx, M. ve Irohara, T., Efficient formulations for the multi-floor facility layout problem with elevators. Optimization Online, 1–23, 2007.
  • Bernardi, S., ve Anjos, M.F., A two-stage mathematical-programming method for the multi-floor facility layout problem. Journal of the Operational Research Society, 64(3), 352–364, 2013.
  • Ghadikolaei, Y.K. ve Shahanaghi, K., Multi-floor Dynamic Facility Layout: A Simulated Annealing-based Solution. International Journal of Operational Research 16 (4): 375–389, 2013.
  • Hathhorn, J., Sisikoglu, E. ve Sir, M.Y., A Multi Objective Mixed-integer Programming Model for a Multi-floor Facility Layout. International Journal of Production Research 51 (14): 4223–4239, 2013.
  • Kia, R., Khaksar-Haghani, F., Javadian, N. ve Tavakkoli-Moghaddam, R., Solving a Multi-floor Layout Design Model of a Dynamic Cellular Manufacturing System by an Efficient Genetic Algorithm. Journal of Manufacturing Systems 33 (1): 218–232, 2014.
  • Neghabi, H. ve Ghassemi Tari, F., An optimal approach for maximizing the number of adjacencies in multi floor layout problem. International Journal of Production Research, 53(11), 3462-3474, 2015.
  • Ahmadi, A. ve Jokar, M.R.A., An efficient multiple-stage mathematical programming method for advanced single and multi-floor facility layout problems.” Applied Mathematical Modelling 40: 5605-5620, 2016.
  • Che, A., Zhang, Y. ve Feng, J., Bi-objective optimization for multi-floor facility layout problem with fixed inner configuration and room adjacency constraints. Computers and Industrial Engineering 105: 265-276, 2017.
  • Guan, C., Zhang, Z., ve Li, Y. A flower pollination algorithm for the double-floor corridor allocation problem. International Journal of Production Research, 1–22, 2019.
  • Ahmadi, A., Pishvaee, M.S. ve Jokar, M.R.A., A Survey on Multi-floor Facility Layout Problem. Computers and Industrial Engineering 107 (2017) 158-170, 2017.
  • Conejo, A.J., Castillo, E., Minguez, R., Garcia-Bertrand, R. Decomposition Techniques in Mathematical Programming. Springer-Verlag Berlin Heidelberg, Germany, 2006.
  • Benders, J. F. Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), 238–252, 1962.
  • Rahmaniani, R., Crainic, T. G., Gendreau, M., & Rei, W., The Benders decomposition algorithm: A literature review. European Journal of Operational Research, 259(3), 801–817, 2017.
  • You, F. and Grossmann I.E., Multicut Benders decomposition algorithm for process supply chain planning under uncertainty. Annals of Operations Research 210, 191–211, 2013.
  • 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.
  • Winston, W.L., Operations Research, Applications and Algorithms (3rd Edition), Belmont: Duxbury Press, California, A.B.D., 1994.
  • Meller, R.D., Chen, W. ve Sherali, H.D., Applying the sequence-pair representation to optimal facility layout designs. Operations Research Letters, 35, 651–659, 2007.
  • Meller R.D. ve Bozer Y.A., Solving the facility layout problem with simulated annealing. Technical Report 91-20, Department of Industrial & Operations Engineering, University of Michigan, 1992.
  • Ingole, S. ve Singh, D., Unequal-area, fixed-shape facility layout problems using the firefly algorithm, Engineering Optimization, 49 (7), 1097-1115, 2017.
  • Engineering Optimization Software, PLANOPT User’s Manual (Ver. 1.50). Deltona, Florida, 1996.
There are 48 citations in total.

Details

Primary Language Turkish
Subjects Engineering
Journal Section Makaleler
Authors

Hüseyin Karateke 0000-0001-5441-2949

Ramazan Şahin 0000-0001-7074-4038

Publication Date March 5, 2021
Submission Date May 8, 2020
Acceptance Date November 20, 2020
Published in Issue Year 2021

Cite

APA Karateke, H., & Şahin, R. (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. https://doi.org/10.17341/gazimmfd.734297
AMA Karateke H, Şahin R. Çok katlı tesis yerleşim problemi için iki aşamalı yaklaşım: Benders ayrıştırma algoritması. GUMMFD. March 2021;36(2):953-970. doi:10.17341/gazimmfd.734297
Chicago Karateke, Hüseyin, and Ramazan Şahin. “Ç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 (March 2021): 953-70. https://doi.org/10.17341/gazimmfd.734297.
EndNote Karateke H, Şahin R (March 1, 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.
IEEE H. Karateke and R. Şahin, “Çok katlı tesis yerleşim problemi için iki aşamalı yaklaşım: Benders ayrıştırma algoritması”, GUMMFD, vol. 36, no. 2, pp. 953–970, 2021, doi: 10.17341/gazimmfd.734297.
ISNAD Karateke, Hüseyin - Şahin, Ramazan. “Ç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 (March 2021), 953-970. https://doi.org/10.17341/gazimmfd.734297.
JAMA Karateke H, Şahin R. Çok katlı tesis yerleşim problemi için iki aşamalı yaklaşım: Benders ayrıştırma algoritması. GUMMFD. 2021;36:953–970.
MLA Karateke, Hüseyin and Ramazan Şahin. “Ç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, pp. 953-70, doi:10.17341/gazimmfd.734297.
Vancouver Karateke H, Şahin R. Çok katlı tesis yerleşim problemi için iki aşamalı yaklaşım: Benders ayrıştırma algoritması. GUMMFD. 2021;36(2):953-70.