Development of a scheduling tool for constructing a Malaysian school timetable using genetic algorithms / Salihin Farag Shoeeb - Salihin Farag , Shoeeb (2003)
The school timetabling problem is essentially the construction of a timetable for each teacher and class that satisfies the teacher requirements and which does not violate the condition that no teacher or class is scheduled more than once in the same time period. It belongs to a class of scheduling problems which is highly constrained and which is known to be NP-hard and NP-complete. A feasible timetable is one which satisfies all the hard constraints. However, to obtain a good quality timetable we have to satisfy as many soft constraints as possible. A recent approach to derive a near-optimal solution is to use evolutionary or genetic algorithms. In this project, we describe in detail the school timetable problem and present the genetic algorithm employed to construct the timetable for a typical Malaysian schools.