A Course timetabling algorithm

Abstract

öz Bir üniversite için haftalık ders programı hazırlanmasında ders saatleri, akademik personel, derslikler gibi mevcut kaynaklar çoğu kez cakışmasız bir çizelgeye olanak tanımaz. Kabul edilebilir iyi bir program hazırlamakta karşılaşılan büyüklükte kombinatoryel bir probleme çözüm getirmek için Tabu Arama Tekniği gibi bir pratik metoda ihtiyaç vardır. Bu tezde Tabu Arama Tekniği'nin akademik ders programı hazırlanmasında nasıl kullanılabileceği anlatılmaktadır, önerilen algoritma akademisyen ve öğrenci çakışmasını azaltmayı, öğlen yemeği saatine minimal sayıda ders koymayı, programda boşluğu azaltmayı ve akademisyenlerin ders saati tercihlerine mümkün nisbette cevap vermeyi amaçlamaktadır. Ders saatlerinin belli zaman dilimleri içerisinde başlayıp bitmek zorunda olduğu, derslerin tek bölümü bulunduğu, blok ders olmadığı ve sınıf kısıtlamasının bulunmadığı varsayılmıştır. iv

ABSTRACT In most practical academic course timetabling cases, time-slots, academic staff, and classrooms available can not accommodate a conflict-free solution. Finding a feasible schedule with certain desirable characteristics requires the use of heuristic procedures for dealing with the combinatorial size of realistic schedules. One of the most efficient heuristics for handling large optimization problems is the Tabu Search technique. An algorithm outlining the implementation details of applying Tabu Search to the course timetabling problem is presented in this thesis. The algorithm attempts to find a good assignment of every lecture of each course to a period of the weekly timetable on the basis of minimal instructor and student overlaps, minimal courses at lunch periods, a compact schedule, and satisfaction of instructors' preferences about periods. The assumptions are fixed time periods, single section non-consecutive courses, and unlimited availability of rooms. m