A NEW MATHEMATICAL MODEL AND RANDOM KEY BASED METAHEURISTIC SOLUTION APPROACH FOR COURSE-ROOM-TIME ASSIGNMENT PROBLEM

Year 2019, Volume: 27 Issue: 2, 67 - 76, 15.08.2019

Zehra Kamışlı Öztürk , Müjgan Sağır

https://doi.org/10.31796/ogummf.549986

Cited By: 3

Abstract

This study presents a newly developed mixed-integer mathematical model for university course-room-time assignment problem. Optimal results with no soft constraint violations are obtained for some type of problem instances. As problem complexity increases it becomes more difficult to find feasible solution for this problem in a reasonable time. Therefore, a heuristic approach is often needed for such problems. In this study, a random key based genetic algorithm (RKGA) is developed. RKGA encoding is used in order to encode the chromosomes with a length of just the number of courses and not to use problem specific genetic operators and/or repair mechanisms. Well-known problem instances from the literature are selected to evaluate the outcome. The performance of RKGA is competitive to that of other algorithms especially for big size problems.

Keywords

Course-room-time, assignment problem, Mathematical modelling, Random key based genetic algorithms

DERS-DERSLİK-ZAMAN DİLİMİ ATAMA PROBLEMİ İÇİN YENİ BİR MATEMATİKSEL MODEL VE RASSAL ANAHTAR TEMELLİ METASEZGİSEL ÇÖZÜM YAKLAŞIMI

Abstract

Bu çalışmada üniversite ders-derslik-zaman dilimi atama problemi için yeni bir karma tam sayılı matematiksel model önerilmiştir. Geliştirilen karma tam sayılı matematiksel model ile literatürde yer alan test problemleri çözdürülmüş ve bir kısmı için tüm esnek kısıtlar sağlanarak en iyi çözüm elde edilmiştir. Problem karmaşıklığı arttıkça makul sürelerde uygun çözüm bulmak zorlaştığından, bu tür problemlerin çözümü için sezgisel bir yaklaşıma ihtiyaç duyulmaktadır. Çalışmada, rassal anahtar temelli bir genetik algoritma (RKGA) geliştirilmiştir. Probleme özgü özel genetik operatörler ve/veya onarma mekanizmaları kullanmamak için sadece ders sayısı uzunluğundaki kromozomları kodlamak için RKGA kodlaması kullanılmıştır. Çıktıların
değerlendirilmesi için literatürde iyi bilinen test problemleri seçilmiştir. Özellikle büyük boyutlu problemlerde RKGA’nın performansının diğer algoritmalar ile rekabet edebilir düzeyde olduğu görülmüştür.

Keywords

Ders-derslik-zaman dilimi atama problemi, Matematiksel modelleme, Rassal anahtar temelli genetik algoritma

References

