Parallel Genetic Algorithm for High School Timetabling

The high school timetabling problem is a combinatorial optimization problem, proved to be NP-hard. It is a task to assign class–teacher interactions to rooms and timeslots of a weekly schedule. The nature of the problem varies depending on the region and institution. It has several hard and soft constraints. It means finding an assignment, such that no hard constraints are violated and the number of violations of soft constraints is minimized. Large and complex high school timetabling problem taken from real life, often takes long time to do manually. Hence, automated timetabling has attracted researchers since 1980s and many techniques have been proposed to solve it. Genetic Algorithm can be effectively used to solve such difficult problem. We propose the Parallel Genetic Algorithm (PGA) with customized operators and probabilistic repair to solve “hard timetabling” test problems hdtt4, hdtt5 and hdtt6 given by Professor Kate Smith-Miles in OR-Library. The optimal objective function for each of these problems is no clashes and fulfilling teacher’s workload on each class in given room. The functions are designed for intelligent operators and repair. The PGA consisting operators augmented with problem specific knowledge and probabilistic repair in crossover converges