A multiswap algorithm for the university course timetabling problem

Being a complex computational optimisation problem, the university course timetabling involves assignment of events to timeslots and rooms on a weekly basis. In handling the problem, the hard and soft constraints must be addressed to ensure that a feasible and (near) optimal timetable is obtained. Since assigning rooms to events is an integral part of the university course timetabling, this paper is particularly concerned of the previously-overlooked room operations (any operation performed between the room and the event in the same timeslot). The proposed MultiSwap algorithm contributes to major improvement in processing the room operations. This is achieved by combining the MultiSwap algorithm with the graph coloring heuristic method to satisfy the hard constraints and with the local search-based algorithms to minimize the violations of the soft constraints. In this paper, the MultiSwap is incorporated with the largest weighted degree and backtracking algorithms on one hand to satisfy the hard constraints, and is incorporated with local search algorithm to minimize the violation of soft constraints. Using the standard dataset of Socha prepared for the university course timetabling, the results show that the room operations can further enhance the performance of heuristic methods and local search-based algorithms.