New solution techniques for no-wait permutation flowshop scheduling problems
Beklemesiz permütasyon akış tipi çizelgeleme problemleri için yeni çözüm teknikleri
- Tez No: 904098
- Danışmanlar: PROF. DR. LEVENT KANDİLLER
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2024
- Dil: İngilizce
- Üniversite: Yaşar Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 236
Özet
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.
Özet (Çeviri)
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.
Benzer Tezler
- Exact approaches for the no wait flowshop problem
Başlık çevirisi yok
AHMET EMİR TUZCU
Yüksek Lisans
İngilizce
2019
Endüstri ve Endüstri MühendisliğiÖzyeğin ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ÖMER ERHUN KUNDAKCIOĞLU
- Çifte kaynak kısıtlı grup teknolojisi üretim sistemlerinin bozucu faktörlere dayanıklı tasarımı
Robust design of dual resource constrained group technology production systems
MUSTAFA AKHUN
Doktora
Türkçe
1999
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiPROF. DR. M. BÜLENT DURMUŞOĞLU
- Vokal kord paralizlerinde tiroplasti implantı'nin tasarımı ve geliştirilmesi
Design and development of thyroplasty implant for vocal cord paralysis
FATİH ÇİFTÇİ
Yüksek Lisans
Türkçe
2017
BiyomühendislikYıldız Teknik ÜniversitesiBiyomühendislik Ana Bilim Dalı
YRD. DOÇ. DR. CEM BÜLENT ÜSTÜNDAĞ
YRD. DOÇ. DR. RAŞİT CEVİZCİ
- İhracat finansmanının yapısı ve Türkiye'de uygulanan ihracat finansmanı teknikleri
The Financial structure of export and the financial techniques of export used in Turkey
IŞIL AVUNDUK
Yüksek Lisans
Türkçe
1993
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. RAMAZAN EVREN
- Öneri sistemleri ve grup çalışma yazılımı kullanılarak yapılan bir uygulama
Başlık çevirisi yok
MURAT BİRCANER
Yüksek Lisans
Türkçe
1998
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ALPASLAN FIĞLALI