Solving university course timetabling problem using genetic algorithm

Abstract

Üniversite ders programı oluşturma problemi, belli bir sayıdaki derslerin sınırlı sayıdaki sınıf, zaman dilimi ve öğretim elemanları gibi kaynaklara önceden belirlenmiş kısıtları sağlayacak şekilde dağıtılmasını içerir. Kısıtlar iki gruba ayrılır: Kati kısıtlar ve gevşek kısıtlar. Bir ders programının kabil olabilmesi için bütün kati kısıtları sağlaması gerekir. İyi kalitede olabilmesi için de mümkün olduğunca fazla gevşek kısıtları sağlamalıdır.Üniversite ders programı oluşturma problemi Np-hard problemler sınıfındadır. Bu şu demektir; bu tip soruları çözmede harcanan zaman ve yapılan iş, problemin büyüklüğü arttıkça eksponensiyel olarak artar. Bu da bu problemleri daha zor ve daha zaman alıcı yapar. Bu yüzden bunları çözmekte ve tam sonuç bulmak yerine en iyi veya en iyiye en yakın çözümler üretmek için eniyileme teknikleri kullanılır. Genetik algoritmalar bu tip problemlerin çözümünde verimli bir method olarak düşünülür.Genetik algoritma, ilk kez Charles Darwin tarafından anlatılan evrim teorisini baz alır ve doğadaki seleksiyon, çaprazlama, mutasyon ve değiştirme gibi yapıları taklit etmeye çalışır. Bu olasılıksal operatörlerle, bibiriyle yarışan alternatif çözümler arasından en iyi çözümü seçer.Bu tezde, önce genetik algoritmanın genel tanımı ve genetik algoritmanın verimliliğinin sebeplerini açıklayan teorik altyapısı, Şema teoremi verilir. Daha sonra, Bahçeşehir Üniversitesi Fen Edebiyat Fakültesi verileriyle gerçek bir üniversite ders programlama problemi denenir. Bu probleme genetik algoritma tabanlı bir çözüm önerilir. Genetik algoritma uygulamaları anlatılır ve örnek probleme uygulanır. Ayrıca, popülasyon büyüklüğü, çaprazlama ve mutasyon oranları gibi parametrelerin en iyi değerlerinin tespiti denenir. Bu problemde sonuç olarak sadece kabil ders programları üreten, modifiye edilmiş, kati kısıtların ihlaline izin vermeyen genetik operatörlerle çalıştık. Bu yüzden amaç sadece iyi kalitede ders programı üretmekti. Bu bize daha kısa sürede daha iyi sonuçlar elde etmeyi sağladı.

The university course timetabling problem consists of allocating a number of courses to a limited set of resources such as rooms, timeslots, set of lecturers and group of students in such a way to satisfy predefined constraints. The constraints can be divided into two groups: hard constraints and soft constraints. A timetable has to satisfy all hard constraints in order to be feasible and it should be satisfy as much as possible soft constraints in order to be good quality.The university timetabling problem is in class of NP-hard problems. This means that the amount of time and work required to solve this type of problems increases exponentially with the problem size. This makes these problems more difficult and time consuming. Therefore optimization techniques are used to solve them and produce optimal or near optimal feasible solutions. Genetic algorithms are considered as an efficient approach for solving this type of problems.Genetic algorithm is based on the principle of evolution first described by Charles Darwin and it tries to mimic some features of nature such as selection, crossover, mutation and replacement. Through these probabilistic operators, genetic algorithms choose the optimal solution among a set of alternate solutions which compete with each other.In this thesis, first a general description of genetic algorithms and theoretical background, Schema Theorem, which describes the reasons of efficiency of genetic algorithms are given. Then a real life university course timetabling problem is examined with data coming from Bahcesehir University, Faculty of Arts and Sciences. A solution based on genetic algorithm is proposed for the problem. The genetic algorithm implementations are described and applied to the sample problem. Moreover, determination of the best parameter values, such as the population size, mutation and crossover rate, etc. is tried. We work on this problem by introducing modified genetic operators which do not allow violations of any hard constraints, as a result produce only feasible solutions. Therefore the aim of the genetic algorithm is to produce a good quality timetable. This gains us to get better solutions in a comparative short time.