University course timetabling using multi objective genetic algortihms

Abstract

Yapay Zeka alanındaki en ilgi çekici ve heyecan verici konulardan birisi Üniversite Ders Programlamasıdır. Bu sadece problemin çok zor olmasından değil aynı zamanda bu konuda çok çeşitli araştırma yapılmış olmasından da kaynaklanır. Üniversite Ders Programları işlevsel olmalarının yanında kaliteli de olmalıdır. Kaliteli bir ders programı zorunlu olmayan kısıtları da sağlamalıdır. Genellikle bu kısıtların bir çoğu birbiriyle çelişmektedir. Çizge Boyama algoritması zorunlu kısıtları çözümlemede kullanılan yaklaşımlardan birisidir. Bu çalışmada çok hedefli genetik algoritmalar Yeditepe Üniversitesi Ders Programı problemini çözmede kullanılmıştır. Yeditepe Üniversitesi Bilgisayar Mühendisliği bölümünün kendisine özgü birtakım kısıtlar çözümlenmeye çalışılmıştır. Aynı yöntem İtalya'daki Udine Üniversitesi'nin ölçüm karşılaştırma testlerinde de kullanılmıştır.

University Course Timetabling is one of the interesting and exciting research areas of combinatorial optimization. This is not only due to the NP-hardness of the problem but also diversity of the researches in this area. University course timetables should be feasible and of course decent. The timetables created should satisfy different constraints which can be classified as hard and soft. Hard constraints should be obeyed strictly so that the timetable becomes feasible. On the other hand, a decent timetable should also satisfy the soft constraints. Experience in this area shows that these constraints conflict with each other in most of the cases. Using graph coloring algorithms is an approach to satisfy hard constraints. In this work, multi objective genetic algorithms are used to solve Yeditepe University Computer Engineering Department's course timetabling problem. Some special constraints of Yeditepe University Computer Engineering Department which are not common in timetabling literature are handled. The genetic algorithm utilized handles the hard constraints as a graph coloring problem and solves these constraints together with the soft ones using the multi objective framework. The adopted version of this framework is also applied to solve the benchmarking timetabling problems proposed by University of Udine - Italy.