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
Creative Commons License
This article is licensed under a
Creative Commons Attribution-ShareAlike 4.0 International License.
Home | Editorial Board | Author info | Archive | Contact
Copyright JACSM 2007-2024