一个典型的大学课程编排问题

课程表编排问题是TTP 问题之一,Even 等人[1 ]证明了TTP 问题是NP 难问题。课程表编排问题是一个解决时间和空间资源矛盾的多因素优化决策问题,即对班级、教师、时间、课程、教室等五个相互制约的基本因素进行时空安排问题。这种安排问题需要满足一定的约束条件集,如关于教室的位置与容量、时间间隔、特定课程承接关系等方面的约束条件。目前各类学校都存在着学生数量、课程设置增多,而相应的配套硬件资源没有太大变化的情况。这就要求能利用已有的资源,选择最合理的课程表编排方案。近40 年来,人们尝试着用各种方法求解此问题,如整数规划( Integer linear programming) [2 ] 、图着色( Graph cooring) [3 ] 、各种推理搜索方法[4 ] 、进化算法( Evolutionary computation) [5 ] ,等等。