Random partial neighborhood search for the post-enrollment course timetabling problem. (February 2018)

• Record Type: Journal Article
• Authors: Nagata, Yuichi
• Is Part Of: Computers & operations research. Volume 90(2018)
• Page Start: 84
• Page End: 96
• Publication Date: 2018-02
• Subjects: Candidate list -- Partial neighborhood -- Tabu search -- Timetabling; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2017.09.014
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A local search-based algorithm that incorporates a mechanism for adapting the neighborhood size during the course of the search is developed for the post-enrollment-based course timetabling problem. The trade-off between exploration and exploitation during search can be controlled simply by adjusting the neighborhood size. The proposed local search-based algorithm with an appropriate updating strategy for the neighborhood size and neighborhood structure obtains highly competitive performance compared with the leading solvers developed for the well-known Socha et al., ITC-2002, and ITC-2007 benchmark sets, despite its simplicity. Abstract: 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.