Çok tesisli bütünleşik üretim ve dağıtım çizelgeleme problemleri için çözüm yöntemleri

Abstract

Günümüzde firmalar diğer firmalarla rekabet edebilmek için üretim ve dağıtım operasyonlarını birlikte yürütmek zorundadır. Üretim faaliyetleri, müşteri siparişlerinin tesis içerisindeki işlem sıraları ve bu işlemlerin çizelgelenmesi operasyonlarını, dağıtım faaliyetleri ise üretilen ürünlerin müşterilere teslim sürecini kapsamaktadır. Zamana duyarlı (bozulabilir) ürünler, üretimi tamamlandıktan sonra kısıtlı bir zaman diliminde müşteriye teslim edilmek zorundadır. Bozulabilir ürünler için bütünleşik bir yaklaşımın uygulama alanlarına örnek olarak gazete, gıda ürünleri, hazır beton karışımları, nükleer ilaç ve endüstriyel yapıştırıcı malzemeleri üretim ve dağıtımı verilebilir. Literatürde üretim planlama ve dağıtım planlamasının ayrı ayrı ele alındığı yaklaşım çok uzun yıllardır çalışılmasına rağmen bütünleşik üretim ve dağıtım çizelgeleme problemi yaklaşık 20 yıldır yoğun olarak çalışılmaktadır. Bu çalışmaların çok büyük bir kısmında ise bozulabilir ürünler göz önüne alınmamıştır. Oysa bu tarz bozulabilir ürünlerin üretim ve dağıtımının planlanması, yaşanacak gecikmelerde ürünlerin kısmen veya tamamen değerlerini yitirmelerine yol açacağından, çok daha önemlidir. Tez kapsamında literatürde Bütünleşik Üretim ve Dağıtım Çizelgeleme (BÜDÇ) Problemi olarak adlandırılan problem ele alınmıştır. Bu problem bünyesinde makine çizelgeleme ve araç rotalama problemlerini barındırmaktadır. Çok sayıda çeşidi olan BÜDÇ problemi ele alınırken rotalama kararları da göz önüne alınmıştır. Rotalama kararlarının göz önüne alındığı bu problemde dağıtım aşamasında birden fazla müşterinin ziyaret edilmesine izin verilmektedir. Tez kapsamında literatürde daha önce ele alınmamış olan BÜDÇ problemleri incelenmiştir. Tez çalışmasında ilk olarak sistemde birden fazla tesisin bulunduğu ve müşterilere her tesiste bulunan tek araçla hizmet edilen Çok Tesisli ve Tek Araçlı Bütünleşik Üretim ve Dağıtım Çizelgeleme Problemi (ÇT_TA_BÜDÇ) ele alınmıştır. Problemin çözümü için öncelikle bir matematiksel model geliştirilmiştir. Hem makine çizelgeleme hem de araç rotalama problemi NP-zor problem sınıfında yer aldığı için BÜDÇ probleminin de NP-zor yapıda olduğu bilinmektedir. Bu nedenle büyük boyutlu problemlerin çözümü için daha kısa sürelerde optimal ya da optimale yakın çözümler elde edilebilmesi amacıyla Değişken Komşu Arama (DKA) Algoritması geliştirilmiştir. Geliştirilen matematiksel model ve DKA algoritması 6 farklı parametre üzerinden değerlendirilmiş ve sonuçlar karşılaştırılmıştır. Geliştirilen 2592 adet test probleminin matematiksel model ile çözülmesi sonucunda 7200 saniye süre sınırı içerisinde 833 adet test probleminde uygun bir çözüm elde edilememişken DKA algoritması ile tüm problemler için uygun bir çözüm bulunmuştur. Matematiksel model ile 74 adet test probleminde optimal sonuçlar elde edilmiştir ve bu problemlerin hepsi 10 müşterili problemlerdir. Optimal sonuçların elde edildiği problemler için ortalama çözüm süresi 3085 saniyedir. DKA algoritması ile matematiksel model ile elde edilen sonuçlar bir saniyenin altında bir sürede elde edilmiştir. Matematiksel model ile DKA algoritmasının sonuçları karşılaştırıldığı zaman elde edilen Yüzde Sapma Değeri (YSD) ortalama %15.16 olarak hesaplanmıştır. Matematiksel modelin çözümü için gereken süre ortalama 7083 saniye iken bu süre DKA algoritmasında yaklaşık 70 saniyedir. DKA algoritmasını hem süre hem de performans açısından çok daha iyi sonuçlar sağlamaktadır. Tez çalışmasında çalışılan bir diğer problem ise yine sistemde birden çok tesisin bulunduğu ve tesislerde de birden çok aracın mevcut olduğu Çok Tesisli ve Çok Araçlı Bütünleşik Üretim ve Dağıtım Çizelgeleme Problemi (ÇT_ÇA_BÜDÇ)'dir. Problemin çözümü için ilk problemde olduğu gibi öncelikle bir matematiksel model geliştirilmiştir. Geliştirilen matematiksel model geliştirilen geçerli eşitsizlikler ile kuvvetlendirilmiştir. Büyük boyutlu problemler için daha kısa sürelerde optimal ya da optimale yakın çözümler elde edilebilmesi amacıyla Memetik Algoritma (MA) geliştirilmiştir. ÇT_ÇA_BÜDÇ için gerçekleştirilen deneysel çalışmalar farklı parametre seviyeleri için ele alınmış ve sonuçlar raporlanmıştır. 2592 adet test probleminin 1283 adedinde uygun çözümler elde edilmiştir. Matematiksel modele göre elde edilen YSD değeri %0.48 olarak hesaplanmıştır. Bu sonuçların elde edilebilmesi için geçen yaklaşık ortalama süre 4920 saniyedir. Optimal çözümler ise yaklaşık ortalama 539 saniyede elde edilmiştir. MA ile bu çözümlerin elde edilmesi için gereken ortalama süre 3 saniyedir. Bu da algoritmanın ne kadar hızlı ve doğru sonuçlar verdiğini göstermektedir. Problemlerin MA ile çözümünden elde edilen en küçük değerlerin matematiksel model ile aralarındaki farka göre matematiksel model ve MA birbirine çok yakın sonuçlar vermektedir. Elde edilen en küçük değerler göz önüne alındığında MA %0.08 daha iyi sonuç vermektedir. MA ile elde edilen 5 farklı çözümün ortalaması göz önüne alındığında ise matematiksel model çözümlerinin ve MA çözümlerinden %0.01 daha iyi olduğu söylenebilir. Aynı ya da çok yakın sonuçlara MA ile çok kısa sürelerde ulaşılması mümkündür. MA algoritmasının çözümü için gereken süre en küçük 0.01 saniye iken en uzun sürede çözülen problem 26 saniyede çözülmüştür. Ayrıca MA ile tüm problemler için uygun bir çözüm elde edilmişken matematiksel model ile çözüm elde edilemeyen 1309 adet problem mevcuttur. Bu nedenle MA'nın matematiksel modele göre çok daha başarılı olduğu söylenebilir. Müşteri sayısı arttıkça matematiksel model ile uygun çözüm elde etmek zorlaşırken MA ile matematiksel modelden çok daha iyi sonuçlar elde edilmiştir. Matematiksel model ile 50 müşterilik 5 problem için uygun bir çözüm elde edilmiş bu problemlerin YSD değeri %11.03 olarak hesaplanmıştır. MA ile bu 5 problem için %7.17 daha iyi sonuçlar elde edilmiştir. Diğer tüm parametreler için MA ile elde edilen en küçük değerler matematiksel model ile elde edilen değerlerden daha iyidir.

