《精品毕业论文--目前流行的几种排课算法的介绍》由会员分享，可在线阅读，更多相关《精品毕业论文--目前流行的几种排课算法的介绍（19页珍藏版）》请在金锄头文库上搜索。
1、目前流行的几种排课算法的介绍21. 自动排课算法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)自动排课问题是:设计
2、适当的数据结构和算法, 以确定 C1 , C2 , ., Cn 中每个课程的教学应占据的时间段,并且保证任何一个时间段仅由一门课程占据.2 .主要数据结构对于每一门课程,分配2 个字节的“时间段分配字”(无符号整数) : T1 , T2 , ., Tn . 其中任何一个时间段分配字(假设为Ti ) 都具有如下格式:Ti 的数据类型C 语言格式定义为:unsigned int . Ti 的最高位是该课程目前是否是有效的标志,0 表示有效,1 表示无效(如停课等) ;其它各位称为课程分配位, 每个课程分配位占连续的3 个位(bit) ,表示某教学日(星期一 星期五) 安排该课程的时间段的值,0 表
3、示当日未安排,1 4 表示所安排的相应的时间段(超过4 的值无效) .在这种设计下, 有效的时间段分配字的值应小于32 768 (十六进制8000) , 而大于等于32 768 的时间段分配字对应于那些当前无效的课程(既使课程分配位已设置好也如此) , 因此很容易实现停课/ 开课处理.3 .排课算法在上述假设下,自动排课算法的目标就是确定 C1 , C2 , ., Cn 所对应的 T1 , T2 , ., Tn .从安排的可能性上看,共有(即有A（20，（N-20）)20 !/ (20 - N) !种排法( N 的含义见(2) 式) . 如果有4 门课,每门课一周上2 次,则N = 8 ,这8
4、 次课可能的安排方法就会有20 !/ (20 - 8) ! = 5 079 110 400 ,即50 多亿种. 如果毫无原则地在其中选择一种方案,将会耗费巨大量的时间. 所以排课的前提是必须有一个确定的排课原则. 我们采用轮转分配法作为排课原则:从星期一第1 时间段开始按 C1 , C2 , ., Cn 中所列顺序安排完各门课程之后(每门课安排1 次) ,再按该顺序继续向后面的时间段进行安排,直到所有课程的开课次数符合 N1 , N2 , ., Nn 中给定的值为止. 在算法描述中将用 C1 , C2 , ., C n 表示 C1 , C2 , ., Cn , 对 N1 , N2 , ., N
5、n和 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 进行以下操作:如果Nc-index 0 ,则做以下操作:把segment 的值写入Tc-index 的第(week - 1) 3 3week 3 3 - 1 位中Nc-index 的值减1
6、如果Nc-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
7、门课程在人工干预下改成星期数为week 、时间段为segment 的位置,则根据上述数据结构需做如下运算:T i = T i &( (7 (week - 1) * 3) ) + (segment (week - 1)*3) ,其中&、 和n 分别为按位与、按位取反和按位左移运算符(下同) .问题是如何判断是否已有其它课程安排在同一个时间段上. 设人工调整的时间段分配字为T1 ,则该问题描述为:判断时间段分配字T 1 与 T2 , T 3 , ., T n 中的某个分配字是否存在相同课程分配位上的相等的非零时间段值, 或者说 T 2 , T 3 , .,T n 中是否存在与T 1 冲突的时间段分
8、配字. 为简化起见,在以下算法描述中假设所有时间段分配字的最高位为0.算法2 冲突检测算法输入T1 和 T2 , ., Tn .输出与T1 冲突的 T2 , ., Tn 中的时间段分配字.对c-index = 2 ,3 , ., n 做以下操作:初始化屏蔽字mask = 7对星期值week = 1 ,2 ,3 ,4 ,5 做以下操作:如果T1 & mask 等于Tc-index & mask ,而且二者不等于0则: T 1 与Tc-index 相冲突,转mask 左移3 位(或乘8)算法结束本算法时间复杂度为O ( n) ( n 为课程门数)5.算法分析 此算法以课程为中心，进行搜索匹配，取最
9、先匹配的值；具有占有空间少，运算速度快的特点。但其未对数据进行择优选取，所以不能对教学资源（教师、教室）合理分配，也不能满足一些特殊要求（比如有些老师喜欢上午上课，有些老师偏向于集中式上课；有些课程安排到上午会更合适些，有些课程不能安排到上午等）。22 基于优先级的排课算法从数学上讲, 排课问题是一个在时间、教师、学生和教室四维空间, 以教学计划和各种特殊要求为约束条件的组合规划问题。其实质就是解决各因素之间的冲突。在设计算法时, 为了降低课程调度的算法复杂性, 我们主要采用了化整为零的思想及优先级算法:1排课的预处理1等价类的划分将具有共同听课对象的任务划分在同一等价类中, 在每个等价类之间
10、只存在地点上的冲突, 而没有时间上的冲突。 然后按照的大小, 从大到小进行处理。 等价类的划分可以先按年级分, 然后再按系别分, 如下 所示:听课对象等价类的划分自控系机械系化工系管理系.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 又可以按院系分为若干个子
11、类, 然后对每个子类分别进行排课处理, 这样做就可以大大降低算法的复杂性2教室分类为了合理使用教室, 我们采用了教室分类的办法, 以便尽可能在课程编排过程中避免上课人数少的课程盲目强占容量大的教室现象。首先将教室按照其类型分为若干个等价类, 如下所示,然后, 根据教室的容量再分别对每个教室等价类进行划分: 如分为0 30 人、30 60 人、6090 人、90 120 人、120 180 人等若干种 教室等价类的划分:教室类型等价类R 教室类型等价类R普通教室R1 听力教室R5投影教室R2 物理实验室R6多媒体教室R3 化学实验教室R7制图教室R4 计算机实验教学R83.时间预处理1) 构造时
12、间模式库时间模式是根据教务人员的经验, 为各种周学时数不同的课程指定的一种时间组合方式.例如, 一门课程的周学时数为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 节这个时间单元。这样, 对
13、于每种周学时数, 可以将所有合理的时间组合形式存入模式库中。以便进行时间处理时可以用时间模式库中的各种模式进行匹配。2) 时间数组为了表示班级、教师、教室的可排课时间, 分别为他们建立一维数组L例如, 某位教师的初始可排课时间数组为(123456123456123456123456 123456)。 其中共有五组数据, 分别表示一周中的五天; 而一组数据共有6 个字符“1、2、3、4、5、6”分别表示一天中的六个时间单元。 当为某位教师分配时间后, 相应的那位字符就置为0L 例如, 某位教师的可排课时间数组为( 020456 103456 003456 120456023456) , 则表示这
14、位教师在周一的12 节和56 节, 周二的34 节, 周三的12 节和34 节, 周四的56 节, 周五的12 节已经安排了课程, 如果要再安排课程的话, 就应该安排在非0 的时间单元L对于班级和教室也可以进行同样的处理, 分别标出可排课时间。2每一子类的排课处理在对每个子类的排课处理中, 我们结合了分治法、贪婪法、回溯法三者的思想L首先, 根据分治法的思想把整个排课过程分成时间分配和教室分配两个阶段。然后, 依据贪婪法的算法思想, 在时间分配时,总是在尚未分配的时间单元中选择上课效果最好的单元。而在时间分配发生死锁时, 会向上回溯搜索到发生冲突的最近一个记录, 然后对它进行重排以解决冲突。
15、具体处理过程如下:1设定优先级对子类中的课程计算优先级L设优先级函数为:D (g ) = J (g )*C1 + T (g ) * C2 + P (g ) * C3 ( 1 )其中, J (g ) 表示课程级别, 选修课的课程级别设置为1, 必修课的课程级别设置为2; T (g ) 表示该课程的周学时数; P (g ) 表示该课程的参与人数; C1、C2、C3 是可以调整的参数。 由式(1) 可以看出课程级别越高、周学时越多、参加人数越多的课程, 其D (g )值越大, 其优先级也越高; 反之, D (g ) 值越小, 其优先级越低。这样, 就可以根据计算的优先级的高低对课程进行排序, 优先级高的优先调度。2查询可用时间单元第
