OPTIMIZATION OF TIMETABLE AT THE UNIVERSITY
DOI:
https://doi.org/10.15588/1607-3274-2021-3-15Keywords:
university timetabling, optimization, problems with boolean variables, exact quadratic regularization method.Abstract
Context. In this paper, we consider a well-known university scheduling problem. Such tasks are solved several times a year in every educational institution. The problem of constructing an optimal schedule remains open despite numerous studies in this area. This is due to the complexity of the corresponding optimization problem, in particular, its significant dimension. This complicates its numerical solution with existing optimization methods. Scheduling models also need improvement. Thus, schedule optimization is a complex computational problem and requires the development of new methods for solving it.
Objective. Improvement of optimization models for timetabling at the university and the use of new effective methods to solve them.
Method. We use the exact quadratic regularization method to solve timetabling optimization problems. Exact quadratic regularization allows transforming complex optimization models with Boolean variables into the problem of maximizing the vector norm on a convex set. We use the efficient direct dual interior point method and dichotomy method to solve this problem. This method has shown significantly better results in solving many complex multimodal problems. This is confirmed by many comparative computational experiments. The exact quadratic regularization method is even more effective in solving timetabling problems. This optimization method is used for the first time for this class of problems, so it required the development of adequate algorithmic support.
Results. We propose a new, simpler timetabling optimization model that can be easily implemented software in Excel with the OpenSolver, RoskSolver, and others. We give a small example of building a schedule and describe step-by-step instructions for obtaining the optimal solution.
Conclusions. An efficient new technology developed for university timetable, which is simple to implement and does not require the development of special software. The efficiency of the technology is ensured by the use of a new method of exact quadratic regularization.
References
de Werra, D. An introduction to timetabling, European Journal of Operational Research, 1985, 19, pp. 151 – 162.
Kosolap A. A new method for global optimization, ESAIM: Proceedings and surveys, 2021, Vol. 71. pp. 121–130.
Junginger W. Timetabling in Germany – a survey [Электронный ресурс], In Interfaces, 1986, Vol. 16, No. 4, pp. 66–74. https://pubsonline.informs.org.
Shraerf A. A survey of automated timetabling, Journal Artificial Intelligence Review, 1999, Volume 13, Issue 2, pp. 1–8.
Oude Vrielink R. A., Jansen E. A., Hans E. W., van Hillegersberg J. Practices in timetabling in higher education institutions: a systematic review. Ann. Oper. Res., 2019, 275, pp. 145–160.
Aziz N. L. A., Aizam N. A. H. A brief review on the features of university course timetabling problem. AIP Conference Proceedings, Volume 2016, Issue 1, pp. 1–8.
Qu R., Burke E.K. A survey of search methodologies and automated system development for examination timetabling. Journal of scheduling, 2009, Volume 12, Number 1, pp. 55–89.
Bettinelli A., Cacchiani V., Roberti R., Toth P. An overview of curriculum-based course timetabling, TOP, 2015, No 23, pp. 313–349. DOI: 10.1007/s11750-015-0366-z.
Hayat Alghamdi, Tahani Alsubait, Hosam Alhakami, Abdullah Baz A Review of Optimization Algorithms for University Timetable Scheduling Engineering, Technology & Applied Science Research, 2020, Vol. 10, No. 6, pp. 6410–6417.
Nocedal J., Wright S. J. Numerical optimization. Springer, 2006. 685 p.
Kosolap A. Practical Global optimization. Dnipro, Publisher Bila K. O., 2020, 192 p.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2021 А. І. Косолап, Т. М. Дубовик
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
