A comprehensive timetabling at Marmara University


Thesis Type: Doctorate

Institution Of The Thesis: Marmara University, Faculty of Engineering, Industrial Engineering, Turkey

Approval Date: 2014

Thesis Language: Turkish

Student: AYLA GÜLCÜ

Supervisor: SEROL BULKAN

Abstract:

Eğitsel çizelgeleme, bütün kurumlarda karşılaşılan en önemli yönetsel aktivilerden biridir. Problemin el ile çözümü çok vakit alıcıdır. El ile bulunan çözüm hem öğrenciler hem de öğretmenler açısından tatmin edici olmayabilir. Biz bu tez çalışmasında bir gerçek hayat ders çizelgeleme problemini tanımlayarak çözmeye çalıştık. Mevcut durumda ders çizelgeleri el ile hazırlanıyor. Mevcut yöntem ile kalitesi yüksek çizelgeler üretilemediği herkes tarafından bilinmektedir. Çizelgelerin otomatik olarak üretilmesi için, genetik algoritma tabanlı bir hibrid çözücü geliştirilmiştir. Hibrid olma durumu iki şekilde sağlanmıştır. İlk olarak, başlangıç çözümü oluşturulurken kısıt programlama kullanılmıştır. Bu kısıt programlama yaklaşımında çeşitli düşük seviye sezgisel algoritmalar kullanılmıştır. Geliştirilen kısıt programlama metodunun çözümün kalitesi ve çözüm süresi açısından çok verimli olduğu gözlenmiştir. Ek olarak, bu metod girdi verisindeki tutarsızlıkların tamımlanması açısından çok faydalı olmuştur. Ayrıca bu metod ile tamsayı programlama tekniğinin performans kıyaslaması sunulmuştur. İkinci olarak, yerel arama metodlarından değişken komşuluk arama genetik algoritmaya eklenmiştir. Genetik algoritmada her bir jenerasyon oluştuktan sonra seçilen bazı üyelere bu yerel arama uygulanmıştır. Girdi verisi hazırlanan arayüz üzerinden toplanmıştır. 2013-2014 bahar ABSTRACT Educational timetabling is one of the most important administrative activity that takes place in all institutions. Manual solution of the problem is too time-consuming. The manual solution may not be satisfactory for both students and instructors. In this dissertation, we attempt to address and solve a real-life university course timetabling problem. Currently, course timetables are constructed manually. It is known that the current approach is far from finding a high-quality solution. In order to create timetables automatically, a genetic algorithm based hybrid solver has been developed. Two forms of hybridization are employed. First hybridization is employed during creating initial population. Initial population is created with constraint programming. Several low-level heuristics are used in the proposed constraint programming approach. This approach is found to be very effective in terms of solution quality and computation time. In addition, this method was of great help in order to identify inconsistencies in the input data. A performance comparison of the proposed method with integer programming is also presented. Second form of hybridization involves incorporation of a local search-based heuristic into the GA. After each generation, variable neighborhood search is applied on a number of selected individuals. Input data for the current instance is collected from users through a web interface designed for the solver. The 2013-2014 spring semester timetables have been created by using this solver.