Iterated two-stage multi-neighbourhood tabu search approach for examination timetabling problem

摘要

In this research, we introduce a set of multi-neighbourhood strategies of iterated two-stage tabu search, ITMTS, to solve examination timetabling problems. This work is based on the standard tabu search with some modifications that are derived from the neighbourhood structure. The neighbourhood structure has divided the neighbourhood search mechanism into two stages, vertical neighbourhood search and horizontal neighbourhood search. These search mechanisms will work alternately with different neighbourhood concentration and candidate evaluation. We test and evaluate ITMTS with the uncapacitated Carter benchmark datasets and standard Carter's proximity cost. Our results are comparable with other approaches that have been reported in the literature with regards to the Carter's benchmark dataset and have shown as a promising technique to be further enhanced.