Heurıstıcs Based On Decomposıtıon Algorıthms For Multı-Floor Facılıty Layout Problem

Tesis yerleşim problemi (TYP) tesiste yer alan bölümlerin en uygun alanlara yerleştirilmesi ile ilgilenmektedir. Tesis yerleşim probleminin temel amacı, bir sistem aracılığıyla iş, malzeme ve bilginin sorunsuz akışının sağlanmasıdır. TYP, tek katlı ve çok katlı yerleşim olarak iki farklı sınıfa ayrılabilir. Bölümlerin birden fazla katta yer aldığı problem türlerine çok katlı tesis yerleşim problemi (ÇKTYP) denilmektedir. Gerçek dünya uygulamalarında, bazen malzeme ve işlemlerden dolayı tesisteki bölümleri tek kat yerine birden çok kata yerleştirmek daha pratiktir. Ancak bu durum problemin çözümünü zorlaştırır. ÇKTYP’nde kat sayısı, bölüm sayısı, asansör sayısı, asansörün konumu gibi karar değişkenleri problemin karmaşıklığını arttırmaktadır. Bu tez çalışmasının motivasyonu, ÇKTYP literatürü incelenmiş ve problemin çözümünde kullanıldığına rastlanılmamış algoritmalar olan Dantzig-Wolfe ve Benders ayrıştırma algoritmalarının geliştirilmesidir. Geliştirilen yöntem iki aşamadan oluşmaktadır. Birinci aşamada 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 belirlenmektedir. Bu aşamada ÇKTYP’nin matematiksel modeli ana problem ve alt problem olmak üzere iki parçaya ayrıştırılmıştır. Geliştirilen Dantzig-Wolfe ve Benders ayrıştırma algoritmalarının test edilmesi için literatürde daha önce çözümü yapılan 5, bu çalışmada ÇKTYP’ne uyarlanan 3 olmak üzere toplam 8 problemin çözümü yapılmıştır. Çözüm sonuçları incelendiğinde, geliştirilen Dantzig-Wolfe ve Benders ayrıştırma algoritmalarının literatürden alınan 5 problemin hepsi için daha iyi sonuçlar bulduğu görülmüştür. Literatürdeki test problemi eksikliği dikkate alınarak toplamda 140 tane test problemi üretilmiştir. Üretilen test problemleri geliştirilen Dantzig-Wolfe ve Benders ayrıştırma algoritmaları ile çözülmüşlerdir. Tez kapsamında ayrıca gerçek hayat uygulaması da gerçekleştirilmiştir. Bu kapsamda bir yağ üretim tesisi incelenmiş, modellenmiş ve geliştirilen algoritmalar ile çözülmüştür. Çözüm sonucunda mevcut yerleşim %7,5 iyileştirilmiştir.Facility layout problem (FLP) deals with the location of the departments in the facility to the most suitable arrangements. The main purpose of the FLP is to ensure the smooth flow of work, material and information through a system. FLP can be divided into two different classes as single-floor and multi-floor layout problem. The types of problems in which the departments are located on more than one floor are called multi-floor facility layout problem (MFLP). In real world applications, it is sometimes more practical to arrange departments in the facility on multi floors rather than a single floor, due to materials and processes. However, this situation makes it difficult to solve the problem. Decision variables such as number of floors, number of departments, number of elevators, location of the elevator increase the complexity of the problem in the MFLP. The motivation for this thesis study is the development of Dantzig-Wolfe and Benders decomposition algorithms, which are unseen algorithms used in solving the problem when the literature of the MFLP has been examined. The developed method consists of two-stages. In the first stage, while the departments are assigned to the floors, in the second stage, the locations of the departments are determined to minimize the total material handling costs between the departments. At second stage, the mathematical model of the multi-floor facility layout problem has been divided into two parts, the master problem and the sub-problem. In order to test the developed Dantzig-Wolfe and Benders decomposition algorithms, a total of 8 problems were solved, 5 of which were solved in the literature and 3 of which were adapted to the MFLP in this study. When the experimental results are examined, it is seen that the developed Dantzig-Wolfe and Benders decomposition algorithms have found better solutions for all of 5 problems. Considering the test problem deficiencies in the literature, a total of 140 problems were developed and the solutions of the Dantzig-Wolfe and Benders decomposition algorithm were shown. The generated test problems were solved with the developed Dantzig-Wolfe and Benders decomposition algorithms. Real life application has also been carried out within the scope of the thesis. In this context, an oil production facility was examined, modeled and solved with developed algorithms. As a result of the solution, the facility layout has been improved by 7.5%