Öğretme ve öğrenme tabanlı optimizasyon algoritması ile sınav çizelgeleme problemlerinin çözümü
Solving examination timetabling problems teaching and learning based optimization algorithm
Yazar: SEYYİDE YILDIRIM
Danışman: PROF. DR. KAAN YARALIOĞLU
Dokuz Eylül Üniversitesi / Sosyal Bilimler Enstitüsü / Ekonometri Ana Bilim Dalı / Ekonometri Bilim Dalı
Derece: Yüksek Lisans, 2014
Konu: Ekonometri = Econometrics
Dizin: Algoritmalar = Algorithms ; Optimizasyon = Optimization ; Sınav = Examination ; Sınav çizelgeleme = Examination scheduling ; Çizelgeleme = Scheduling ; Öğrenme = Learning ; Öğretme = Teaching

Özet:
Sınav çizelgeleme problemleri, belli kısıtlar altında, sınavların sınırlı sayıda zaman periyotlarına atanmaya çalışıldığı NP-complete karmaşıklık sınıfına ait kombinatoryel optimizasyon problemleridir. Son 20 yılda bu zor problemin çözümü için yüksek seviyeli arama stratejisi kullanan pek çok meta-sezgisel yöntem önerilmiştir. Bu yöntemlerin çoğu etkin state-of-art (en gelişkin) yaklaşımlar olması ile birlikte oldukça kompleks ve karmaşık yöntemlerdir. Bu tez kapsamında, uygulanabilirliği açısından basit ve yalın bir yöntem olan Öğretme- Öğrenme tabanlı optimizasyon (ÖÖTO) algoritmasının sınav çizelgeleme problemlerine yeni ve etkin bir yöntem olarak sunulup sunulamayacağı araştırılmıştır. ÖÖTO algoritması pek çok mühendislik tasarım ve kısıtlı-kısıtsız optimizasyon problemleri üzerinde etkinliğini ispatlamıştır. Bu problemlerden farklı olarak sınav çizelgeleme problemleri; çok boyutlu, çok modlu ve kesikli arama yüzeyine sahip olması açısından ÖÖTO için nispeten zorlu bir alandır. Çalışmanın diğer bir amacı, Öğretme ve Öğrenme tabanlı optimizasyon algoritmasının çizelgeleme gibi karmaşık optimizasyon problemleri üzerindeki performansının araştırılmasıdır.
Önerilen algoritma, Carter benchmark (kıyaslama) olarak da bilinen 13 gerçek-hayat problem seti üzerinde test edilmiştir. Çalışmanın çıktıları göstermiştir ki ÖÖTO algoritması sınav çizelgeleme problemleri için basit ve yalın bir yöntem olma avantajı ile birlikte uygulanabilir yeni bir alternatif yöntemdir.



Anahtar Kelimeler: Sınav Çizelgeme Problemleri, Öğretme Öğrenme Tabanlı Optimizasyon Algoritması, Meta-Sezgisel Yöntemler, Kombinatöryel Optimizasyon.

Abstract:
Examination timetabling problems are combinatorial optimization problems which are subtitle of NP-complete complexness class within a set of constraints and are used to assign examinations to limited time periods. In last two decades, great many meta-heuristic methods using high-level search strategy have been suggested for the solution of this difficult problem. As well as most of these methods are active state-of-art approaches; they are notably complex and complicated. In this study, it is investigated that whether the Teaching-Learning Based Optimization algorithm (TLBO) which is a simple and smooth method in terms of applicability can be suggested as a new and effective method to the examination timetabling problems. Although TLBO is proved to be effective on engineering design and constrained-unconstrained optimization problems, it is a challenging method for ETP since they have multi dimensions, multi modes and discrete search surfaces. The other aim of the study is to investigate the performance of TLBO on complicated optimization problems such as timetabling optimization.
Suggested algorithm was tested for 13 real-world problem set recognized as Carter benchmark. The ultimate outcome of the study shows that with its advantage of being a simple method, TLBO algorithm is an alternative applicable method for ETP.



Keyword: Examination Timetabling, Teaching and Learning Based Optimization Algorithm, Meta-Heusristic, Combinatorial Optimization.