Sezgisel algoritmalarla ders çizelgeleme problemi çözümü
Course timetable problem solving with herustic algorithms
Yazar: RECEP ÇOLAK
Danışman: DOÇ. DR. TUNCAY YİĞİT
Süleyman Demirel Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2015
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Ders çizelgeleme =   ; Genetik algoritma tekniği = Genetic algorithm technique ; Sezgisel algoritmalar = Heuristic algorithms

Özet:
Bu çalışmada sezgisel algoritmalardan birisi olan genetik algoritma ile ders çizelgeleme problemine çözüm getirmek amaçlanmıştır bunun için bir bilgisayar programı yazılmış parametreler değiştirilerek deneyler yapılmış ve sonuçlar grafikler halinde listelenmiştir.
Üniversiteler için ders çizelgelemenin otomatikleştirilmesi şubelerin, öğretim elemanlarının ve dersliklerin çakışmadan, ilgili eğitim-öğretim döneminde okulda ki bütün şubeler için açılmış olan tüm derslerin istenilen koşullara uyacak şekilde atamasının yapılmasıdır. Yapılacak olan atama işleminde derslerin önceden tanımlı olan dersliklere ve şube öğrencilerini alabilecek dersliğe atanması. Öğretim elemanlarının istemediği zaman dilime ve günlük belirli bir ders saatinden daha fazla derse atanmaması, öğretim elemanının aynı anda tek bir derse atanması, şubenin atanmayan hiçbir dersinin kalmaması ve aynı zaman dilime birden çok derse atanmaması gerekmektedir. Derslik içinde aynı zaman dilimine birden fazla dersin atanmaması, derslerin istenmediği dersliklere atanmaması ve bunlar gibi daha bir çok birçok kısıtlamanın çözülmek zorunda olması problemin çözümünü zorlaştırmaktadır. Problemin çözümünde çok fazla veri, az kaynak ve çok fazla kısıtın bulunması klasik bilgisayar programları yerine genetik algoritma, karınca kolonisi algoritması, yapay arı kolonisi algoritması, tabu arama algoritması gibi sezgisel algoritmalar kullanılmaktadır. Sezgisel algoritmalar ile çok büyük olan arama uzayı içinde paralel bir arama ile çözüme ulaşılmaya çalışılmakta ve kabul edilebilir sonuçlar elde edilebilmektedir.
Yapılan çalışmada Süleyman Demirel Üniversitesi Uzaktan Eğitim Meslek Yüksekokuluna ait gerçek veriler kullanılarak sezgisel bir yaklaşım olan genetik algoritma ile çalışan bir uygulama yazılımı hazırlanmıştır. Yazılan program şube, ders, derslik ve öğretim elemanı değerlerini veri tabanından okuyarak çalışmaktadır. Veri tabanına başka bir okula ait veriler girilir ise hazırlanan program üzerinde bir değişiklik yapmadan şube, ders, derslik ve öğretim elemanı sayısından bağımsız olarak çalışabilmektedir.. Program farklı birey sayılarında değişik çaprazlama ve mutasyon oranı ile farklı iterasyon sayıları için test edilmiştir. Testler sonucunda birbirinden farklı sonuçlar çıksa da hepsinde ihlal edilen kısıtların büyük çoğunluğu çözülebilmiştir. Program sonunda ortaya çıkan ders çizelgeleri şube, derslik ve öğretim elemanları için ayrı ayrı alınıp incelenmiştir. Şube derslerinde çakışma olmamış ve atanmayan hiçbir ders kalmamıştır, öğretim elemanlarının dersleri çakışmamış ve istemedikleri saate atama yapılmamıştır. Dersler için özel derslikler tanımlanmış ise dersler bu dersliklere atanmıştır. Probleme uygun tasarım ile enetik algoritma kullanılarak ders çizelgeleme problemi kabul edilebilir bir zaman içinde çözülebilmektedir.

Abstract:
In this study, it is intended to solve the problem of course scheduling with the genetic algorithm which is one of the heuristic algorithms. For this purpose, a computer program has been written, tests were performed by varying the parameters and the results were listed graphically.
Automation of course scheduling for universities is the assignment of all courses opened to all branches at the school in relevant academic year in accordance with the desired conditions without overlap of branches, lecturers and classrooms. The assignment of courses to predefined classrooms and to the classrooms in which branch students can take in the assignment process. There are some needs for the assignment; the assignment should be made for the time zone asking by lecturers, the lecturers should not take courses more than a specific hour in a day, the lecturers should take only one course at the same time, there should be no course that the assignment has not been made in the branch and the courses should not be given at the same time zone. The assignment of more than one course at the same time to the classrooms, the assignment of courses to undesired classrooms and many restrictions like that should be resolved and these make difficult to solve the problem. While solving the problem, heuristic algorithms such as genetic algorithms, ant colony algorithm, artificial bee colony algorithm and taboo search algorithm are used instead of the classic computer programs due to the presence of too much data, fewer resources and too many constraints. It is tried to reach a solution via a parallel search in very large search space by heuristic algorithms, and acceptable results can be obtained.
In the study, an application software working with genetic algorithms which is an heuristic approach has been written by using real data from Distance Education Vocational School in Süleyman Demirel University. The program is working by reading branch, lesson, classroom and lecturer values from its database. If the data belonged to another school is entered into the database, it can be worked independently from branch, lesson, classroom and lecturer numbers without making a change on the prepared program. The program was tested for a number of different iterations with different crossover and mutation rate in the varying number of individuals. Although the test results are different from each other, the majority of violated constraints could be solved in all. The course schedules obtained at the end of the program were examined separately for branch, classrooms and lecturers. There was no overlap for branch courses and there was no course that the assignment has not been made, the courses of lecturers were not overlapped and there was no assignment to the undesired hours. If specific classrooms were defined for courses, the courses were assigned to these classes. The course scheduling problem can be solved in an acceptable time by using genetic algorithm with proper design to the problem.