A Review of Optimization Algorithms for University Timetable Scheduling
Abstract
The university course timetabling problem looks for the best schedule, to satisfy given criteria as a set of given resources, which may contain lecturers, groups of students, classrooms, or laboratories. Developing a timetable is a fundamental requirement for the healthy functioning of all educational and administrative parts of an academic institution. However, factors such as the availability of hours, the number of subjects, and the allocation of teachers make the timetable problem very complex. This study intends to review several optimization algorithms that could be applied as possible solutions for the university student course timetable problem. The reviewed algorithms take into account the demands of institutional constraints for course timetable management.
Keywords:
timetabling, genetic algorithms, Particle Swarm Optimization (PSO)Downloads
References
N. L. A. Aziz and N. A. H. Aizam, "A brief review on the features of university course timetabling problem," AIP Conference Proceedings, vol. 2016, no. 1, Sep. 2018, Art. no. 020001 DOI: https://doi.org/10.1063/1.5055403
D. M. Premasiril, "University Timetable Scheduling Using Genetic Algorithm Approach Case Study: Rajarata University OF Sri Lanka," Journal of Engineering Research and Application, vol. 8, no. 12, pp. 30-35, 2018.
E. A. Okonji, Y. M. Oluwatoyin, and O. I. Patricia, "Intelligence Classification of the Timetable Problem: A Memetic Approach," International Journal on Data Science and Technology, vol. 3, no. 2, pp. 24-33, 2017. DOI: https://doi.org/10.11648/j.ijdst.20170302.12
R. R. Iwankowicz and M. Taraska, "Self-classification of assembly database using evolutionary method," Assembly Automation, vol. 38, no. 3, pp. 268-281, Jan. 2018 DOI: https://doi.org/10.1108/AA-06-2017-071
W. Tian, W. Guo, and M. He, "On the classification of NP complete problems and their duality feature," International Journal of Computer Science & Information Technology, vol. 10, no. 1, pp. 67-78, 2018. DOI: https://doi.org/10.5121/ijcsit.2018.10106
J. Soyemi, J. L. Akinode, and S. A. Oloruntoba, "Automated Lecture Time-tabling System for Tertiary Institutions," International Journal of Applied Information Systems, vol. 12, no. 5, pp. 20-27, 2017. DOI: https://doi.org/10.5120/ijais2017451700
A. E. Phillips, C. G. Walker, M. Ehrgott, and D. M. Ryan, "Integer programming for minimal perturbation problems in university course timetabling," Annals of Operations Research, vol. 252, no. 2, pp. 283-304, May 2017 DOI: https://doi.org/10.1007/s10479-015-2094-z
M. F. Syahputra et al., "Genetic algorithm to solve the problems of lectures and practicums scheduling," IOP Conference Series: Materials Science and Engineering, vol. 308, Feb. 2018, Art. no. 012046 DOI: https://doi.org/10.1088/1757-899X/308/1/012046
R. A. Oude Vrielink, E. A. Jansen, E. W. Hans, and J. van Hillegersberg, "Practices in timetabling in higher education institutions: a systematic review," Annals of Operations Research, vol. 275, no. 1, pp. 145-160, Apr. 2019 DOI: https://doi.org/10.1007/s10479-017-2688-8
O. Y. M. Al-Rawi and T. Mukherjee, "Application of Linear Programming in Optimizing Labour Scheduling," Journal of Mathematical Finance, vol. 9, no. 3, pp. 272-285, Jun. 2019 DOI: https://doi.org/10.4236/jmf.2019.93016
I. R. Cassar, N. D. Titus, and W. M. Grill, "An improved genetic algorithm for designing optimal temporal patterns of neural stimulation," Journal of Neural Engineering, vol. 14, no. 6, Nov. 2017, Art. No. 066013 DOI: https://doi.org/10.1088/1741-2552/aa8270
A. Hussain, Y. S. Muhammad, and A. Nawaz, "Optimization through genetic algorithm with a new and efficient crossover operator," International Journal of Advances in Mathematics, vol. 2018, no. 1, pp. 1-14, 2018.
S. Muniyappan and P. Rajendran, "Contrast Enhancement of Medical Images through Adaptive Genetic Algorithm (AGA) over Genetic Algorithm (GA) and Particle Swarm Optimization (PSO)," Multimedia Tools and Applications, vol. 78, no. 6, pp. 6487-6511, Mar. 2019 DOI: https://doi.org/10.1007/s11042-018-6355-0
M. Posada, H. Andersson, and C. H. Hall, "The integrated dial-a-ride problem with timetabled fixed route service," Public Transport, vol. 9, no. 1, pp. 217-241, Jul. 2017 DOI: https://doi.org/10.1007/s12469-016-0128-9
R. Ganguli and S. Roy, "A Study on Course Timetable Scheduling using Graph Coloring Approach," International Journal of Computational and Applied Mathematics, vol. 12, no. 2, pp. 469-485, 2017.
P. Kenekayoro, "Incorporating Machine Learning to Evaluate Solutions to the University Course Timetabling Problem," Covenant Journal of Informatics and Communication Technology, vol. 7, no. 2, pp. 18-35, Dec. 2019.
A. Malikov, V. Voronkin, and S. Pevchenko, "Software and hardware infrastructure for timetables scheduling in university," CEUR Workshop Proceedings, vol. 2254, pp. 191-198, 2018.
C. Kalu, S. Ozuomba, and S. I. Umana, "Development of Mechanism for Handling Conflicts and Constraints in University Timetable Management System," in Communications on Applied Electronics, vol. 7, 24 vols., New York, USA, 2018, pp. 22-32. DOI: https://doi.org/10.5120/cae2018652804
O. Abayomi-Alli, A. Abayomi-Alli, S. Misra, R. Damasevicius, and R. Maskeliunas, "Automatic Examination Timetable Scheduling Using Particle Swarm Optimization and Local Search Algorithm," in Data, Engineering and Applications, R. K. Shukla, J. Agrawal, S. Sharma, and G. Singh Tomer, Eds. Singapore: Springer, 2019, pp. 119-130. DOI: https://doi.org/10.1007/978-981-13-6347-4_11
P. G. Daniel, A. O. Maruf, and B. Modi, "Paperless Master Timetable Scheduling System," International Journal of Applied Science and Technology, vol. 8, no. 2, pp. 58-68, Jun. 2018 DOI: https://doi.org/10.30845/ijast.v8n2a7
A. M. Hambali, Y. A. Olasupo, and M. Dalhatu, "Automated university lecture timetable using Heuristic Approach," Nigerian Journal of Technology, vol. 39, no. 1, pp. 1-14, Apr. 2020. DOI: https://doi.org/10.4314/njt.v39i1.1
K. Yonekura and Y. Kanno, "A Heuristic Method Using Hessian Matrix for Fast Flow Topology Optimization," Journal of Optimization Theory and Applications, vol. 180, no. 2, pp. 671-681, Feb. 2019. DOI: https://doi.org/10.1007/s10957-018-1404-4
E. D. Taillard, "Heuristic Methods for Large Centroid Clustering Problems," Journal of Heuristics, vol. 9, no. 1, pp. 51-73, Jan. 2003. DOI: https://doi.org/10.1023/A:1021841728075
E.-G. Talbi, "Combining metaheuristics with mathematical programming, constraint programming and machine learning," 4OR, vol. 11, no. 2, pp. 101-150, 2013. DOI: https://doi.org/10.1007/s10288-013-0242-3
S. Larabi Marie-Sainte, "A survey of Particle Swarm Optimization techniques for solving university Examination Timetabling Problem," Artificial Intelligence Review, vol. 44, no. 4, pp. 537-546, Dec. 2015. DOI: https://doi.org/10.1007/s10462-015-9437-7
A. E. Phillips, C. G. Walker, M. Ehrgott, and D. M. Ryan, "Integer programming for minimal perturbation problems in university course timetabling," Annals of Operations Research, vol. 252, no. 2, pp. 283-304, May 2017. DOI: https://doi.org/10.1007/s10479-015-2094-z
K. S. Abdallah, "Multi-objective Optimization for Exam Scheduling to Enhance the Educational Service Performance," The Journal of Management and Engineering Integration, vol. 9, no. 1, pp. 14-23, 2016.
N. Pillay, "A review of hyper-heuristics for educational timetabling," Annals of Operations Research, vol. 239, no. 1, pp. 3-38, Apr. 2016. DOI: https://doi.org/10.1007/s10479-014-1688-1
A. Cataldo, J.-C. Ferrer, J. Miranda, P. A. Rey, and A. Saure, "An integer programming approach to curriculum-based examination timetabling," Annals of Operations Research, vol. 258, no. 2, pp. 369-393, Nov. 2017. DOI: https://doi.org/10.1007/s10479-016-2321-2
C. K. Teoh, A. Wibowo, and M. S. Ngadiman, "Review of state of the art for metaheuristic techniques in Academic Scheduling Problems," Artificial Intelligence Review, vol. 44, no. 1, pp. 1-21, Jun. 2015. DOI: https://doi.org/10.1007/s10462-013-9399-6
M. Lindahl, M. Sørensen, and T. R. Stidsen, "A fix-and-optimize matheuristic for university timetabling," Journal of Heuristics, vol. 24, no. 4, pp. 645-665, Aug. 2018. DOI: https://doi.org/10.1007/s10732-018-9371-3
M. N. Mohmad Kahar and G. Kendall, "A great deluge algorithm for a real-world examination timetabling problem," Journal of the Operational Research Society, vol. 66, no. 1, pp. 116-133, Jan. 2015. DOI: https://doi.org/10.1057/jors.2012.169
V. Pereira and G. C. Helder, "Linear Integer Model for the Course Timetabling Problem of a Faculty in Rio de Janeiro," Advances in Operations Research, vol. 2016, no. 1-9, 2016, Art. no. 7597062. DOI: https://doi.org/10.1155/2016/7597062
S. Anam, "Multimodal optimization by using hybrid of artificial bee colony algorithm and BFGS algorithm," Journal of Physics: Conference Series, vol. 893, Oct. 2017, Art. no. 012068. DOI: https://doi.org/10.1088/1742-6596/893/1/012068
M. M. Najafabadi, T. M. Khoshgoftaar, F. Villanustre, and J. Holt, "Large-scale distributed L-BFGS," Journal of Big Data, vol. 4, no. 1, Jul. 2017, Art. no. 22. DOI: https://doi.org/10.1186/s40537-017-0084-5
J. Guo and A.S. Lewis. "Rescaling nonsmooth optimization using BFGS and Shor updates." 2018.
L. Su, Y. Xu, Y. Yuan, and J. Yang, "Combining Pixel Swapping and Simulated Annealing for Land Cover Mapping," Sensors, vol. 20, no. 5, Jan. 2020, Art. no. 1503. DOI: https://doi.org/10.3390/s20051503
A.-R. Hedar, W. Deabes, M. Almaraashi, and H. H. Amin, "Evolutionary Algorithms Enhanced with Quadratic Coding and Sensing Search for Global Optimization," Mathematical and Computational Applications, vol. 25, no. 1, Mar. 2020, Art. no. 7. DOI: https://doi.org/10.3390/mca25010007
J. Tassone, G. Pond, and S. Choudhury, "Algorithms for optimizing fleet staging of air ambulances," Array, vol. 7, Sep. 2020, Art. no. 100031. DOI: https://doi.org/10.1016/j.array.2020.100031
M. Xu and J. Zhou, "Elite Immune Ant Colony Optimization-Based Task Allocation for Maximizing Task Execution Efficiency in Agricultural Wireless Sensor Networks," Journal of Sensors, vol. 2020, Jan. 2020, Art. no. 3231864. DOI: https://doi.org/10.1155/2020/3231864
M. Jalal, A. K. Mukhopadhyay, and Z. Grasley, "Design, manufacturing, and structural optimization of a composite float using particle swarm optimization and genetic algorithm," Proceedings of the Institution of Mechanical Engineers, Part L: Journal of Materials: Design and Applications, vol. 233, no. 7, pp. 1404-1418, Jul. 2019. DOI: https://doi.org/10.1177/1464420718755546
M. Rezaei, M. Akbarpour Shirazi, and B. Karimi, "IoT-based framework for performance measurement: A real-time supply chain decision alignment," Industrial Management & Data Systems, vol. 117, no. 4, pp. 688-712, Jan. 2017. DOI: https://doi.org/10.1108/IMDS-08-2016-0331
H. Jafarzadeh, N. Moradinasab, and M. Elyasi, "An Enhanced Genetic Algorithm for the Generalized Traveling Salesman Problem," Engineering, Technology & Applied Science Research, vol. 7, no. 6, pp. 2260-2265, Dec. 2017. DOI: https://doi.org/10.48084/etasr.1570
R. Perez-Rodriguez and A. Hernandez-Aguirre, "A hybrid estimation of distribution algorithm for flexible job-shop scheduling problems with process plan flexibility," Applied Intelligence, vol. 48, no. 10, pp. 3707-3734, Oct. 2018. DOI: https://doi.org/10.1007/s10489-018-1160-z
C. B. Kalayci, O. Polat, and S. M. Gupta, "A hybrid genetic algorithm for sequence-dependent disassembly line balancing problem," Annals of Operations Research, vol. 242, no. 2, pp. 321-354, Jul. 2016. DOI: https://doi.org/10.1007/s10479-014-1641-3
S. Acid, L. M. de Campos, and M. Fernandez, "Score-based methods for learning Markov boundaries by searching in constrained spaces," Data Mining and Knowledge Discovery, vol. 26, no. 1, pp. 174-212, Jan. 2013. DOI: https://doi.org/10.1007/s10618-011-0247-5
R. L. Burdett and E. Kozan, "A sequencing approach for creating new train timetables," OR Spectrum, vol. 32, no. 1, pp. 163-193, 2010. DOI: https://doi.org/10.1007/s00291-008-0143-6
N. Liu, D. Plets, S. K. Goudos, L. Martens, and W. Joseph, "Multi-objective network planning optimization algorithm: human exposure, power consumption, cost, and capacity," Wireless Networks, vol. 21, no. 3, pp. 841-857, Apr. 2015. DOI: https://doi.org/10.1007/s11276-014-0822-y
M. Ehrgott, C. Guler, H. W. Hamacher, and L. Shao, "Mathematical optimization in intensity modulated radiation therapy," Annals of Operations Research, vol. 175, no. 1, pp. 309-365, Mar. 2010. DOI: https://doi.org/10.1007/s10479-009-0659-4
V. Grout, J. McGinn, and J. Davies, "Real-time optimisation of access control lists for efficient Internet packet filtering," Journal of Heuristics, vol. 13, no. 5, pp. 435-454, Oct. 2007. DOI: https://doi.org/10.1007/s10732-007-9019-1
V. K. Kaishev, D. S. Dimitrova, S. Haberman, and R. J. Verrall, "Geometrically designed, variable knot regression splines," Computational Statistics, vol. 31, no. 3, pp. 1079-1105, Sep. 2016. DOI: https://doi.org/10.1007/s00180-015-0621-7
E. Elbeltagi, M. Ammar, H. Sanad, and M. Kassab, "Overall multiobjective optimization of construction projects scheduling using particle swarm," Engineering, Construction and Architectural Management, vol. 23, no. 3, pp. 265-282, Jan. 2016. DOI: https://doi.org/10.1108/ECAM-11-2014-0135
M. Spiliotis, L. Mediero, and L. Garrote, "Optimization of Hedging Rules for Reservoir Operation During Droughts Based on Particle Swarm Optimization," Water Resources Management, vol. 30, no. 15, pp. 5759-5778, Dec. 2016. DOI: https://doi.org/10.1007/s11269-016-1285-y
Τ. M. Kumar and Ν. A. Singh, "Environmental Economic Dispatch with the use of Particle Swarm Optimization Technique based on Space Reduction Strategy," Engineering, Technology & Applied Science Research, vol. 9, no. 5, pp. 4605-4611, Oct. 2019. DOI: https://doi.org/10.48084/etasr.2969
J. Kennedy and R. Eberhart, "Particle swarm optimization," in International Conference on Neural Networks, Perth, WA, Australia, Dec. 1995.
J.-S. Pan, Z. Meng, S.-C. Chu, and H.-R. Xu, "Monkey King Evolution: an enhanced ebb-tide-fish algorithm for global optimization and its application in vehicle navigation under wireless sensor network environment," Telecommunication Systems, vol. 65, no. 3, pp. 351-364, Jul. 2017. DOI: https://doi.org/10.1007/s11235-016-0237-4
Z. Jiang, Q. Lin, K. Shi, and W. Pan, "A novel PGSA-PSO hybrid algorithm for structural optimization," Engineering Computations, vol. 37, no. 1, pp. 144-160, Jan. 2019. DOI: https://doi.org/10.1108/EC-01-2019-0025
G. Lin and J. Guan, "A Binary Particle Swarm Optimization for the Minimum Weight Dominating Set Problem," Journal of Computer Science and Technology, vol. 33, no. 2, pp. 305-322, Mar. 2018. DOI: https://doi.org/10.1007/s11390-017-1781-4
D. Wang, D. Tan, and L. Liu, "Particle swarm optimization algorithm: an overview," Soft Computing, vol. 22, no. 2, pp. 387-408, Jan. 2018. DOI: https://doi.org/10.1007/s00500-016-2474-6
Y. Ning, Z. Peng, Y. Dai, D. Bi, and J. Wang, "Enhanced particle swarm optimization with multi-swarm and multi-velocity for optimizing high-dimensional problems," Applied Intelligence, vol. 49, no. 2, pp. 335-351, Feb. 2019. DOI: https://doi.org/10.1007/s10489-018-1258-3
U. Nagalingam, B. Mahadevan, K. Vijayarajan, and A. P. Loganathan, "Design optimization for cogging torque mitigation in brushless DC motor using multi-objective particle swarm optimization algorithm," COMPEL: The International Journal for Computation and Mathematics in Electrical and Electronic Engineering, vol. 34, no. 4, pp. 1302-1318, Jan. 2015. DOI: https://doi.org/10.1108/COMPEL-07-2014-0162
M. Nouiri, A. Bekrar, A. Jemai, S. Niar, and A. C. Ammari, "An effective and distributed particle swarm optimization algorithm for flexible job-shop scheduling problem," Journal of Intelligent Manufacturing, vol. 29, no. 3, pp. 603-615, Mar. 2018. DOI: https://doi.org/10.1007/s10845-015-1039-3
R. J. Acosta-Amado, M. Villa-Marulanda, A. Garcia-Diaz, I. Atuahene, and I. C. Lacera-Cortes, "Planning Personnel Timetable: A Network Model for an Academic Application," in Industrial & Systems Engineering Research Conference, Nashville,Tennessee, Jun. 2015, pp. 2656-2663.
A. (Avi) Ceder, S. Hassold, and B. Dano, "Approaching even-load and even-headway transit timetables using different bus sizes," Public Transport, vol. 5, no. 3, pp. 193-217, Oct. 2013. DOI: https://doi.org/10.1007/s12469-013-0062-z
J. Joy and T. Nambirajan, "Automating Time Table Planning Process: Participatory Action Research," SCMS Journal of Indian Management, vol. 15, no. 4, pp. 32-51, 2018.
O. Ullrich, D. Lückerath, and E. Speckenmeyer, "Do regular timetables help to reduce delays in tram networks? It depends!," Public Transport, vol. 8, no. 1, pp. 39-56, Mar. 2016. DOI: https://doi.org/10.1007/s12469-015-0115-6
M. A. Al-Betar and A. T. Khader, "A harmony search algorithm for university course timetabling," Annals of Operations Research, vol. 194, no. 1, pp. 3-31, Apr. 2012. DOI: https://doi.org/10.1007/s10479-010-0769-z
Downloads
How to Cite
License
Copyright (c) 2020 Authors
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License 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) after its publication in ETASR with an acknowledgement of its initial publication in this journal.
