Studies on different types of facility layout problems

Abstract

Facility layout problems are applied to find the best arrangement of facilities in manufacturing and service environments. The main goal of these problems is to minimize the total weighted travelled distance of the facilities by the travelled frequency of them. The difficult part is how to measure these distances. A frequently used approximation is the Manhattan distance. However, it is significantly shorter than the real distance in many cases. This thesis suggests an exact mathematical model for closed loop layout that uses real distances instead of Manhattan distance. Many feasible solutions are generated for benchmark problems that are competitive with the solutions provided by metaheuristics. A generalization of multi-dimensional scaling (MDS) method is developed to reconstruct the layout problems from their distance matrix. MDS is a well-known method used in statistics to explore the hidden dependency among data. The reconstruction done by MDS is completely successful if the distance used in layout problems is of Euclidean type. Therefore the generalized MDS provides the opportunity to reconstruct the layout problems with any distance type. The results show that only the Quadratic Assignment Problems which are the models of real layout problems can be reconstructed successfully. The thesis also suggests a mathematical model based on Travelling Salesman Problem and its Dantzig-Fulkerson-Johnson formulation to rearrange the departments of a supermarket in order to increase the travelled path of customers and motivate them to buy more items. The study was done in one of the biggest supermarket chain of Hungary by considering the purchasing items of more than 13,000 customers. The computational experiences show that the total travelled distance can be increased by approximately 4 percent.Öz:Tesis içi yerleşim, tesislerin üretim ve hizmet ortamlarında en iyi iç düzenlemesini bulmak için uygulanmaktadır. Bu problemlerin temel amacı seyahat sıklığına göre tesislerin toplam ağırlıklı seyahat mesafesini en aza indirmektir. Zor olan kısmı bu mesafelerin nasıl ölçüldüğü ile bağlantılıdır. Manhattan mesafesi sık kullanılan bir yaklaşıklamadır. Ancak birçok durumda gerçek mesafeden anlamlı derecede kısadır. Bu tez, kapalı döngü iç yerleşimi için Manhattan mesafesi yerine gerçek mesafe kullanmakta olan kesin sonuç veren bir matematiksel model önermektedir. Birçok uygulanabilir çözüm sezgi ötesi yöntemlerle sağlanan çözümlere rakip olabilecek denektaşı problemler için oluşturulmuştur. Genelleştirilmiş bir çok boyutlu ölçekleme metodu, tesis içi yerleşim problemlerini mesafe matrislerinden yeniden kurmak için geliştirilmiştir. Çok boyutlu ölçekleme, veriler arasındaki gizli bağlantıyı keşfetmek için istatistikte kullanılan bilinen bir yöntemdir. Çok boyutlu ölçekleme ile yeniden kurma, iç yerleşim probleminin öklit türü olması durumunda tamamen başarılıdır. Bu nedenle genelleştirilmiş çok boyutlu ölçekleme herhangi bir mesafe tipi olan iç yerleşim problemlerinin yerinden kurulması fırsatı yaratır. Sonuçlar göstermektedir ki sadece gerçek iç yerleşim problemlerinin modeli olan karesel atama problemleri başarılı bir şekilde yeniden kurulabilmektedir. Bu tez ayni zamanda müşterilerin süpermarkette daha fazla ürün almaları yönünde motive olmaları amacıyla katettikleri mesafeyi artırmak için gezgin satıcı problemi ve onun Dantzig-Fulkerson-Johnson biçimlendirmesini baz alarak süpermarket departmanlarının yeniden düzenlemesini sağlayan bir matematiksel model önermektedir. Bu çalışma Macaristanda bulunan en büyük süpermarket zincirlerinden birinde, 13000‘den fazla müşterinin satın aldığı ürünler dikkate alınarak yapılmıştır. Hesaplamalı denemeler göstermektedir ki toplam seyahat edilen mesafe yaklaşık yüzde 4 oranında artırılabilmektedir.