Tez No	İndirme	Tez Künye	Durumu
597263		Üniversite ders çizelgeleme probleminin tamsayılı doğrusal programlama ve sezgisel yaklaşımlar ile çözümü / Solving university course timetabling problems with integer linear programming and heuristic approaches Yazar:AKIN ÖZKAN Danışman: PROF. DR. AYDIN ULUCAN Yer Bilgisi: Hacettepe Üniversitesi / Sosyal Bilimler Enstitüsü / İşletme Ana Bilim Dalı / Sayısal Yöntemler Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Eğitim ve Öğretim = Education and Training ; İşletme = Business Administration Dizin:Ders programları = Curriculum ; Doğrusal programlama = Linear programming ; Doğrusal tamsayı programlama = Linear integer programming ; Sezgisel yaklaşım = Intuitive approach ; Tam sayılı doğrusal programlama = Integer linear programming ; Üniversiteler = Universities	Onaylandı Doktora Türkçe 2019 135 s.
Üniversite ders çizelgeleme NP-Tam problem sınıfında olan ve her üniversitenin kendine özel gereksinimlerinden dolayı daha da karmaşıklaşan bir problem türüdür. Bu çalışmada, şubeli ve seçmeli derslere sahip olmanın yanında çoğu kaynağı ortak kullanan ve birçok bölüme sahip fakülte düzeyindeki ders çizelgeleme problemlerini tamsayılı doğrusal programlama (TDP) veya sezgisel yaklaşımlar ile çözebilen bir çözücü tasarlamak ve benzer yapıdaki problemlere kolayca uyarlanabilecek atama modelleri oluşturmak amaçlanmıştır. Bu kapsamda; derslerin zorunlu, şubeli zorunlu ve seçmeli olma durumlarını da dikkate alan TDP ve sezgisel modeller oluşturulmuştur. Tek aşamalı olarak sunulan TDP modelinde parametreler indislere göre gruplanarak oluşturulduğu için hem kısıt sayısı hem de karar değişken sayısı önemli ölçüde azaltılmıştır. Bu sayede, büyük ölçekli bir gerçek hayat problemi olan İktisadi ve İdari Bilimler Fakültesi (HÜİİBF) ders çizelgeleme problemi optimal olarak çözülebilmiştir. Sezgisel çözüm için iki aşamalı algoritmalar kullanılmaktadır. İlk aşamada uygulanabilir bir başlangıç çözümü elde edilmekte, ikinci aşamada çözümün kalitesi iyileştirilmektedir. Başlangıç çözümü için, biri açgözlü sezgisel (a greedy heuristics-GH) ve bir diğeri iteratif ileri arama (iterative forward search-IFS) sezgiseli olan iki farklı yaklaşım kullanılmıştır. İyileştirme aşamasında ise birer yerel arama sezgiseli olan tabu arama (tabu search-TS) ve benzetim tavlaması (simulating annealing-SA) sezgiselleri kullanılmıştır. Modellere ek bir kısıt (derslik sabitliği kısıtı) eklendiğinde problemin kompleksliği artmış ve TDP modeli ile optimal çözüme ulaşılamadığı görülmüştür. Sezgisel modeller kullanıldığında ise göreli olarak iyileştirilmiş çözümler elde edilmişidir. Sonuçlar, başlangıç çözümü aşamasında, çözüm süresi açısından GH algoritmasının IFS algoritmasından daha hızlı olduğunu, iyileştirme aşamasında ise SA sezgiselinin TS sezgiselinden daha iyi sonuçlar verdiğini göstermiştir.
University course timetabling is a problem type that is in the NP-Complete problem class and can become even more difficult due to the specific requirements of each university. In this study, it is aimed to design to a solver that can be used to solve university course timetabling problems which consists of multiple departments, have many common resources as well as have elective and multi-section courses at faculty level by using integer liner programming or heuristic approaches, and to develop assignment models that can be easily adapted to the problem in the similar structure. In this context, ILP and heuristic models that can take into account availability of mandatory, multi-section mandatory and elective of the courses were developed. In the ILP model, the number of decision variables and constraints have significantly reduced since the parameters were grouped according to indices. In this way, Faculty of Economics and Administrative Sciences at Hacettepe University course timetabling problem which is a large scale real-life problem could has been solved optimally. While this model is an exact algorithm, heuristics algorithms are two-stage. In the first stage, a feasible initial solution is obtained and in the second stage, the quality of the solution is improved. Two different approaches are proposed for the initial solution: a greedy heuristics (GH) and an iterative forward search (IFS). In the second stage, tabu search (TS) and simulating annealing (SA), which are local search heuristics, are used. When an additional constraint (room stability constraint) has added to the models, the complexity of the problem has increased and the optimal solution could has not be reached with the ILP model. When heuristic models have used, relatively bettered solutions have obtained. The results have shown that the GH algorithm is faster than the IFS algorithm in the initial solution stage and that the SA heuristic give better results than the TS heuristic in the improvement stage.