New solution techniques for no-wait permutation flowshop scheduling problems / Beklemesiz permütasyon akış tipi çizelgeleme problemleri için yeni çözüm teknikleri

Abstract

Beklemesiz Permütasyon Akış Tipi Çizelgeleme Problemi (NWPFSP) çizelgeleme problemlerinin bir varyantı olup bu problem tipinde işler, makineler arasında bekleme süreleri olmadan makinelerden sabit bir sırayla geçmelidir. Bu tez, Beklemesiz Permütasyon Akış Tipi Çizelgeleme Problemleri için yenilikçi çözüm tekniklerini araştırmaktadır. Bu tezin ana katkıları iki yönlüdür: tek-hedefli optimizasyon ve iki-kriterli optimizasyon. Tek-hedefli optimizasyon kapsamında, tamamlanma süresi, toplam akış süresi ve toplam gecikmeyi ayrı ayrı minimize etmeye yönelik beş matematiksel model formülasyonunu incelemektedir — üçü Karma-Tamsayılı Doğrusal Programlama (MILP) ve ikisi Kısıtlama Programlama (CP) kullanılarak geliştirilmiştir. Karma-Tamsayılı Doğrusal Programlama modellerden bir tanesi, bu hedeflere ulaşmak için geçerli eşitsizliklerle güçlendirilmiştir. Ayrıca, tamamlanma süresi, toplam akış süresi, toplam gecikme ve geciken işlerin sayısını ayrı ayrı optimize etmek için En Kısa Yol (SP) algoritmasına dayanan yeni bir Alt Sınır (LB) mekanizması geliştirilmiştir. Daha sonra, Beklemesiz Permütasyon Akış Tipi Çizelgeleme Problemlerinde geciken işlerin sayısını minimize etmek amacıyla bir Karma-Tamsayılı Doğrusal Programlama (MILP) sınıfına ve bir Kısıtlama Programlama (CP) sınıfına ait iki matematiksel model incelenmiştir. Geciken işlerin sayısını enazlamak için yeni bir üst sınır olan Feda Et ve Yeniden Düzenle Sezgisel Algoritması (SRH) önerilmiştir. Beklemesiz Permütasyon Akış Tipi Çizelgeleme Problemlerinde geciken işlerin sayısını optimize etmek, geç kalma ile ilgili performans ölçütlerini iyileştirmek için de önemli olan yüksek kaliteli teslim tarihleri gerektirir. Bu sorunu çözmek amacıyla, yüksek kaliteli teslim tarihleri üretmek için yeni bir mekanizma geliştirilmiştir. Bu mekanizma, Feda Et ve Yeniden Düzenle Sezgisel Algoritmasını (SRH) içeren, hem pratik hem de etkili teslim tarihleri üretir. İki-kriterli optimizasyon kapsamında ise, Beklemesiz Permütasyon Akış Tipi Çizelgeleme Problemleri, iki-kriterli bir kombinatoryal optimizasyon problemi olarak ele alınır ve toplam akış süresi ile tamamlanma süresini aynı anda minimize etmeyi amaçlar: İki-Kriterli Beklemesiz Permütasyon Akış Tipi Çizelgeleme Problemleri (BI-CRI NWPFSPs). İlk olarak, İki-Kriterli Beklemesiz Permütasyon Akış Tipi Çizelgeleme Problemlerini (BI-CRI NWPFSPs) ele almak amacıyla bir Karma-Tamsayılı Doğrusal Programlama (MILP) model formülasyonu incelenmiştir. Bunun ardından, İki-Kriterli Beklemesiz Permütasyon Akış Tipi Çizelgeleme Problemleri (BI-CRI NWPFSPs) için Q-öğrenme destekli algoritmalar geliştirilmiştir. Q-öğrenme, eylem seçimlerini yönlendirmek için kullanılan tanınmış bir pekiştirmeli öğrenme tekniğidir ve bu sayede yinelemeli meta-sezgisel süreçte rastgele keşif ihtiyacını azaltır. Geliştirilen Q-öğrenme destekli meta-sezgiseller, Q-öğrenme ile İki-Kriterli Tekrarlı Açgözlü Algoritma (BC-IGQL) ve Q-öğrenme ile İki-Kriterli Blok Ekleme İyileştirici Algoritma (BC-BIHQL) olarak adlandırılmıştır. Bu algoritmaların performansı, diğer modern sezgisel yaklaşımların performanslarıyla karşılaştırılmıştır. Böylece, bu tez, hem tek-hedefli hem de iki-kriterli senaryolar için yeni çözüm teknikleri geliştirerek Beklemesiz Permütasyon Akış Tipi Çizelgeleme Problemleri (NWPFSP) literatürünü zenginleştirmektedir. No-Wait Permutation Flowshop Scheduling Problem (NWPFSP) is a scheduling problem variant where jobs must proceed through machines in a fixed order without waiting times between operations. This thesis explores innovative solution techniques for the NWPFSPs. The primary contributions of this thesis are twofold: single-objective optimization and bi-criteria optimization. For single-objective optimization, this thesis examines five mathematical model formulations — three using Mixed-Integer Linear Programming (MILP) and two using Constraint Programming (CP) — focused on separately minimizing makespan, total flow time, and total tardiness. One MILP model is enhanced with valid inequalities to address these objectives. A new Lower Bound (LB) mechanism based on the Shortest Path (SP) algorithm is developed to optimize makespan, total flow time, total tardiness, and the number of tardy jobs separately. Following that, two mathematical models, one belonging to the MILP class and the other to the CP class, have been studied for the number of tardy job minimization in NWPFSPs. A novel upper bound, the Sacrifice and Rearrange Heuristic (SRH), is introduced to minimize the number of tardy jobs. Optimizing the number of tardy jobs in NWPFSPs requires high-quality due dates, as they are crucial for improving performance metrics related to lateness. A new mechanism for generating high-quality due dates has been developed to address this. Incorporating the Sacrifice and Rearrange Heuristic (SRH), this mechanism ensures practical and effective due dates. For bi-criteria optimization, the NWPFSP is approached as a combinatorial optimization problem with two objectives, aiming to minimize total flow time and makespan simultaneously: Bi-Criteria No-Wait Permutation Flowshop Scheduling Problems (BI-CRI NWPFSPs). Initially, an MILP model formulation is explored to address BI-CRI NWPFSPs. Following this, Q-learning-guided algorithms are developed for Bi-CRI NWPFSPs. Q-learning, a well-known reinforcement learning technique, is employed to direct action selection, thereby reducing the need for random exploration during the iterative metaheuristic process. The developed Q-learning guided metaheuristics are Bi-Criteria Iterated Greedy Algorithm with Q-Learning (BC-IGQL) and Bi-Criteria Block Insertion Heuristic Algorithm with Q-Learning (BC-BIHQL). The performance of these algorithms is compared with other state-of-the-art approaches. Thus, this thesis advances the literature on the NWPFSPs by developing new solution techniques for both single-objective and bi-criteria scenarios.