An effective constraint-aware optimization method for university course timetabling problem

摘要

University course timetabling is known to be hard combinatorial optimization problem. It is difficult to tackle the constraints including the classroom, course and the teacher requirement. Some optimization approaches have been proposed in order to solve this kind of problem, one of the efficient solution methods for this problem is tabu search. But these methods little take attention to the constraint relationships, mainly concern the conflict circumstances. In this paper, constraint-aware modeling method is proposed based on the fuzzy Petri net, which can respect the constraint relationships among the courses, the classrooms and the teachers. Then we locate the best legal firing sequences in the constraint model by the differential evolution (DE) method, in order to obtain the optimal course timetabling plan. The theoretical analysis and specific example show that the method is very effective.