Complex University Timetabling Using Iterative Forward Search Algorithm and Great Deluge Algorithm

I Gusti Agung Premananda(1*), Ahmad Muklason(2),

(1) Institut Teknologi Sepuluh Nopember
(2) Institut Teknologi Sepuluh Nopember
(*) Corresponding Author
DOI: https://doi.org/10.23917/khif.v7i2.12879

Abstract

University timetabling is an issue that has received more attention in the field of operations research. Course scheduling is the process of arranging time slots and room for a class by paying attention to existing limitations. This problem is an NP-Hard problem, which means the computation time to find a solution increases exponentially with the size of the problem. Solutions to problems of this kind generally use a heuristic approach, which tries to find a sufficiently good (not necessarily optimal) solution in a reasonable time. We go through two stages in solving the timetabling problem. The first stage is to schedule all classes without breaking any predefined rules. The second stage optimizes the timetable generated in the first stage. This study attempts to solve the class timetabling problem issued in a competition called the 2019 International Timetabling Competition (ITC 2019). In the first stage, we use the Iterative Forward Search (IFS) algorithm to eliminate timetable candidates and to generate a schedule. In the second stage, we employ the Great Deluge algorithm with a hyper-heuristic approach to optimize the solution produced in the first stage. We have tested the method using 30 datasets by taking 1,000,000 iterations on each dataset. The result is an application that does schedule elimination and uses the IFS algorithm to produce a schedule that does not violate any of the hard constraints on 30 ITC 2019 datasets. The implementation of the Great Deluge algorithm optimizes existing schedules with an average penalty reduction of 42%.

Keywords

timetabling; class scheduling; iterated forward search; international timetabling competition

Full Text:

PDF

References

Lindahl, M., Mason, A. J., Stidsen, T. and Sørensen, "A strategic view of University timetabling," European Journal of Operational Research, vol. 226, no. 1, pp. 35-45, 2018.

V. I. Skoullis, . I. X. Tassopoulos and G. N. Beligiannis, "Solving the high school timetabling problem using a hybrid cat swarm optimization based algorithm," Applied Soft Computing, vol. 52, pp. 277-289, 2017.

M. Chen, X. Tang, T. Song, C. Wu, S. Liu and X. Peng, "A Tabu search algorithm with controlled randomization for constructing feasible university course timetables," Computers and Operations Research, pp. 1-20, 2020.

J. S. Tan, S. L. Goh, G. Kendall and N. R. Sabar, "A survey of the state-of-the-art of optimisation methodologies in school timetabling problems," Expert Systems With Applications, vol. 165, 2021.

T. Thepphakorn and P. Pongcharoen , "Performance improvement strategies on Cuckoo Search algorithms for solving the university course timetabling problem," Expert Systems with Applications, no. 161, 2020.

L. Saviniec and A. A. Constantino, "Effective local search algorithms for high school timetabling problems," Applied Soft Computing, vol. 60, pp. 363-373, 2017.

A. Rezaeipanah, S. S. Matoori and G. Ahmadi , "A hybrid algorithm for the university course timetabling problem using the improved parallel genetic algorithm and local search," Applied Intelligence, no. 51, p. 467–492, 2021.

T. Song, S. Liu, X. Tang, X. Peng and M. Chen, " An iterated local search algorithm for the University Course Timetabling Problem," Applied Soft Computing, vol. 68, pp. 597-608, 2018.

T. M¨uller, R. Bart´ak and H. Rudov´a, "Iterative Forward Search Algorithm: Combining Local Search with Maintaining Arc Consistency and a Conflict-Based Statistics," Principles and Practice of Constraint Programming - CP, vol. 3258, 2004.

Rudová, H., Müller, T. and Murray, K., "Complex university course timetabling," Journal of Scheduling, vol. 14, no. 2, p. 187–207, 2010.

A. Muklason, G. B. Syahrani and A. Marom, "Great Deluge Based Hyper-heuristics for Solving Real-world University Examination Timetabling Problem: New Data set and Approach," The Fifth Information Systems International Conference 2019, pp. 647-655, 2019.

T. M¨uller , ·. H. Rudov´a and Z. M¨ullerov´a, "University course timetabling and International Timetabling Competition 2019," Proceedings of the 12th International Conference on the Practice and Theory of Automated Timetabling (PATAT-2018), pp. 5-31, 2018.

Article Metrics

Abstract view(s): 624 time(s)
PDF: 505 time(s)

Refbacks

  • There are currently no refbacks.