AUTOMATED UNIVERSITY COURSE TIMETABLING USING HYPER-HEURISTIC APPROACH

The university course timetabling problem (UCTP) is a crucial yet intricate task for academic departments. UCTP is classied as an NP-hard problem; therefore, a simple solution may not be applicable to it. However, recently, hyper-heuristic algorithms, as a new approach, can automatically generate solutions. A hyper-heuristic algorithm consists of one or two high-level heuristics and several low-level heuristics. The low-level heuristics are responsible for generating or improving the initial solution, while the high-level heuristics are used to select the best low-level heuristics for achieving better solutions.
This paper aims to produce timetables by mathematical modelling of real-world hard and soft constraints and developing a hyper-heuristic algorithm as an ecient solution. In formulating the mathematical model of UCTP, it is considered that certain classes are pre-allocated to departments. Additionally, some three- and four-unit courses are held in two sessions per week, following the traditional patterns of Saturday-Monday, Sunday- Tuesday, and Monday-Wednesday (assuming Saturday to Wednesday as the workweek). There is also the possibility of following new patterns, such as Saturday- Tuesday and Sunday-Wednesday.
The proposed hyper-heuristic is based on a customized Imperialist Competitive Algorithm (ICA) as a high-level heuristic. It utilizes nine low-level heuristics, ve strategies for implementing them, and four heuristics for choosing time slots. The modied ICA is a bi-objective and constructive algorithm, while the original is a singleobjective and improvement-based algorithm. The modi ed ICA has a variable self-tuned parameter and two assimilation process in strategic and operational level. The low-level heuristics refer to selecting courses for allocation that are pre-allocated, limited in time or location, most limited, most limited in remaining slots, most crowded, longest time, in the heaviest group, belong to a highly participated lecturer, or belong to faculty members.
The hyper-heuristic algorithm was programmed in MATLAB 2018b and ran on a PC with an Intel Core i5 3450 CPU and 8 GB of RAM. The algorithm was tested using real data from Shiraz University. The results revealed that the hyper-heuristic algorithm can generate 10 distinct timetables within a runtime of 17 hours, without the need for human intervention. The best-produced timetable can increase class utilization by up to 11% and reduce student average waiting time by one hour per week.