| Paper title: |
A New Genetic Approach for Course Timetabling Problem |
| DOI: | https://doi.org/10.4316/JACSM.202101001 |
| Published in: | Issue 1, (Vol. 15) / 2021 |
| Publishing date: | 2021-04-19 |
| Pages: | 9-14 |
| Author(s): | BALAN Ionuț |
| Abstract. | Educational timetabling problems, such as university exam timetabling, university course timetabling and school timetabling, are combinatorial optimization problems that require the allocation of a set of resources to meet some objectives, based a specified set of constraints [1]. The university course timetabling is often finalized in stages, the data changes making it impossible to return to a certain previous version. As each version is announced to the community, it is desirable to have a robust initial schedule, i.e. one that can be repaired with a limited number of changes, being a version that, through modifications, will lead to a new solution whose quality is better [2]. In this article we used genetic algorithms that, based on heuristics, generate an initial population of good quality schedules. Within the described algorithm we calculate a fitness function that takes into account the windows between teaching activities, but also takes into account the efficient use of space, but also a maximum number of lectures per day. To test the algorithm we used a set of real data from the Faculty of Economics and Public Administration, belonging to "Ştefan cel Mare" University from Suceava, Romania. |
| Keywords: | Timetabling, Genetic Algorithm, Chromosomes, Generations, Greedy, NEH, Job Shop Scheduling, Optimization |
| References: | 1. N. Pillay, A review of hyper-heuristics for educational timetabling, Annals of Operational Research, 239, 2016, pp.3-38 2. A. Gulcu, C. Akkan, Robust university course timetabling problem subject to single and multiple disruptions, European Journal of Operational Research, Vol. 283, issue 2, 1 June 2020, pp. 630-646 3. M. Lindahl, M. Sorensen, T. R. Stidsen, A fix-and-optimize matheuristic for university timetabling, Journal of Heuristics 24, 2018, pp. 645-665 4. V. Pereira, H.G. Costa, Linear Integer model for the course timetabling problem of a faculty in Rio de Janeiro, Advances in Operational Research , vol 2016, pp.1-9 5. E.K. Burke, J.H. Kingston, D. De Werra, Applications to timetabling. The Handbook of Graph Theory, J. Gross and J. Yellen (eds.), Chapman Hall/ CRC Press, 2004, pp. 445-474 6. Z.P. Lu, J.K. Hao, Adaptive Tabu search for course timetabling, European Journal Of Operational Research, 2010, pp. 235-244 7. G.M.White, B.S. Xie, S. Zonjic, Using Tabu search wirh longer-term memory and relaxation to create examination timetables, European Journal Of Operational Research, 2004, pp. 80-91 8. E.K. Burke, B. McCollum, A. Meisels, S. Petrovic, R. Qu, A graph-based hyper heuristic for timetabling problems, European Journal Of Operational Research, 2007, pp. 177-192 9. J. Thompson, K. Dowsland, A robust simulated annealing based examination timetabling system, Computers & Operations Research, vol. 25, issues 7-8, 1998, pp. 637-648 10. M. Colorni, Genetic Algorithms and highly constrained problems: the timetable, Parallel Problem Solving from Nature, H.P. Schwefel, R. Manner (eds.), 496, Springer, Berlin Heidelberg, 1991, pp. 55-59 11. M. Dorigo, C. Blum, Ant colony optimization theory: a survey, Theoretical Computer Science 344, 2005, pp. 243-278 12. K.A. Smith, D. Abramson, D. Duke, Hopfield neural network for timetabling: formulations, methods, and comparative results, Computers & Industrial Engineering, vol. 44, issue 2, 2003, pp. 283-305 13. A. Lewis, Parallel Optimisation Algorithms for Continuous Non-Linear Numerical Simulations, School of Computing and Information Technology, Grifftih University, Nathan Campus, Brisbane, Australia, thesis, 2004 14. I. Balan, S.G. Pentiuc, TSP secvenţial vs. paralel folosind algoritmii genetici, Seminarul Științific Sisteme Distribuite (Suceava - online) Ediția 2009, ISSN 2067-5259 15. D. Zaharie, Calcul neural şi calcul evolutiv, Universitatea de Vest Timişoara, 2004 (material didactic) 16. M. Nawaz, E.E. Enscore Jr, I. Ham, A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, OMEGA, The International Journal of Management Science, 11(1), 1983, pp. 91-95 |
| Back to the journal content | |