• Abdullah, S., Burke, E.K. & McCollum, B. (2005). An investigation of variable neighborhood search for university course timetabling, Proceedings of 2nd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA 2005), New York,.413-427.
• Abramson, D. (1991). Constructing school timetables using simulated annealing: sequential and parallel algorithms. Management Science, 37(1), 98-113.
• Abuhamdah, A. and Ayob, M. (2005). Experimental result of particle collision algorithm for solving course timetabling problems. International Journal of Computer Science and Network Security, 9(9), 134-142.
• Alkan, A. and Özcan, E. (2003). Memetic algorithms for timetabling, Proceedings of IEEE Congress on Evolutionary Computation, 1796–1802.
• Asmuni, H., Burke, E.K. & Garibaldi, J. (2005). Fuzzy multiple heuristic ordering for course timetabling, Proceedings of the 2005 UK Workshop on Computational Intelligence UK IC 2005, London, UK, 302-309.
• Bean, J.C. (1994). Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing, 6, 154-160.
• Beligiannis, G.N., Moschopoulosa, C.N., Kaperonisa, G.P. & Likothanassisa, S. D. (2008). Applying evolutionary computation to the school timetabling problem: the Greek case. Computers and Operations Research, 35(4), 1265-1280.
• Bellio, R., Ceschia, S., Di Gaspero, L. Schaerf, A. & Urli, T. (2016). Feature-based tuning of simulated annealing appliedto the curriculum-based course timetabling problem. Computers & Operations Research, 65, 83-92.
• Bolaji, A.L., Kahader, A.T. & Al-Betar, M.A. (2014). University course timetabling using hybridized artificial bee colony with hill climbing optimizer. Journal of Computational Science, 5, 809-818.
• Burke, E.K., Elliman, D. & Weare, R. (1994). A genetic algorithm based university timetabling system, Proceedings of the 2nd East-West International Conferance on Computer Technologies in Education, Crimea, Ukraine.
• Burke, E.K., Kendall, G. & Soubeiga, E. (2003). A tabu search hyperheuristic for timetabling and rostering. Journal of Heuristics, 9(6), 451-470.
• Burke, E.K., Marecek, J., Parkes, A.J. & Rudová, H. (2007a). Penalising patterns in timetables: novel integer programming formulations. Operations Research Proceedings, 2007, 409-414.
• Burke, E.K., McCollum, B., Meisels, A., Petrovic, S. & Qu, R. (2007b). A graph-based hyper-heuristic for educational timetabling problems. European Journal of Operational Research, 176, 177-192.
• Chen, R. and Shih, H. (2013). Solving university course timetabling problems using constriction particle swarm optimization with local search. Algorithms, 6, 227-244.
• Colorni, A., Dorigo, M. & Maniezzo, V. (1992). A genetic algorithm to solve the timetable problem. Technical Report, 90060: Politecnico di Milano, Italy.
• Costa, D. (1994). A tabu search algorithm for computing an operational timetable. European Journal of Operational Research, 79, 98-110.
• Daskalaki, S., Birbas, T. & Housos, E. (2004). An integer programming formulation for a case study in university timetabling. European Journal of Operational Research, 153, 117-135.
• Ejaz, N. and Javed, M.Y. (2007). A hybrid approach for course scheduling inspired by die-hard co-operative ant behavior, Proceedings of the IEEE International Conference on Automation and Logistics, 3095 – 3100.
• Eklund, N.H.W. (2006). Using genetic algorithms to estimate confidence intervals for missing spatial data. IEEE Transactions on Systems, Man, and Cybernetics-Part C: Applications and Reviews, 36(4), 519-524
• Gunawan, A., Ng, K.M. & Poh, K.L. (2007). Solving the teacher assignment-course scheduling problem by a hybrid algorithm. International Journal of Mechanical, Aerospace, Industrial, Mechatronic and Manufacturing Engineering, 1(2), 136-141.
• Kamisli Ozturk, Z., Ozturk, G. & Sagir, M. (2010). An automated multi-objective invigilator-exam assignment system. International Journal of Information Technology & Decision Making, 9(2), 223-238.
• Kostuch, P. (2005). The university course timetabling problem with a three-phase approach. practice and theory of automated timetabling. Lecture Notes in Computer Science, 3616(2005), 109-125.
• Kovačič, M. (1993). Timetable construction with markovian neural network. European Journal of Operational Research, 69,92-96.
• Michalewicz, Z. (1996). Genetic algorithms + data structures = evolution programs. London: Springer-Verlag.
• Piechowiak, S. & Kolski, C. (2004). Towards a generic object oriented decision support system for university timetabling: an interactive approach. International Journal of Information Technology & Decision Making, 3(1), 179-208.
• Schaerf, A. (1999). A survey of automated timetabling. Artificial Intelligence Review, 13(2), 87-127.
• Schimmelpfeng, K. and Helber, S. (2007). Application of a real-world university-course timetabling model solved by integer programming. OR Spectrum, 29, 783-803.
• Socha, K., Knowles, J. & Samples, M. (2003). A max-min ant system for the university course timetabling problem. Lecture Notes in Computer Science, 2463(10), 1-13.
• Srinivas, M. and Patnaik, L.M. (1994). Genetic algorithms: a survey. Computer, 27(6), 17-26.
• Snyder, L.V. and Daskin, M.S. (2006). A random-key genetic algorithm for the generalized traveling salesman problem. European Journal of Operational Research, 174, 38-953.
• Thompson, J.M., and Dowsland, K.A. (1998). A robust simulated annealing based examination timetabling system. Computers & Operations Research, 25(7/8), 637-648.
• Valdes, R.A., Crespo, E. & Tamarit, J.M. (2002). Design and implementation of a course scheduling system using tabu search. European Journal of Operational Research, 137, 512-523.
• Yu, E. and Sung, K.S. (2002). A genetic algorithm for a university weekly courses timetabling problem. International Transactions in Operational Research, 9, 703-717.