Stratified random sampling technique for integrated two-stage multi-neighbourhood tabu search for examination timetabling problem

In this research, we introduce a stratified random sampling technique that guides the selection mechanism to select the events (exams) for the integrated two-stage multi-neighbourhood tabu search (ITMTS) in solving examination timetabling problem. This technique is used during the timetable improvement phase especially when dealing with the exhaustive search mechanism in order to reduce the possibilities of extensive neighbors evaluation in finding good neighbours, without scarifying (too much) on the performance of the ITMTS. The selection mechanism only selects a set of exams (that represents a whole exam population) for every exhaustive evaluation of ITMTS. Therefore, this strategy can speed up the searching process and might lead the ITMTS to search in more promising area. We test and evaluate this strategy on the uncapacitated Carter benchmark datasets by using the standard Carter´s proximity cost. Our results are comparable with other approaches that have been reported in the literatures subject to the Carter´s benchmark datasets.