Combining the Min-Conflicts and Look-Forward Heuristics to Effectively Solve A Set of Hard University Timetabling Problems

Abstract

University timetabling problems (UTPs) represent a class of challenging, high-dimensional and multi-objectives combinatorial optimization problems that are commonly solved by constructive search, local search methods or their hybrids. In this paper, we proposed to combine the min-conflicts and look-forward heuristics used in local search methods to effectively solve general university timetabling problems. Our combined heuristics when augmented with the k-reset operator, and appropriate heuristic variable ordering strategy achieved impressive results on a set of challenging UTPs obtained from an international timetabling competition. A preliminary analysis of the results was given. More importantly, our search proposal shed light on effectively solving other complex or large-scale scheduling problems.