Bütünleşik üretim ve dağıtım çizelgeleme problemleri için çözüm yaklaşımları
Solution approaches for integrated production and distribution scheduling problems
Yazar: ECE ÇETİN YAĞMUR
Danışman: PROF. SAADETTİN ERHAN KESEN
Konya Teknik Üniversitesi / Lisansüstü Eğitim Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2021
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Günümüzde rekabetin işletmelerden çok işletmelerin tedarik zincirleri arasında gerçekleştiği düşünüldüğünde, tedarik zincirinde yer alan fonksiyonların etkin bir şekilde yönetilmesi işletmeler açısından oldukça önemsenmektedir. Üretim ve dağıtım, tedarik zincirinde yer alan iki temel fonksiyondur. Geleneksel yaklaşımda bu fonksiyonlar bireysel olarak değerlendirilmekte ve hiyerarşik olarak ele alınmaktadır. Hiyerarşik bir şekilde alınan bu kararlar sistemin bütünü açısından en iyiyi garanti edememektedir. Bu nedenle tedarik zinciri açısından bütünsel en iyiye ulaşmak için üretim ve dağıtım operasyonlarının bütünleşik bir şekilde ele alınması gerekmektedir. Ekonomik avantajlarının yanı sıra gerçek hayatta üretim ve dağıtım operasyonlarının bütünleşik olarak ele alınmasını zorunlu kılan bazı durumlarla karşılaşılmaktadır. Çabuk bozulan ve zamana duyarlı ürünlerin üretimi ve dağıtımı bu uygulama alanlarından birisidir. 
Yapılan tez çalışmasında operasyonel düzeyde üretim ve dağıtım operasyonlarının bütünleştirilmesi incelenmiştir. Üretim aşamasında üretim çizelgeleme problemini dağıtım aşamasında ise araç rotalama problemini bünyesinde barındıran bu problem literatürde "Bütünleşik Üretim ve Dağıtım Çizelgeleme (BÜDÇ) Problemi" olarak adlandırılmaktadır. Tez çalışmasında BÜDÇ kapsamında üç farklı problem ele alınmıştır. Permütasyon Akış Tipi Üretim Ortamı ile Tek Araçlı Dağıtım Ortamını içeren BÜDÇ (PAT_TA) Problemi olarak ifade edilen ilk problemde siparişlerin seri olarak yerleştirilmiş tüm makineleri aynı sırada ziyaret ettiği permütasyon akış tipi üretim ortamı ve sınırlı kapasiteye sahip tek araçla teslimatlarının yapıldığı bir dağıtım ortamı incelenmiştir. Permütasyon Akış Tipi Üretim Ortamı ile Çok Araçlı Dağıtım Ortamını içeren BÜDÇ (PAT_ÇA) Problemi olarak ifade edilen ikinci problemde ilk problemin daha genel bir hali dikkate alınarak aynı üretim ortamı ile heterojen kapasiteli birden fazla aracın olduğu dağıtım ortamı incelenmiştir. Son olarak; Atölye Tipi Üretim Ortamı ile Çok Araçlı Dağıtım Ortamını içeren BÜDÇ (AT_ÇA) Problemi olarak ifade edilen üçüncü problemde ise siparişlerin makinelerdeki operasyon sıralarının birbirinden farklı olduğu atölye tipi üretim ortamı ve heterojen kapasiteli birden fazla aracın bulunduğu dağıtım ortamı incelenmiştir. Her üç problemde de araç sayısının sınırlı olması nedeniyle bazı müşteri siparişleri belirtilen teslim tarihinden sonra teslim edilebilmekte, dolayısıyla bu siparişler için gecikmeler oluşmaktadır. PAT_TA ve PAT_ÇA Problemlerinde müşterilerin teslim tarihlerinin yeterince büyük olduğu durumda taşıma sürecinin mümkün olan en kısa sürede tamamlanması istenmektedir. Dolayısıyla PAT_TA ve PAT_ÇA Problemleri için amaç, toplam tur zamanı ile toplam gecikme toplamının en küçüklenmesi olarak ele alınmıştır. AT_ÇA Problemi ise çevresel faktörler de probleme dahil edilerek araçlar tarafından havaya salınan toplam CO2 emisyonu ve maksimum gecikmenin en küçüklenmesi şeklinde çok amaçlı bir yapıda incelenmiştir. Her üç problemde de sistemdeki araçlar planlama periyodu boyunca birden fazla kez kullanılabilmektedir. Tez kapsamında incelenen problemler literatürde daha önce çalışılmamıştır ve ilk kez bu tez çalışmasında incelenmiştir. 
PAT_TA Problemi için öncelikle problemin varsayımları ve kısıtları tanımlanarak Karma Tamsayılı Doğrusal Programlama (KTDP) modeli geliştirilmiştir. Ardından problemin NP-zor yapısı nedeniyle büyük boyutlu problemler için makul sürelerde optimal ya da optimale yakın çözümlerin elde edilmesi amacıyla Memetik Algoritma (MA) yaklaşımı önerilmiştir. PAT_TA Problemi için önerilen çözüm yöntemlerinin performanslarını değerlendirmek amacıyla 1080 adet test problemi müşteri sayılarına göre küçük, orta ve büyük boyutlu olmak üzere oluşturulmuştur. İncelenen 1080 örneğin sadece 256 tanesinde CPLEX ile üç saat süre sınırı içerisinde optimal çözüm elde edilebilmiştir. Bu 256 örneğin 243 tanesinde MA ile optimal çözümlere saniyelerle ifade edilen oldukça kısa sürelerde ulaşılmıştır. Orta boyutlu problemlerde CPLEX ve MA'nın göreli performansları birbirlerine oldukça yakınken çözüm süreleri değerlendirildiğinde MA'nın çözüm süresi açısından oldukça etkin olduğu görülmüştür. Büyük boyutlu problemlerde ise CPLEX hiçbir örnekte optimal çözüm elde edememiş bununla birlikte üç saatlik süre sınırı içerisinde CPLEX'in göreli performansı MA'ya göre oldukça düşük bulunmuştur. 
PAT_ÇA Problemi için geliştirilen Karma Tamsayılı Programlama (KTP) modeli doğrusal olmadığından model önce doğrusallaştırma kısıtları ile doğrusal hale getirilmiş ardından PAT_TA Problemi için geliştirilen MA yaklaşımı sistemde birden fazla araç olduğu için PAT_ÇA Problemine göre yeniden uyarlanmıştır. PAT_ÇA Problemi için geliştirilen 1980 test problemi üzerinde CPLEX ve MA'nın performansları değerlendirilmiştir. CPLEX, PAT_TA Problemi için tüm örneklerde üst sınır elde edebilirken PAT_ÇA Problemi için üretilen 720 adet büyük boyutlu örneğin sadece 388 tanesinde verilen süre sınırları içerisinde bir üst sınır elde edebilmiştir. Bununla birlikte PAT_TA Problemi için küçük boyutlu problemlerde CPLEX tüm örnekler için optimal çözümü elde edebilirken PAT_ÇA Problemi için 180 adet küçük boyutlu problemin 145 tanesinde optimal çözüm elde edebilmiştir. Sonuç olarak sistemdeki araç sayısının birden fazla olmasının problem karmaşıklığını artırdığı gözlenmiştir. PAT_ÇA Problemi için önerilen MA ile optimali bilinen 145 örneğin hepsinde optimal değerler saniyelerle ifade edilen oldukça kısa sürelerde bulunmuştur. MA ile CPLEX'in göreli performansları değerlendirildiğinde orta boyutlu problemlerde PAT_TA Problemi için yakın sonuçlar elde edilirken PAT_ÇA Problemi için önerilen MA 10 müşterinin olduğu durumda bile CPLEX'e göre göreli sapma değeri açısından daha başarılı bulunmuş ve müşteri sayısının artmasıyla MA'nın CPLEX'e göreli performansı büyük oranda artış göstermiştir. Geliştirilen MA en büyük boyutlu problemlerde bile bir dakikadan daha kısa bir sürede CPLEX'e göre büyük üstünlük sağlamıştır. 
AT_ÇA Problemi çok amaçlı yapıda Karma Tamsayılı Doğrusal Programlama modeli (KTDP) ile formüle edilmiş ve problemin çözümü için kesin yöntem olarak Artırılmış Epsilon Kısıt Yöntemi (AEKY) uygulanmıştır. AEKY'nin problem boyutu arttıkça yetersiz gelmesi üzerine çok amaçlı optimizasyon problemleri için geliştirilen iki farklı sezgisel yöntem, Baskın Olmayan Sıralama Genetik Algoritma-II (BSGA-II) ve Pareto Yerel Arama (PYA), AT_ÇA Problemine uygulanmıştır. PYA yaklaşımı içerisinde, problemin üretim ortamında değişken komşu arama algoritması kullanılırken dağıtım aşamasında yerel arama yaklaşımına başvurulmuştur. AT_ÇA Problemi için rassal olarak üretilen 624 adet test problemi üzerinde önerilen algoritmaların hem kesin yöntemle hem de birbirleriyle karşılaştırılması yapılmıştır. Çok amaçlı optimizasyon performans kriterleri olarak pareto çözüm sayısı, hipervolüm değerleri ve ortalama çözüm süreleri kullanılmıştır. Sonuçlar değerlendirildiğinde küçük boyutlu örneklerde hem BSGA-II hem de PYA ile elde edilen Pareto yüzeyler AEKY ile elde edilen gerçek Pareto yüzeye oldukça yakın bulunmuştur. Orta ve büyük boyutlu problemlerde ise AEKY ile verilen süre sınırı içerisinde ödünleşim matrisi oluşturulamadığından yalnızca BSGA-II ve PYA'nın birbirine göre performansı değerlendirilmiştir. Sonuçlara göre her üç performans kriteri açısından da on dakikalık süre sınırı içerisinde elde edilen Pareto çözümlere göre BSGA-II, PYA'ya göre daha başarılı bulunmuştur. PYA'nın müşteri sayısındaki artışa oldukça duyarlı olduğu gözlenerek PYA bir saat çalıştırılmıştır. Elde edilen sonuçlar incelendiğinde çözüm süresinin artırılmasının PYA performansını ciddi oranda artırdığı hatta bazı örneklerde PYA'nın BSGA-II'yi geçtiği görülmüştür.

