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.