Nowadays, companies must carry out production and distribution operations together to compete with other companies. While the production activities include the order of operations of customer demands within the facility and the scheduling of these operations, distribution activities include the process of delivering the products to customers. One of these operations is time sensitive products. Time-sensitive (perishable) products must be delivered to the customer in a limited time, after their production is completed. Newspapers, food products, ready mixed concrete mixes, nuclear medicine, and industrial adhesive materials can be given as examples of application areas of an integrated approach for perishable products. Although production planning and distribution planning are studied separately for many years, the integrated production and distribution scheduling problem has been studied extensively for about 20 years. Perishable products are not considered in most of these studies. However, the planning of the production and distribution of perishable products is more important because of it will cause the products to lose their value partially or completely in delays. In this thesis, the problem has been examined called as Integrated Production and Outbound Distribution Scheduling (IPODS) Problem in the literature. This problem includes machine scheduling and vehicle routing problems and has many variants. In this study, routing decisions are also considered allowing to visit more than one customer during the same tour. In this thesis, IPODS problems that have not been dealt with before in the literature have been examined. As a first problem, the Integrated Production and Outbound Distribution Scheduling Problem with Multiple Plants and Single Vehicle (IPODS_MP_SV) is discussed. In this problem, there are more than one plant in the system and customers are served with a single vehicle in each facility. A mathematical model is developed to solve the problem firstly. The Variable Neighborhood Search (VNS) Algorithm has been developed to obtain optimal or near-optimal solutions in a shorter time for the solution of large-scale problems. Developed mathematical model and the VNS algorithm are evaluated with 6 different parameters and compared the results. For the developed 2592 test problems, although the mathematical model could not be solved 833 test problems, the VNS algorithm found a feasible solution for all problems. Optimal results are obtained in 74 test problems with the mathematical model, and all these problems are in the case of 10 customers. The average solution times for problems with optimal results is 3085 seconds. The results obtained with the VNS algorithm, and the mathematical model were obtained in less than 1 seconds. When the results of the mathematical model and the VNS algorithm is compared, the difference between the GAP values is calculated as 15.16% on average. While the time required for the solution of the mathematical model is 7083 seconds on average, this time is about 70 seconds in the VNS algorithm. The VNS algorithm provides much better results both in terms of time and performance. Another study of the thesis is The Integrated Production and Outbound Distribution Scheduling Problem with Multiple Plants and Multiple Vehicles (IPODS_MP_MV). This problem includes many plants in the system, and more than one vehicle in these plants. For the solution to the problem, firstly a mathematical model was developed as in the first problem. The developed mathematical model is strengthened by the valid inequalities. Since the IPODS problem is known to be NP-hard class, the Memetic Algorithm (MA) has been developed to obtain optimal or near-optimal solutions for large-sized problems in a shorter time. Test instances for the IPODS_MP_MV are examined for different parameters and the results are reported. Optimal or feasible solutions are obtained in 1283 problems of 2592 test problems. The GAP value obtained according to the mathematical model was calculated as 0.48%. The GAP value is very close to "0" indicates that these results very close to the optimal result are obtained. The average time to obtain these results is 4920.55 seconds in mathematical model. Optimal solutions were obtained in an average of 538.98 seconds in mathematical model. The average time required to obtain these solutions with the MA is 3 seconds. This shows how fast and accurate results the algorithm gives. Considering that the smallest values obtained with MA, MA gives 0.08% better results. Considering that the average of 5 different solutions obtained with MA, it can be said that the mathematical model solutions 0.01% better than MA solutions. It is possible to say the same or very close results in a very short time with MA. The problems are solved by the MA algorithm at least 0.01 seconds, at most 26 seconds. In addition, while a feasible solution is obtained for all problems with MA, there are 1309 problems that cannot be solved with the mathematical model. Therefore, it can be said that the MA algorithm is more efficient than the mathematical model. As the number of customers increases, while it becomes difficult to obtain a feasible solution with the mathematical model, obtained much better results with MA. With the mathematical model, a feasible solution was obtained for 5 problems within the case of 50 customers, and the GAP value of these problems was calculated as 11.03%. 7.17% better results were obtained for these 5 problems with MA.