Adaptive Tabu Search for course timetabling

作者：Lue Zhipeng; Hao Jin Kao

来源：European Journal of Operational Research, 2010, 200(1): 235-244.

DOI：10.1016/j.ejor.2008.12.007

• Timetabling
• Heuristic
• Tabu Search
• Iterated Local Search
• Perturbation operator
• ITC-2007

This paper presents an Adaptive Tabu Search algorithm (denoted by ATS) for solving a problem of curriculum-based course timetabling. The proposed algorithm follows a general framework composed of three phases: initialization, intensification and diversification. The initialization phase constructs a feasible initial timetable using a fast greedy heuristic. Then an adaptively combined intensification and diversification phase is used to reduce the number of soft constraint violations while maintaining the satisfaction of hard constraints. The proposed ATS algorithm integrates several distinguished features such as an original double Kempe chains neighborhood structure, a penalty-guided perturbation operator and an adaptive search mechanism. Computational results show the high effectiveness of the proposed ATS algorithm, compared with five reference algorithms as well as the current best known results. This paper also shows an analysis to explain which are the essential ingredients of the ATS algorithm.

• 出版日期2010-1-1