Müfredat Bazlı Ders Zamanlama Tablosu Çizelgeleme Problemi Eniyilemesi için Yeni Açgözlü Algoritmalar

Abstract

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.

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.