Ü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
- Tez No: 597263
- Danışmanlar: PROF. DR. AYDIN ULUCAN
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Eğitim ve Öğretim, İşletme, Computer Engineering and Computer Science and Control, Education and Training, Business Administration
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2019
- Dil: Türkçe
- Üniversite: Hacettepe Üniversitesi
- Enstitü: Sosyal Bilimler Enstitüsü
- Ana Bilim Dalı: İşletme Ana Bilim Dalı
- Bilim Dalı: Sayısal Yöntemler Bilim Dalı
- Sayfa Sayısı: 135
Özet
Ü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.
Özet (Çeviri)
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.
Benzer Tezler
- Akademik ders programlarının yapılması probleminin matematiksel modeller ve algoritmalarla çözümü ve uygulaması
Solution of the academic course scheduling problem with mathematical modeling and algorithms and its application
UĞUR BAÇ
- Üniversite ders zaman çizelgeleme problemi
University course timetabling problem
RUMEYSA ÖZDEMİR
Yüksek Lisans
Türkçe
2012
MatematikYıldız Teknik ÜniversitesiMatematik Ana Bilim Dalı
PROF. DR. MEHMET AHLATCIOĞLU
- Ders programı çizelgeleme problemi için 0-1 tamsayılı programlama yaklaşımı
A 0-1 integer programming approach to course scheduling problem
HAKAN ALTUNAY
Yüksek Lisans
Türkçe
2015
Endüstri ve Endüstri MühendisliğiKırıkkale ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. TAMER EREN
- Üniversite zaman çizelgeleme problemine tamsayılı programlama yaklaşımı: Mersin Üniversitesi Mimarlık Fakültesi örneği
University time scheduling problem integer programming approach: The case of Mersin University Faculty of architecture
ALİ ARPACIOĞLU
Yüksek Lisans
Türkçe
2019
Eğitim ve ÖğretimMersin Üniversitesiİşletme Ana Bilim Dalı
PROF. DR. TEVFİK AYTEMİZ
- Optimal kapasite dağıtımı ile yükseköğrenim kalitesinin geliştirilmesi: Bir gelir yönetimi yaklaşımı
Improving higher education quality by optimal capacity allocation: A revenue management approach
ARMAĞAN ÖZBİLGE