Application of Genetic Algorithms In Scheduling Problems

Abstract

Timetabling is one of the scheduling problems. It is NP hard and it is well known that these problems can be transformed to other NP hard problems. So we decided to focus on one of the representative problems namely school timetabling. Our approaches implemented using several variants of genetic algorithms were tested primarily with the hard timetabling test problems hdtt4, hdtt5, hdtt6, hdtt7 and hdtt8. These datasets are provided by Prof. Kate Smith-Miles in OR-Library. OR-Library is a collection of test data sets for a variety of OR problems. They are hard as all resources are to be allocated in all available timeslots. Hence it is difficult to obtain clash-free timetables; they are highly constrained and thus too difficult. Two hybrid approaches genetic algorithm along with tabu search and genetic algorithm along with simulated annealing are also used to solve them. The optimal objective function for each of these problems is no clashes and fulfilling teacher s workload on each class in given room. The execution times are compared with the recent work carried out using different methodologies on same data set. The techniques reduce overall computational time while generating optimal solutions. newlineFirst we applied successfully the genetic algorithm to real time problem, the departmental timetable of Dr. B. A. Technological University, Lonere. However we decided to move to standard datasets so as to compare our results with approaches proposed by other researchers. The simple genetic algorithm is then applied on all hard timetabling problems. First a suitable chromosome structure is designed for hdtt problem and the genetic algorithm parameters like population size, number of generations, mutation rate, crossover rate, selection type etc. are properly chosen. The GA run is often sensitive to these parameter values hence selection of parameters is important otherwise it leads to longer execution times or suboptimal results. The algorithm gives results for hdtt4 but not for other problems even after execution for