A Human-computer Cooperation Approach For University Course Timetabling Problem Under Uniform Teaching Resources

University course timetabling problem (UCTP) is the most important and complex work in teaching system. With the continuous expansion of colleges’ graduate admissions and the continuous deepening of the reform of education, students enrollment increasing rapidly, the number of classes and courses has grown substantially, the timetable planning based on the uniform teaching resources of a university becomes more and more complex. Artificial process is time-consuming and easy to cause confusion of arranging results, but machine arrangement is lack of flexibility. Therefore, man-machine coordinated process becomes urgent to solve the problem of timetabling.In the early 1976, university course timetabling problem has been proved to be a NP complete problem by S.Even. The nature of UCTP is arrange school courses to the limited class and the teaching resources, under the condition of satisfy the constraints. Although there are a lot of research on UCTP, but it has not been solved well for decades.Greedy algorithm is a kind of algorithm simplify the complexity of the problem. Greedy algorithm adopt iterative select top down method, according to the greedy strategy to solve the local optimal solution. Greedy arithmetic gets going from an initial solution to problem, through a series of greeding chosen which is best chosen at currently status, and it gets the aim step by step, hope to get the better solution as possible as it can. When it reaches a step cannot resumption, the arithmetic will stop.The paper starts by providing an overview about curriculum scheduling problem. Then, it introduces the research status and development trend of this issue at home and abroad. Thirdly, in this paper, a human-computer cooperation approach for UCTP is presented with considering complex multi-constraint conditions based on the uniform teaching resources which include students, teachers and classrooms with feasible timeslot, respectively. Firstly, the objective function is generated based on the evenness for all the curriculums of a student and the satisfaction of a teacher who teaches a curriculum and the walking distance of student. And then, transform the constraints to relational operation expressed by relation algebra, thereby heuristic rules are formed. Greedy algorithm is applied to search the optimal solutions in the shrunk solution space. Finally, a course timetabling instance from a university is carried out to demonstrate the validation of the new method.