Study On The Genetic Algorithms For The Timetabling Problem

The timetabling problem (TP) is an NP-hard multiobjective combinatorial optimization problem with constraints. Therefore, it is much unlikely that there exist a polynomial-time algorithm for the TP.Genetic algorithms (GAs) are a large class of efficient randomly searching algorithms that mimic the evolution of species, which are often employed to approximately solve NP-hard Problems. This thesis is aimed at solving the TP using GA. The main work of this thesis is listed below.â‘ The formal description of the TP is presented. The reason why the TP is computationally hard is explained. An effective approach to treating the TP is described.â‘¡Through a quantitative analysis of the TP with multiple fuzzy objectives, the solution space is established.â‘¢A chromosome coding scheme and a heredity operator are designed for solving the TP, and a multiobjective concordance decision-making model is built up. A fusion of these items leads to a new fitness function. On this basis, a new timetabling algorithm is proposed, which is justified with a numerical example.