The Application of Late Acceptance Heuristic Method for the Tanzanian High School Timetabling Problem

Abstract

High School timetabling is the problem of scheduling lessons of different subjects and teachers to timeslots within a week, while satisfying a set of constraints which are classified into hard and soft constraints. This problem is different from university course timetabling problem because of the differences in structures including classroom allocations and grouping of subject combinations. Given the scarce education resources in developing countries, high school timetabling problem plays a very important role in optimizing the use of meager resources and therefore contribute to improvement of quality of education. The problem has attracted attention of many researchers around the world; however, very little has been done in Tanzania. This paper presents a solution algorithm known as Late Acceptance heuristic for the problem and compares results with previous work on Simulated Annealing and Great Deluge Algorithm for three schools in Dar es Salaam Tanzania. It is concluded that Late Acceptance heuristic gives results which are similar to the previous two algorithms but performs better in terms of time saving.  
 
Keywords: Late Acceptance, High School Timetabling, Combinatorial Optimization, Heuristics, NP-Hard