A study on uniform parallel machine scheduling with sequence dependent setup times
Sıraya bağımlı kurulum süreleri ile tek tip paralel makine çizelgelemesi üzerine bir çalışma
- Tez No: 713433
- Danışmanlar: DOÇ. DR. AYHAN ÖZGÜR TOY, PROF. DR. LEVENT KANDİLLER
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: paralel makine çizelgelemesi, sıraya bağlı kurulum süresi, tam-etkenli tasarım, sezgisel yöntem, tek tip makine, toplam tamamlanma süresi, parallel machine scheduling, sequence-dependent setup time, full factorial design, randomized heuristic, uniform machines, total completion times
- Yıl: 2022
- 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ı: 90
Özet
Çizelgeleme problemleri; operasyon yönetimi, bilgisayar bilimi ve bilgi sistemleri dahil olmak üzere birçok akademik disiplinde karar vermek için gereklidir. Çoğu çizelgeleme problemi güçlü anlamda NP-zor olduğundan, kesin algoritmalar ve verimliliklerinin nasıl ölçeklendiği konusunda sınırlı araştırma vardır. Bu çalışmada, maksimum tamamlama süresini en aza indirmek için sıraya bağlı kurulum süreleriyle tek tip paralel makine çizelgeleme problemini ele alıyoruz. Problemimizi açık bir şekilde tanımlayan ve küçük boyutlu problemler için en uygun çözümleri elde etmek için kullanılabilecek bir tam sayılı problem formülasyonu sunuyoruz. Sonrasında, problemimiz NP-zor olduğundan, iyileştirme alt rutini ile rastgele bir buluşsal yöntem öneriyoruz. Hesaplamalı bir çalışma yoluyla önerilen sezgisel yöntemin performansı 320 örnekle test edilmiştir. Bu örnekleri, beş farklı faktörlü deneyin tam faktöriyel tasarımını (DOE) kullanarak oluşturduk. Hesaplamalı çalışmamız, önerilen matematiksel modelin ortalama 22.88 dakika sürdüğünü ve sezgisel algoritmanın bu sonuçları yalnızca 0.062 dakikada elde ettiğini göstermektedir. Sezgisel yöntem sonuçları ile matematiksel model sonuçları karşılaştırıldığında, CPLEX yazılımında yapılan sezgisel yöntem ortalama olarak yaklaşık %4 Gap değerine sahiptir. Ayrıca, iyileştirme adımının sezgisel yöntemin genel performansına katkısı %73,34'tür.
Özet (Çeviri)
Scheduling problems are essential for decision-making in many academic disciplines, including operations management, computer science, and information systems. Since many scheduling problems are NP-hard in the strong sense, there is only limited research on exact algorithms and their efficiency when implemented on parallel computing architectures. This master's thesis considers the uniform parallel machine scheduling problem with sequence-dependent setup times to minimize the maximum completion time (makespan). We present an IP formulation, which clearly describes our problem and can be used to obtain optimal solutions for small-sized problems. As our problem is NP-hard, we propose a randomized heuristic with an improvement subroutine. The performance of the proposed heuristic through a computational study was tested with 320 instances. We created these instances using the full factorial design of experiment (DOE) with five different factors. Our computational study indicates that the proposed mathematical model takes 22.88 minutes on average, and the heuristic algorithm achieves these results only in 0.062 minutes. The average solutions obtained with the heuristic have an approximately 4% Gap value for average CPLEX solutions. Also, the contribution of the improvement subroutine step to the overall performance of the heuristic is 73.34%.
Benzer Tezler
- Sıra bağımlı hazırlık süreli, makine uygunluk kısıtları olan benzer paralel makine çizelgeleme problemi için sezgisel bir algoritma
A heuristic algorithm for uniform parallel machine scheduling problems with sequence dependent setup time, machine eligibility restrictions
FATİH FIRAT
Yüksek Lisans
Türkçe
2021
Endüstri ve Endüstri MühendisliğiEskişehir Osmangazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. MÜJGAN SAĞIR
- How cryptographic implementations affect mobile agent systems
Şifreleme gerçekleştirmelerinin gezgin aracı internet sistemlerini nasıl etkilediği
İSMAİL ULUKUŞ
Yüksek Lisans
İngilizce
2003
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiSistem ve Kontrol Mühendisliği Ana Bilim Dalı
PROF. DR. EMİN ANARIM
- Parallel machine scheduling to minimize total cost functions
Paralel makina çizelgelemesinde toplam maliyet fonksiyonlarının enazlanması
MERAL AZİZOĞLU
Doktora
İngilizce
1994
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ÖMER KIRCA
- Fixed job scheduling on uniform parallel machines
Bir biçimli paralel makinalarda sabit iş çizelgelemesi
ÖZGÜN BARIŞ BEKKİ
Yüksek Lisans
İngilizce
2003
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF.DR. MERAL AZİZOĞLU
- Minimization of mean weighted flowtime on parallel processors
Paralel makinalarda ortalama ağırlıklı iş akış zamanlarının enazlanması
ÖZLEM AKSOY
Yüksek Lisans
İngilizce
1993
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. SUNA KONDAKÇI (KÖKSALAN)