自约束和关系约束
优化约束与解的质量
改进回溯算法
高校排课问题
在高校排课问题中,一个排课任务是指为一次教学任务做出的场地及时间的选择,这种选择必须满足教学任务自身的条件需求,并且不能与其他排课任务发生冲突。
这里,排课任务是变量,可供选取的资源为问题的值域,而需求与冲突就是约束。
由上可见,排课问题可以看做一个约束满足问题,问题的求解表现为对各排课任务寻找满足约束的资源,解的优劣也可以通过约束来表征。
变量及值域
在高校排课问题中,排课任务应具有课程、教师、班级、教学场地、教学时间等基本属性。
为便于问题的简化,不妨将教学场地和教学时间看作排课任务的一个属性。在这里,教学场地与教学时间同时也具有自身的属性。
自约束
自约束:指由单一排课任务自身的条件需求而规定。
例如:排课任务对教学场地的类别、容量的要求及教学时间节次的要求
初始化过程中,可以将其作用于相应排课任务的值域。
关系约束
关系约束通常是动态的二元或高阶约束,但高阶约束一般总可以转化为二元约束,一个排课任务的取值通过关系约束而受到相关排课任务的影响。如为回避冲突而规定的约束、保证同一课程的不同教学任务有合理的时间间隔及使其在相同地点进行而规定的约束,都是典型的关系约束。由于关系约束是动态的,它们一般在求解过程中由相关排课任务的赋值来触发。
约束举例
某排课任务具有自约束:
两个具有相同班级的排课任务具有关系约束:
它由对的赋值来触发。
优化约束与解的质量
高校排课问题具有多个优化目标,将目标通过约束表征而得到高质量解的间接求解方法,通常是有效的。
优化约束是针对高校排课问题的优化目标而建立的约束。它可以是自约束,也可以是关系约束。当排课问题的解满足连同优化约束在内的约束条件时,则可以认为解是高质量的。
最小剩余值启发 |
转播
