Solving university course timetabling problem using genetic algorithm
Üniversitelerde ders programı oluşturma probleminin genetik algoritma ile çözümü
- Tez No: 215922
- Danışmanlar: YRD. DOÇ. DR. AHMET BEŞKESE
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2008
- Dil: İngilizce
- Üniversite: Bahçeşehir Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Bölümü
- Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Sayfa Sayısı: 54
Özet
Üniversite ders programı oluşturma problemi, belli bir sayıdaki derslerin sınırlı sayıdaki sınıf, zaman dilimi ve öğretim elemanları gibi kaynaklara önceden belirlenmiş kısıtları sağlayacak şekilde dağıtılmasını içerir. Kısıtlar iki gruba ayrılır: Kati kısıtlar ve gevşek kısıtlar. Bir ders programının kabil olabilmesi için bütün kati kısıtları sağlaması gerekir. İyi kalitede olabilmesi için de mümkün olduğunca fazla gevşek kısıtları sağlamalıdır.Üniversite ders programı oluşturma problemi Np-hard problemler sınıfındadır. Bu şu demektir; bu tip soruları çözmede harcanan zaman ve yapılan iş, problemin büyüklüğü arttıkça eksponensiyel olarak artar. Bu da bu problemleri daha zor ve daha zaman alıcı yapar. Bu yüzden bunları çözmekte ve tam sonuç bulmak yerine en iyi veya en iyiye en yakın çözümler üretmek için eniyileme teknikleri kullanılır. Genetik algoritmalar bu tip problemlerin çözümünde verimli bir method olarak düşünülür.Genetik algoritma, ilk kez Charles Darwin tarafından anlatılan evrim teorisini baz alır ve doğadaki seleksiyon, çaprazlama, mutasyon ve değiştirme gibi yapıları taklit etmeye çalışır. Bu olasılıksal operatörlerle, bibiriyle yarışan alternatif çözümler arasından en iyi çözümü seçer.Bu tezde, önce genetik algoritmanın genel tanımı ve genetik algoritmanın verimliliğinin sebeplerini açıklayan teorik altyapısı, Şema teoremi verilir. Daha sonra, Bahçeşehir Üniversitesi Fen Edebiyat Fakültesi verileriyle gerçek bir üniversite ders programlama problemi denenir. Bu probleme genetik algoritma tabanlı bir çözüm önerilir. Genetik algoritma uygulamaları anlatılır ve örnek probleme uygulanır. Ayrıca, popülasyon büyüklüğü, çaprazlama ve mutasyon oranları gibi parametrelerin en iyi değerlerinin tespiti denenir. Bu problemde sonuç olarak sadece kabil ders programları üreten, modifiye edilmiş, kati kısıtların ihlaline izin vermeyen genetik operatörlerle çalıştık. Bu yüzden amaç sadece iyi kalitede ders programı üretmekti. Bu bize daha kısa sürede daha iyi sonuçlar elde etmeyi sağladı.
Özet (Çeviri)
The university course timetabling problem consists of allocating a number of courses to a limited set of resources such as rooms, timeslots, set of lecturers and group of students in such a way to satisfy predefined constraints. The constraints can be divided into two groups: hard constraints and soft constraints. A timetable has to satisfy all hard constraints in order to be feasible and it should be satisfy as much as possible soft constraints in order to be good quality.The university timetabling problem is in class of NP-hard problems. This means that the amount of time and work required to solve this type of problems increases exponentially with the problem size. This makes these problems more difficult and time consuming. Therefore optimization techniques are used to solve them and produce optimal or near optimal feasible solutions. Genetic algorithms are considered as an efficient approach for solving this type of problems.Genetic algorithm is based on the principle of evolution first described by Charles Darwin and it tries to mimic some features of nature such as selection, crossover, mutation and replacement. Through these probabilistic operators, genetic algorithms choose the optimal solution among a set of alternate solutions which compete with each other.In this thesis, first a general description of genetic algorithms and theoretical background, Schema Theorem, which describes the reasons of efficiency of genetic algorithms are given. Then a real life university course timetabling problem is examined with data coming from Bahcesehir University, Faculty of Arts and Sciences. A solution based on genetic algorithm is proposed for the problem. The genetic algorithm implementations are described and applied to the sample problem. Moreover, determination of the best parameter values, such as the population size, mutation and crossover rate, etc. is tried. We work on this problem by introducing modified genetic operators which do not allow violations of any hard constraints, as a result produce only feasible solutions. Therefore the aim of the genetic algorithm is to produce a good quality timetable. This gains us to get better solutions in a comparative short time.
Benzer Tezler
- Developing a course scheduling system by using genetic algorithm
Genetik algoritma kullanılarak ders çizelgeleme sistemi tasarımı
CANSU ÇİĞDEM AYDIN
Yüksek Lisans
İngilizce
2008
Mühendislik BilimleriAtılım ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. NERGİZ ERCİL ÇAĞILTAY
- Ders programı çizelgeleme probleminin genetik algoritma ile çözümü: Bir uygulama
Solving the curriculum scheduling problem with genetic algorithm: An application
TUĞÇE NUR YILMAZ
Yüksek Lisans
Türkçe
2023
İşletmeOsmaniye Korkut Ata Üniversitesiİşletme Ana Bilim Dalı
DR. ÖĞR. ÜYESİ BİRSEN İREM KUVVETLİ
- A solution to course scheduling problem using genetic algorithms
Başlık çevirisi yok
ALPAY ALKAN
Yüksek Lisans
İngilizce
2002
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYeditepe ÜniversitesiYRD. DOÇ. DR. ENDER ÖZCAN
- Metasezgisel algoritmalar kullanılarak sınav çizelgeleme
Exam timetabling using metaheuristic algorithms
GÖKHAN SEYFİ
Yüksek Lisans
Türkçe
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUSTAFA SERVET KIRAN
- Ü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
AKIN ÖZKAN
Doktora
Türkçe
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolHacettepe Üniversitesiİşletme Ana Bilim Dalı
PROF. DR. AYDIN ULUCAN