A solution to course scheduling problem using genetic algorithms

Abstract

ÖZET Aynı zamanda Zaman Tablolama Problemi de olarak bilinen Ders Çizelgeleme Problemi, kısaca, daha önceden belirlenmiş olan kısıtların gözönüne alınarak, açılan derslere saat ataması yapmaktan ibarettir. Kısıtlar, öğrenci grupları, eğitmenlerin istekleri, yönetimsel istekler ve performansı iyileştirmeye yönelik talepler olabilir. Bu tezde, çok tipli kısıtlar içerebilen bir üniversiteye ait ders çizelgeleme probleminin Düzenli Hal Genetik Algoritması ile çözümü sunulmuştur. Sistem, hem bilgi girişi hem de sonucun alınabilmesi için güçlü ve kullanımı kolay ara birim içermektedir. Üniversiteler için 18 değişik tipte kısıt tanımlanabilmesine izin verilmiştir. Kısıtlar arasında, baştan birincil-ikincil ayrımı yapılmamış, ancak kullanıcının istediklerine öncelik tanımlanabilmesine izin verilmiştir. Yeni bir mutasyon operatörü (Sıralamalı Mutasyon) ve bir çaprazlama operatörü (sınıf bazlı ve düzenli) geliştirilmiştir. İlk deney sonuçlan oldukça ümit vericidir.

ABSTRACT Course Scheduling Problem (C.S.P.), also known as Time Tabling Problem, is assigning class hours of courses into predefined daily time slots in a week, considering the special constraints. Those may include constraints due to student groups, constraints imposed by instructors, constraints due to timing and other special ones. In this thesis, I present a Steady State Genetic Algorithm (SSGA) for solving a multi- constraint university course-time tabling problem. The system includes a powerful and interactive graphical user interface (GUI) for entering input data and viewing output. 18 different constraints are identified for the university time tabling. All constraints are accepted as hard constraints, but can be prioritized. A new mutation operator (Ranking Mutation Operator) and crossover operator (term based uniform) are introduced. Initial experimental results are promising. pOKfiUAimSYaN