2 目前流行得几种排课算法得介绍 2.1、 自动排课算法 1 、问题得描述 我们讨论得自动排课问题得简化描述如下: 设要安排得课程为{ C1 , C2 , 、, Cn} ,课程总数为n , 而各门课程每周安排次数(每次为连续得2 学时> 为{ N1 , N2 , 、, Nn} 。每周教案日共5 天,即星期一～ 星期五。每个教案日最多安排4 次课程教案,即1 ～ 2 节、3 ～ 4 节、5 ～ 6 节与7 ～ 8 节(以下分别称第1 、2 、3 、4 时间段> 、 在这种假设下,显然每周得教案总时间段数为5 ×4 = 20 ,并存在以下约束关系:

n ≤20 , (1> N = 6n, i =1, Ni ≤20、 (2> 自动排课问题就是:设计适当得数据结构与算法, 以确定{ C1 , C2 , 、, Cn } 中每个课程得教案应占据得时间段,并且保证任何一个时间段仅由一门课程占据、

2 、主要数据结构 对于每一门课程,分配2 个字节得“时间段分配字”(无符号整数> :{ T1 , T2 , 、, Tn} 、 其中任何一个时间段分配字(假设为Ti > 都具有如下格式:

Ti 得数据类型C 语言格式定义为:unsigned int 、 Ti 得最高位就是该课程目前就是否就是有效得标志,0 表示有效,1 表示无效(如停课等> 。其它各位称为课程分配位, 每个课程分配位占连续得3 个位(bit> ,表示某教案日(星期一～ 星期五> 安排该课程得时间段得值,0 表示当日未安排,1 ～ 4 表示所安排得相应得时间段(超过4 得值无效> 、

在这种设计下, 有效得时间段分配字得值应小于32 768 (十六进制8000> , 而大于等于32 768 得时间段分配字对应于那些当前无效得课程(既使课程分配位已设置好也如此> , 因此很容易实现停课/ 开课处理、

3 、排课算法 在上述假设下,自动排课算法得目标就就是确定{ C1 , C2 , 、, Cn} 所对应得{ T1 , T2 , 、, Tn} 、

从安排得可能性上瞧,共有20 !/ (20 - N> !种排法( N 得含义见(2> 式> 、 如果有4 门课,每门课一周上2 次,则N = 8 ,这8 次课可能得安排方法就会有20 !/ (20 - 8> ! = 5 079 110 400 ,即50 多亿种、 如果毫无原则地在其中选择一种方案,将会耗费巨大量得时间、 所以排课得前提就是必须有一个确定得排课原则、 我们采用轮转分配法作为排课原则:从星期一第1 时间段开始按{ C1 , C2 , 、, Cn} 中所列顺序安排完各门课程之后(每门课安排1 次> ,再按该顺序继续向后面得时间段进行安排,直到所有课程得开课次数符合{ N1 , N2 , 、, Nn} 中给定得值为止、 在算法描述中将用{ C[1 ] , C[2 ] , 、, C[ n ]} 表示{ C1 , C2 , 、, Cn} , 对{ N1 , N2 , 、, Nn}

与{ T1 , T2 , 、, Tn} 也采用同样得表示法、 算法1 排课算法 输入 { C1 , C2 , 、, Cn} 、{ N1 , N2 , 、, Nn} 、 输出 { T1 , T2 , 、, Tn} 、 ① 初始化: 星期值week = 1 时间段值segment = 1 { T [1 ] , T [2 ] , 、, T [ n ]} 中各时间段分配字清零 ② 新一轮扫描课程: 置继续处理标志flag = 0 对课程索引值c-index = 1 ,2 , 、, n 进行以下操作: 如果N[c-index ] > 0 ,则做以下操作: 把segment 得值写入T[c-index ]得第(week - 1> 3 3～week 3 3 - 1 位中 N[c-index ]得值减1

如果N[c-index ] > 0 ,则置flag = 1 如果week = 5 并且segment = 4 则:置flag = 1 并转③ 否则:如果segment = 4 则:置segment = 1 且week 增1 否则:segment 增1 检测就是否已全部安排完毕: 如果flag = 1 则:转② 否则:转③ ③ 检测就是否成功: 如果flag = 1 则:开课次数过多 否则:课程安排成功 ④ 算法结束 显然,本算法得时间复杂度为O ( N> ( N 为每周总开课次数, 见(2> 式> , 而存储时间段分配字所用空间为2 n 个字节( n 为课程门数> 、

4 、冲突检测算法 有时在自动排课完毕后,需要人工调整某些课程得安排时间,如把第i 门课程在人工干预下改成星期数为week 、时间段为segment 得位置,则根据上述数据结构需做如下运算:

T [ i ] = T [ i ] &(～ (7 << (week - 1> * 3> > + (segment << (week - 1>*3> , 其中&、～ 与n 分别为按位与、按位取反与按位左移运算符(下同> 、 问题就是如何判断就是否已有其它课程安排在同一个时间段上、 设人工调整得时间段分配 字为T[1 ] ,则该问题描述为:判断时间段分配字T [1 ] 与{ T[2 ] , T [3 ] , 、, T [ n ]} 中得某个分配字就是否存在相同课程分配位上得相等得非零时间段值, 或者说{ T [2 ] , T [3 ] , 、,T[ n ]} 中就是否存在与T [1 ] 冲突得时间段分配字、 为简化起见,在以下算法描述中假设所有时间段分配字得最高位为0、 算法2 冲突检测算法 输入 T1 与{ T2 , 、, Tn} 、 输出 与T1 冲突得{ T2 , 、, Tn} 中得时间段分配字、 ① 对c-index = 2 ,3 , 、, n 做以下操作: 初始化屏蔽字mask = 7 对星期值week = 1 ,2 ,3 ,4 ,5 做以下操作: 如果T[1] & mask 等于T[c-index] & mask ,而且二者不等于0 则: T[ 1 ]与T[c-index ]相冲突,转① mask 左移3 位(或乘8> ② 算法结束 本算法时间复杂度为O ( n> ( n 为课程门数> 5、算法分析

此算法以课程为中心,进行搜索匹配,取最先匹配得值;具有占有空间少,运算速度快得特点。但其未对数据进行择优选取,所以不能对教案资源殊要求合适些,有些课程不能安排到上午等)。

2.2 基于优先级得排课算法 从数学上讲, 排课问题就是一个在时间、教师、学生与教室四维空间, 以教案计划与各种特殊要求为约束条件得组合规划问题。其实质就就是解决各因素之间得冲突。在设计算法时, 为了降低课程调度得算法复杂性, 我们主要采用了化整为零得思想及优先级算法:

1.排课得预处理 1.等价类得划分 将具有共同听课对象得任务划分在同一等价类中, 在每个等价类之间只存在地点上得冲突, 而没有时间上得冲突。 然后按照得大小, 从大到小进行处理。 等价类得划分可以先按年级分, 然后再按系别分, 如下 所示:

听课对象等价类得划分 自控系机械系化工系管理系、 99 级N 1 子类1 子类2 子类3 子类4 、 98 级N 2 子类5 子类6 子类7 子类8 、 97 级N 3 子类9 子类10 子类11 子类12 、 96 级N 4 子类13 子类14 子类15 子类16 、 这样, 先按年级分为四个类: 99 级(N 1> , 98 级(N 2> , 97 级(N 3> , 96 级(N 4> , 而对每一个等价类N 1、N 2、N 3、N 4 又可以按院系分为若干个子类, 然后对每个子类分别进行排课处理, 这样做就可以大大降低算法得复杂性

2.教室分类 为了合理使用教室, 我们采用了教室分类得办法, 以便尽可能在课程编排过程中避免上课人数少得课程盲目强占容量大得教室现象。

首先将教室按照其类型分为若干个等价类, 如下所示,然后, 根据教室得容量再分别对每个教室等价类进行划分: 如分为0～ 30 人、30～ 60 人、60～90 人、90～ 120 人、120～ 180 人等若干种

教室等价类得划分: 教室类型等价类R 教室类型等价类R 普通教室R1 听力教授R5 投影教室R2 物理实验室R6 多媒体教室R3 化学实验教室R7 制图教室R4 计算机实验教案R8 3、时间预处理 1> 构造时间模式库 时间模式就是根据教务人员得经验, 为各种周学时数不同得课程指定得一种时间组合方式、例如, 一门课程得周学时数为4, 那么它得时间组合方式可以有:“11”,“41”。 表示该课程一周上两次, 分别为周一得12 节与周四得12 节L同时, 为了达到较好得上课效果, 也要对这些时间模式进行分级、如下 所示

时间模式分级举例 周学时优先级周一周二周三周四周五 4 1 11 41 ∶∶ 4 2 22 43 : : 其中, 将周一至周五用数字1～ 5 表示, 上课节次: 12 节、34 节、56 节、78 节、晚12 节、晚34 节分别用数字1～ 6 表示。 例如数字“42”表示周四得34 节

这个时间单元。这样, 对于每种周学时数, 可以将所有合理得时间组合形式存入模式库中。以便进行时间处理时可以用时间模式库中得各种模式进行匹配。

2> 时间数组 为了表示班级、教师、教室得可排课时间, 分别为她们建立一维数组L例如, 某位教师得初始可排课时间数组为(123456 123456 123456 123456 123456>。 其中共有五组数据, 分别表示一周中得五天。 而一组数据共有6 个字符“1、2、3、4、5、6”分别表示一天中得六个时间单元。 当为某位教师分配时间后, 相应得那位字符就置为0L 例如, 某位教师得可排课时间数组为( 020456 103456 003456 120456 023456> , 则表示这位教师在周一得12 节与56 节, 周二得34 节, 周三得12 节与34 节, 周四得56 节, 周五得12 节已经安排了课程, 如果要再安排课程得话, 就应该安排在非0 得时间单元L对于班级与教室也可以进行同样得处理, 分别标出可排课时间。

2. 每一子类得排课处理