Müfredat tabanlı üniversite ders çizelgeleme problemi için bir sürü zekası yaklaşımı

Abstract

Üniversite ders çizelgeleme problemi popüler zaman çizelgeleme problemlerinden biri olduğundan çok sayıda araştırmacının ilgisini çekmiştir. NP-Zor problemler grubunda yer alan bu problemin deterministik yöntemlerle çözümü verimli değildir ve bu nedenle sezgisel ve meta-sezgisel yöntemler önerilmektedir. Sürekli uzaydaki optimizasyon problemlerinin çözümü için önerilen meta-sezgisel yöntemlerinden birisi olan ABC algoritması bal arılarının yiyecek aramada kullandığı sürü zekasından ilham alır. Bu algoritma sürekli uzayda diğer meta sezgisel yöntemlerden daha iyi sonuçlar üretmektedir. Ayrık uzay problemlerinin, örneğin üniversite ders çizelgeleme probleminin çözümü için ABC'nin uyarlanması işleminde komşuluk kavramının tanımlanmasına ve kullanılmasına ihtiyaç duyulur. Bu tezde ABC algoritması üniversite ders çizelgeleme problemi türlerinden birisi olan müfredat tabanlı üniversite ders çizelgeleme probleminin (CB-CTT) çözümü için kullanılmıştır. ITC-2007 yarışmasının üçüncü bölümünde yer alan bu problemin çözümünde, temel ABC algoritmasının komşu üretimine değişiklikler yapılmış ve yerel arama yöntemi eklenmiştir. Problem için geliştirilen standart veri setleri üzerinde farklı araştırmacıların farklı yöntemlerle elde ettikleri sonuçları karşılaştırabilmesi sağlandığından dolayı, ITC-2007 probleminin 21 örnek veri seti üzerinde elde ettiğimiz sonuçlar, yarışmada dereceye giren en iyi 5 sonuç ile kıyaslanabilirdir. The University Course Timetabling Problem is one of the most famous scheduling problems, which has attracted many researchers to solve the problem. This problem is located in NP-Hard problems group and so deterministic methods are not efficient to solve it and heuristic and meta-heuristic methods are suggested to do so One of the meta-heuristic methods suggested to solve optimization problems in continuous environments that is inspired by the swarm intelligence of honey bees in search for the food, is called ABC algorithm. This algorithm could achieve good results compared to other meta-heuristic methods in a continuous environment. The task of adapting ABC to solve problem in discrete environments, e.g. University Course Timetabling, needs defining the neighborhood concept and applying this concept to find the better solutions. In this thesis, ABC has been used to solve one of popular types of University Course Time-Tabling problems which is Curriculum Based University Course (CB-CTT) Time-Tabling problem. It was the third type of Time-Tabling problems in ITC-2007 competition. The adaption of ABC to solve this problem gets the advantage of some improvements in neighbor generation and using local search technique, compared to the original ABC algorithm. Having a benchmark case study for this problem helps researchers to work on a standard dataset and makes it easy to compare different results obtained by different researchers with different approaches. Our achieved results on 21 datasets of ITC-2007 is comparable to five winners of this competition