Abstract:
Considering that competition takes place between the supply chains of businesses rather than businesses today, effective management of functions in the supply chain is highly important for businesses. Production and distribution are two main functions in the supply chain. In the traditional approach, these functions are evaluated individually and considered hierarchically. These hierarchically made decisions cannot guarantee optimal in terms of the system. For this reason, production and distribution operations should be handled in an integrated manner to achieve the global optimal in terms of the supply chain. In addition to its economic advantages, it has been inevitable for some cases to consider production and distribution operations in an integrated manner in the supply chain. There are many application areas where production and distribution operations are handled in an integrated manner in real life. Production and distribution of perishable and time-sensitive products is one of these application areas.
In the thesis, the integration of production and distribution operations at the operational level has been examined. This problem, which includes the production scheduling problem in the production phase, and the vehicle routing problem in the distribution phase, is called as "Integrated Production and Distribution Scheduling (IPDS) Problem" in the literature. In the thesis study, three different problems have been addressed within the scope of IPDS. In the problem expressed as the Permutation Flow Shop Production Environment and the Single Vehicle Distribution Environment (PFS-SV) IPDS Problem, a permutation flow shop production environment where orders visit all machines placed in series in the same order and a distribution environment where orders are delivered with a single vehicle with limited capacity are analyzed. In the second problem expressed as the Permutation Flow Shop Production Environment and the Multi Vehicle Distribution Environment (PFS-MV) IPDS Problem, the same production environment and the distribution environment with more than one vehicle with heterogeneous capacity are examined by taking into account the more general form of the first problem. Finally, in the last problem expressed as the Job Shop Production Environment and the Multi Vehicle Distribution Environment (JS-MV) IPDS Problem, the job shop production environment where the operation sequences of the orders are different from each other and the distribution environment with multi vehicles with heterogeneous capacity are examined. Due to the limited number of vehicles in all three types of problems, some customer orders may be delivered after the predefined due date, thus there is tardiness for these orders. In PFS-SV and PFS-MV Problems, when the due dates of the customers are large enough, the distribution process is requested to be completed as soon as possible. Therefore, the objective for PFS-SV and PFS-MV Problems are considered minimizing the sum of total tour time and total tardiness. JS-MV Problem, on the other hand, has been investigated in a multi-objective structure by including environmental factors into the problem, as minimizing the total CO2 emission released into the air by vehicles and minimizing the maximum tardiness. In all three problems, the vehicles in the system can be used more than once during the planning period. All three problems addressed within the scope of the thesis have not been encountered before in the literature and have been examined for the first time in this thesis study.
For PFS-SV Problem, a 	Mixed Integer Linear Programming (MILP) model has been developed by defining the assumptions and constraints of the problem. Due to the NP-hard structure of the problem, the Memetic Algorithm (MA) approach has been proposed to obtain optimal or near-optimal solutions in a reasonable time for big-sized problems. 1080 test instances have been created in small, medium, and big-sized according to the number of customers to evaluate the performance of the solution methods proposed for PFS-SV Problem. In only 256 of the 1080 instances examined, the optimal solution can be obtained with CPLEX within three hours. 243 of these 256 instances, optimal solutions are reached by MA in a very short time expressed in seconds. While relative performances of CPLEX and MA are very close to each other in medium-sized problems, when the solution times are evaluated, it has been seen that MA is very effective in terms of solution time. However, in big-sized problems, CPLEX cannot obtain an optimal solution in any instance and the relative performance of CPLEX within the three-hour time limit is found to be significantly lower than MA.
Since the Mixed Integer Programming (MIP) model developed for PFS-MV Problem is not linear, the model is first linearized with linearization constraints, then the MA approach developed for PFS-SV Problem is adapted according to PFS-MV Problem because there are multi vehicles in the system. The performance of CPLEX and MA are evaluated on the 1980 test instances developed for PFS-MV Problem. While CPLEX can obtain an upper limit in all instances for PFS-SV Problem, for PFS-MV Problem it can obtain an upper limit for only 388 of 720 big-sized instances within the given time limits. Besides, for PFS-SV Problem, CPLEX was able to obtain the optimal solution for all examples, while for PFS-MV Problem it can obtain the optimal solution for 145 of 180 small-sized problems. As a result, it has been observed that the number of vehicles in the system is more than one increases the complexity of the problem. With the proposed MA for PFS-MV Problem, the optimal values in all 145 instances who's optimal are known were found in a very short time, expressed in seconds. When the relative performances of MA and CPLEX are evaluated, close results have been obtained for PFS-SV in medium-sized problems, while the proposed MA for PFS-MV Problem is found to be more successful in terms of relative performance compared to CPLEX even in the case of 10 customers, and with the increase in the number of customers, MA's relative performance to CPLEX has increased substantially. The developed MA outperformed CPLEX even in the biggest problems in less than a minute.
JS-MV Problem has been formulated with a Multi-Objective Mixed Integer Programming model and the Augmented Epsilon Constraint Method (AUGMECON) is applied as the exact method to solve the problem. As the AUGMECON method has become insufficient as the problem size increased, two different heuristic methods, Non-Dominated Sorting Genetic Algorithm-II (NSGA-II) and Pareto Local Search (PLS) have developed for multi-objective optimization problems are applied to JS-MV Problem. In the PLS algorithm, while the variable neighbor search algorithm is applied in the production phase of the problem, the local search approach is used in the distribution phase. The algorithms proposed for JS-MV Problem are compared on 624 randomly generated test instances both with the exact method and with each other. The number of pareto solutions, hypervolume values, and solution times are used as the multi-objective optimization performance criteria. When the results are evaluated, the Pareto fronts obtained with both NSGA-II and PLS approach in small-sized instances are found to be very close to the real Pareto front obtained by AUGMECON. In medium and big-sized problems, since the trade-off matrix cannot be created within the time limit given by AUGMECON, only the relative performance of NSGA-II and PLS to each other has been evaluated. According to the results, NSGA-II is found to be more successful than the PLS compared to the Pareto solutions obtained within the ten-minute time limit in terms of all three-performance criteria. It has been observed that the PLS is very sensitive to the increase in the number of customers, so the PLS is also run for one hour. When the results obtained are examined, it is seen that increasing the solution time significantly increased the performance of the PLS, even in some cases, the PLS has outperformed NSGA-II.