Random partial neighborhood search for the post-enrollment course timetabling problem

In this study, we present a local search-based algorithm for the post-enrollment-based course timetabling problem, which incorporates a mechanism for adapting the neighborhood size during the course of the search. At each iteration, the neighborhood size is changed simply by constructing a random partial neighborhood, which is defined as a random subset of the entire neighborhood. The main reason for using a random partial neighborhood is to control the trade-off between exploration and exploitation during search, and two updating strategies are considered for changing the neighborhood size. The proposed algorithms were tested using well-known benchmark sets and the results obtained were highly competitive with those produced by the leading solvers developed for these benchmark sets.