The Research On The Time Tabling Problem (TTP)

Timetable Problem(TTP) is a special problem of resource arrangement which is widely applied in course scheduling problem(CSP),all sorts of large conferences,sports games and plane scheduling problem. How to resolve TTP is a key point. This paper introduces a method based on the graphics theory and the artificial intelligence that to resolve the TTP.In essence, the graph coloring theory is a partition problem. It divided the points which conflict with each other into different subsets. Based on this instinct, graph theory has been used widely to solve the problem that need to solve the conflict problem.Genetic algorithm is an intelligent algorithm that simulates the process of biological evolution. As a new algorithm of overall optimized search, it has achieved broad application in solving optimization problems due to such distinctive features as simplified process, universality, robustness and availability of parallel processing. Genetic algorithm has become an effective method to resolve NP completeness problem.General speaking, CSP is a part of constraint satisfaction problem. Employing vertex coloring of graph theory, we can easily transfer the CSP into a solvable problem. For CSP has to assign each course a specific time slot, this study is the first ever to construct three lays of graphs, named as weekday, daily, and room graphs to simplify the problem. The nodes are then defined as teacher, course, timetable and classroom. The edge connected two nodes means confliction, which says both of the two nodes not existence simultaneously.The emphasis of this paper is to solve the graph model. To solve the model, this paper brings forward two methods. The first one is group genetic algorithm, the second one is merge model.