AN APPLICATION OF INTEGER LINEAR PROGRAMMING TOWARDS UNIVERSITI MALAYSIA TERENGGANU COURSE SCHEDULING PROBLEM
DOI:
https://doi.org/10.46754/umtjur.v4i4.319Keywords:
University Course Timetabling, Optimization, Mixed Integer Linear Programming, Exact Method, Advanced Interactive Multidimensional Modelling System (AIMMS)Abstract
University Course Timetabling (UCT) problem is a combinatorial optimization problem in which a set of events has to be scheduled in timeslots and located in a suitable room by considering all the constraint involved. A feasible timetable plays an important role in ensuring the tasks or events are carried out appropriately. However, producing one is not an easy task due to its large data size and variety of requirements involved. In this research, mathematical model using Mixed Integer Linear Programming is applied for the university course timetabling problem. To validate the MILP model, data from Universiti Malaysia Terengganu (UMT) Academic Management Department is obtained. The data consists of 27 programmes, 1261 classes of 265 core courses, 59 venues and 50 timeslots. Advanced Interactive Multidimensional Modelling System (AIMMS) mathematical software with CPLEX solver is used as a tool to solve the mathematical model. The research showed that the model developed is applicable to the university course timetabling problem. An optimized solution is achieved in which fulfils the preferences of the users involved. The outcome of this research would indirectly assist the administrative staff who will be in charge in producing an effective course timetable for the university.
References
Aizam N. A. H., & Caccetta, L. (2014). Computational models for timetabling problems. Numerical Algebra, Control and Optimization, 4(3), 269-285. DOI: https://doi.org/10.3934/naco.2014.4.269
Almond, M. (1966). An algorithm for constructing university timetables. The Computer Journal, 8(4), 331-340. DOI: https://doi.org/10.1093/comjnl/8.4.331
Arratia-Martinez, N. M., Maya-Padron, C., & Avila-Torres, P. A. (2021). University course timetabling problem with professor assignment. Mathematical Problems in Engineering, 2021. https://doi. org/10.1155/2021/6617177 DOI: https://doi.org/10.1155/2021/6617177
Aziz, N. L. A., & Aizam, N. A. H. (2017). University course timetabling and the requirements: Survey in several universities in the east-coast of Malaysia. In AIP Conference Proceedings, 1870(1). AIP Publishing LLC. DOI: https://doi.org/10.1063/1.4995845
Aziz, N. L. A., & Aizam, N. A. H. (2018). A brief review on the features of university course timetabling problem. In AIP Conference Proceedings, 2016(1). AIP Publishing LLC. DOI: https://doi.org/10.1063/1.5055403
Collins. (2011). Definition of ‘School’. In Collins English Dictionary. https://www. collinsdictionary.com/dictionary/english/ school.
Daskalaki, S., Birbas, T., & Housos, E. (2004). An integer programming formulation for a case study in university timetabling. European Journal of Operational Research, 153(1), 117-135. DOI: https://doi.org/10.1016/S0377-2217(03)00103-6
Daskalaki, S., & Birbas, T. (2005). Efficient solutions for a university timetabling problem through integer programming. European Journal of Operational Research, 160(1), 106-120. DOI: https://doi.org/10.1016/j.ejor.2003.06.023
Landa-Silva, D., & Obit, J. H. (2009). Evolutionary non-linear great deluge for university course timetabling. In Corchado, E., Wu, X., Oja, E., Herrero, Á., & Baruque, B. (Eds.), Hybrid artificial intelligence systems. HAIS 2009. Lecture Notes in Computer Science, vol 5572. Springer. DOI: https://doi.org/10.1007/978-3-642-02319-4_32
Lawrie, N. L. (1969). An integer linear programming model of a school timetabling problem. The Computer Journal, 12(4), 307-316. DOI: https://doi.org/10.1093/comjnl/12.4.307
MirHassani, S. A. (2006). A computational approach to enhancing course timetabling with integer programming. Applied Mathematics and Computation, 175(1), 814-822. DOI: https://doi.org/10.1016/j.amc.2005.07.039
Mohd, Z. Z., Aziz, N. L. A., & Aizam, N. A. H. (2022). A general mathematical model for university courses timetabling: Implementation to a public university in Malaysia. Malaysian Journal of Fundamental and Applied Sciences, 2022, 18(1), 82–94. DOI: https://doi.org/10.11113/mjfas.v18n1.2408
Schaerf, A. (1999). A survey of automated timetabling. Artificial Intelligence Review, 13(2), 87-127. DOI: https://doi.org/10.1023/A:1006576209967
Rezaeipanah, A., Matoori, S. S., & Ahmadi, G. (2021). A hybrid algorithm for the university course timetabling problem using the improved parallel genetic algorithm and local search. Applied Intelligence, 51(1), 467-492. DOI: https://doi.org/10.1007/s10489-020-01833-x
Qu, R., & Burke, E.K. (2006). Hybridisations within a graph based hyper-heuristic framework for university timetabling problems (Report No. NOTTCS-TR-2006-1). School of CSiT, University of Nottingham.
Additional Files
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Universiti Malaysia Terengganu Journal of Undergraduate Research
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
