Sınav çizelgeleme problemleri için üst sezgisel yaklaşımlar

Abstract

Sınav çizelgeleme problemi katı ve yumuşak kısıtları göz önünde bulundurarak bir dizi sınavı, bir dizi zaman dilimi ve bir dizi dersliğe planlamaktır. Sınav çizelgeleme problemleri özellikle üniversitelerde her sınav döneminde karşılaşılan çözülmesi zor, zaman ve iş gücü gerektiren çok parametreli ve kısıtlı optimizasyon problemleridir. Literatürde bu problemlerin çözümü için günümüze kadar birçok çalışma yapılmıştır. Bu çalışmalarda sınav çizelgeleme problemleri çözümü için çeşitli yöntemler önerilmiştir. Son zamanlarda yapılan çalışmalarda, araştırmacılar üst sezgisel yaklaşımların sınav çizelgeleme problemlerinin çözümünde başarılı olduğunu görmüşler ve bu alana yönelmişlerdir. Üst sezgisel yaklaşımlar belirli bir problem veya problem seti için önceden tanımlanan alt sezgisel yöntemleri kullanarak alt sezgisellerin uygun kombinasyonunu üreten problem alanından bağımsız modellerdir. Bu tez çalışmasında sınav çizelgeleme problemlerinin çözümü için üst sezgisel yaklaşımlar sunulmuştur. Tez çalışmasının temel amacı, sınav çizelgeleme problemlerinin derinlemesine incelenmesi ve üst sezgisel yaklaşımlar ile sınav çizelgeleme problemlerinin çözülmesidir. Üst sezgisel yaklaşımlar sezgisel seçim ve sezgisel üretim olarak ikiye ayrılır. Bu çalışmada sezgisel seçen üst sezgiseller kullanılmıştır. Sezgisel seçen üst sezgisel yaklaşımlar sezgisel seçim ve hareket kabul olmak üzere ikiye ayrılır. Bu çalışmada sezgisel seçim yöntemlerinden basit rastsal ve tez çalışması kapsamında değiştirilen rastsal permütasyon, hareket kabul yöntemlerinden ise sadece iyileşen kullanılarak iki farklı üst sezgisel yaklaşım tasarlanmıştır. Tez çalışmasında öncelikle katı kısıtlar sağlanmıştır. Daha sonra çözümün kalitesini daha da arttıran yumuşak kısıtları sağlamak için ceza matrislerine dayalı alt sezgiseller kullanılmış ve alt sezgiseller ile üst sezgisel yaklaşımı güçlendirmeye odaklanılmıştır. Tasarlanan iki üst sezgisel yaklaşım gerçek dünya örnekleri olan Uluslararası Zaman Çizelgeleme Yarışması (International Timetabling Competition, ITC-2007) tarafından 2007 yılında sunulan problemler üzerinde test edilmiştir. Sonuçlar incelendiğinde bu iki yaklaşımın birbirlerine yakın sonuçlar verdiği fakat ikinci yaklaşımın daha iyi olduğu görülmüştür. Üst sezgisel yaklaşımlar literatürde yer alan bazı çalışmalarla karşılaştırıldığında; bazı sonuçlarda üstün gelmiş, bazı sonuçlarda ise rekabetçi olmuşlardır.

Exam timetabling is to plan a series of exams, a series of timeslots and a series of rooms, taking into account hard and soft constraints. Exam timetabling problems are constrained and multi-parameter optimization problems that require time and labor to be solved especially encountered in universities during each exam period. There are many different studies in the literature for the solution of these problems. In these studies, many methods have been proposed for solving exam timetabling problems. However, researchers have recently seen that the hyper-heuristic approaches are successful in these problems and have turned to this field. Hyper-heuristic approaches are independent from the problem area that produces the appropriate combination of low level heuristics using the predefined low level heuristics for a particular problem or set of problems. In this thesis, hyper-heuristic approaches are presented for solving exam timetabling problems. The main purpose of the thesis study is to examine exam timetabling problems and to solve the exam timetabling problems with hyper-heuristic methods. Hyper-heuristic approaches are divided into heuristic selection and heuristic generation. In this study, selection hyper-heuristics are used. Hyper-heuristic approaches that select heuristic consists of two phases: heuristic selection and move acceptance. Of heuristic selection methods, simple random and random permutation which was changed within the scope of the thesis study was used in this study. Of the move acceptance methods, only improving was used. Two different hyper-heuristic approaches have been designed with these heuristic selection and move acceptance methods. In this study, hard constraints are provided firstly. Then low level heuristics based on penalty matrices were used to increase the quality of the solution by supplying soft constraints. The focus is on supporting to the hyper-heuristic approach with the low level heuristics. The designed two hyper-heuristic approaches were tested on the problems presented in 2007 by the International Timetabling Competition (ITC-2007), which are real world examples. When the results were examined, it was seen that these two approaches gave close results, but the second approach was better. When the hyper heuristic approaches are compared with some studies in the literature; they were superior in some results and competitive in some results.