عنوان مقاله [English]
The university course timetabling problem (UCTP) is a crucial yet intricate task for academic departments. UCTP is classified 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-worldhard and soft constraints and developing a hyper-heuristic algorithm as an efficient 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, five strategies for implementing them, and four heuristics for choosing time slots. The modified ICA is a bi-objective and constructive algorithm, while the original is a single-objective and improvement-based algorithm. The modified 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.