Research On Application Of TS Algorithm To The Solution Of Course-timetabling Problem

Course-timetabling problem, an optimization decision-making problem involving factors such as classes, teachers and classrooms etc, is a typical problem of combinatorial planning. In an automated-course-timetabling system, the algorithm of course timetabling enjoys the core status, but it is rather difficult for us to find an effective processing algorithm due to the complexity of the course-timetabling problem itself. The subject studied in this paper originates from the research on the algorithm of automatic course-timetabling problem.This paper introduced a method to solve the course-timetabling problem based on taboo search. First, uses the network max-flow algorithm in preprocessing to divide the teaching tasks into several groups, in which the tasks can be carried on simultaneously without collisions and the number of the required classrooms not lager than the number of the supplied ones. Second, seeks a best combination between task groups and time slots using taboo search. Last, assigns a classroom to every teaching task and outputs the course timetable.This paper proposes an outline of the algorithm at first. Then, a detailed explanation is given on how to establish the network-flow model as well as how to use the essential factors in taboo search. Finally, uses the real data to carry out the simulation test.The implementation of the plan, which unifies the classical network flows algorithm and the modern heuristic taboo search algorithm, causes the superiorities of two algorithms supplementing each other, and improves the ability of processing problems. After confirmed through the real data simulation, the algorithm which this paper proposed is of certain feasibility and the serviceability.