一种新的课表安排问题的可行解构造算法

A New Algorithm for Constructing Feasible Solution for Timetabling Problems

课表安排问题实质上就是要求将学校开设的所有课程,在满足一定的约束条件下,合理地安排到有限的课时和教室资源上。课表安排问题的困难在于,必须把大量的课程安排到紧缺的资源上,同时不能违反各种苛刻的客观约束和主观约束。这些约束通常分为硬约束和软约束,并定义满足所有硬约束的课表为可行解,而违反最少软约束的可行解为最优解。本文提出了一种基于定向搜索的课表压缩算法来解决可行解的构造问题。算法已经在UCTP实例上进行测试,通过与其他高校算法相比较,验证了算法的高效性。

The course timetabling problem is concerned with the scheduling of a number of courses into some limited resources,such as rooms and timeslots,subject to a set of constraints. The biggest difficulty of the timetabling problem is that we have to schedule all the courses to some limited resource,subject to many subjective and objective constraints. These constraints can be classified into hard and soft constraints. Any feasible timetable has to satisfy all hard constraints. On the other hand,soft constraints are not compulsory but should be satisfied as many as possible. This paper designs a new algorithm based on the proposed One-Way search strategy for constructing feasible solution for timetabling problems. This algorithm was tested on the UCTP benchmarks and the computational results were compared with some algorithms. We finally come to conclusion that our algorithm is outstanding and can compete with other effective approaches.