New greedy algorithms to optimize the curriculum-based course timetabling problem
Müfredat bazlı ders zamanlama tablosu çizelgeleme problemi eniyilemesi için yeni açgözlü algoritmalar
- Tez No: 679100
- Danışmanlar: DR. ÖĞR. ÜYESİ BİLGE SAY, DOÇ. DR. TANSEL DÖKEROĞLU
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2021
- Dil: İngilizce
- Üniversite: Atılım Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 104
Özet
Bu tez,“Ders Zaman Çizelgesi Oluşturma”probleminin bir alt versiyonu olarak bilinen“Müfredata Dayalı Ders Zaman Çizelgesi Oluşturma”(CB-CTT) probleminin optimizasyonu için yeni açgözlü algoritmalar sunmaktadır. Çalışmanın temel amacı, sert kısıtlamaların (uygulanabilir çözümler) doğruluğunu korurken, yumuşak kısıt ihlallerinin toplam sayısını en aza indirmektir. Problem NP-Zor bir problem olduğundan ve büyük örneklerinin pratik zamanlarda çözülmesi için çok uzun süreler gerektirdiğinden, birkaç milisaniye içinde kabul edilebilir sonuçlar üreten açgözlü algoritmalar, arama yapmak için saatler süren eniyileme süreleri harcayan kaba kuvvet ve evrimsel algoritmalara göre daha iyi bir alternatif oluşturmaktadır. Pek çok açgözlü algoritma geliştirildi ve tek bir sezgisel yöntem kullanmak yerine, aynı problem örneğinde 120 açgözlü yöntem tanımlanıp çalıştırıldı ve daha iyi sonuçlar rapor edildi. Açgözlü algoritmaların maliyetlerinin ortalama olarak karşılaştırılabilir olması gerektiğini belirten Ücretsiz Öğle Yemeği Yok (No Free Lunch) Teorisine uygun olarak en iyi sonuçlar çalışmanın sonunda rapor edilmiştir. Önerdiğimiz açgözlü algoritmalarımız; En Büyük-Önce, En Küçük-Önce, En İyi-Uygun-Önce, Ortalama-ağırlıklı Önce sezgisel yöntemleri ve En Yüksek Kullanılamayan ders-ilk sezgisel yöntemlerini kullanarak dersleri kapasitelerine göre sıralanan mevcut odalara atar. Önerilen algoritmamızın performansını değerlendirmek için, İkinci Uluslararası Zaman Çizelgesi Oluşturma Yarışması (ITC-2007) setinden 21 problem örneği üzerinde deneyler yapıldı. Deneysel sonuçlar, önerilen açgözlü algoritmaların, önemli ölçüde azaltılmış yumuşak kısıtlama değerleriyle sıfır sert sınırlama ihlallerini bildirebileceğini doğrulanmaktadır.
Özet (Çeviri)
This thesis presents a set of new greedy algorithms for the optimization of the well-known“Curriculum-Based Course Timetabling”(CB-CTT) problem, which is a sub-type of the“Course Timetabling”problem. The main goal of the study is to minimize the total number of soft constraint violations while preserving the satisfaction of hard constraints (feasible solutions). Since the problem is NP-Hard and large instances of the problem cannot be solved in practical times, greedy algorithms that work to produce acceptable results in a few seconds are good alternatives to brute-force and evolutionary algorithms that spend hours of execution times to search for an optimal solution. Instead of using a single heuristic as it is performed by many greedy algorithms, we define and execute 120 greedy heuristics on the same problem instance simultaneously and report the overall best result, which would produce better results than which is obtainable by using a single greedy heuristic algorithm. The best results with respect to the No Free Lunch Theory, which states that the costs of greedy heuristics should be comparable on average, are reported. Our proposed greedy algorithms use the Largest-First, Smallest-First, Best-Fit, Average-weight first heuristics, and the Highest Unavailable course-first heuristics simultaneously while assigning the courses to the available rooms that are ordered by their capacity according to the above four different criteria. In order to evaluate the performance of our proposed algorithm, we carry out experiments on 21 problem instances from the Second International Timetabling Competition (ITC-2007) benchmark set. The experimental results verify that the proposed greedy algorithms can report zero hard constraint violations (feasible solutions) for 18 problems with significantly reduced soft-constraint values.
Benzer Tezler
- Mobil nesnelerin interneti için yeni nesil hücresel ağ tabanlı ağ dilimleme
Next generation cellular network based network slicing for the mobile internet of things
WAFA HAMDI
Doktora
Türkçe
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. HASAN BULUT
PROF. DR. ORHAN DAĞDEVİREN
- Sıkıştırılmış algılamada sezgisel algoritmaların kullanımına dayalı yöntemlerin incelenmesi ve geliştirilmesi
Analyzing and development of heuristic algorithms in compressed sensing
MURAT EMRE ERKOÇ
Yüksek Lisans
Türkçe
2017
Elektrik ve Elektronik MühendisliğiErciyes ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. NURHAN KARABOĞA
- On balancing social networks
Sosyal ağların dengelenmesi
ARANIYOS TEREFE WELDEGEBRIEL
Doktora
İngilizce
2019
Matematikİstanbul Teknik ÜniversitesiMatematik Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ BURAK YILDIRAN STODOLSKY
- New solution techniques for no-wait permutation flowshop scheduling problems
Beklemesiz permütasyon akış tipi çizelgeleme problemleri için yeni çözüm teknikleri
DAMLA YÜKSEL
Doktora
İngilizce
2024
Endüstri ve Endüstri MühendisliğiYaşar ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. LEVENT KANDİLLER
- Minimizing latency in post-disaster debris removal
Afet sonrası enkazın kaldırılmasındaki gecikmeyi minimize etmek
MERAJ AJAM