A NEW MATHEMATICAL MODEL AND RANDOM KEY BASED METAHEURISTIC SOLUTION APPROACH FOR COURSE-ROOM-TIME ASSIGNMENT PROBLEM
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
Kaynakça
- 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.