目前流行的几种排课算法的介绍.doc

2 目前流行的几种排课算法的介绍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 ,并存在以下约束关系:b5E2RGbCAPn 20 , (1N = 6n， i =1， Ni 20. (2自动排课问题是:设计适当的数据结构和算法, 以确定 C1 , C2 , ., Cn 中每个课程的教案应占据的时间段,并且保证任何一个时间段仅由一门课程占据.p1EanqFDPw2 .主要数据结构对于每一门课程,分配2 个字节的“时间段分配字”(无符号整数 : T1 , T2 , ., Tn . 其中任何一个时间段分配字(假设为Ti 都具有如下格式:DXDiTa9E3dTi 的数据类型C 语言格式定义为:unsigned int . Ti 的最高位是该课程目前是否是有效的标志,0 表示有效,1 表示无效(如停课等 。其它各位称为课程分配位, 每个课程分配位占连续的3 个位(bit ,表示某教案日(星期一 星期五 安排该课程的时间段的值,0 表示当日未安排,1 4 表示所安排的相应的时间段(超过4 的值无效 .RTCrpUDGiT在这种设计下, 有效的时间段分配字的值应小于32 768 (十六进制8000 , 而大于等于32 768 的时间段分配字对应于那些当前无效的课程(既使课程分配位已设置好也如此 , 因此很容易实现停课/ 开课处理.5PCzVD7HxA3 .排课算法在上述假设下,自动排课算法的目标就是确定 C1 , C2 , ., Cn 所对应的 T1 , T2 , ., Tn .jLBHrnAILg从安排的可能性上看,共有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 中给定的值为止. 在算法描述中将用 C1 , C2 , ., C n 表示 C1 , C2 , ., Cn , 对 N1 , N2 , ., NnxHAQX74J0X和 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 的值减1LDAYtRyKfE如果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 为课程门数 .Zzz6ZB2Ltk4 .冲突检测算法有时在自动排课完毕后,需要人工调整某些课程的安排时间,如把第i 门课程在人工干预下改成星期数为week 、时间段为segment 的位置,则根据上述数据结构需做如下运算:dvzfvkwMI1T i = T i &( (7 * 3 + (segment *3 ,rqyn14ZNXI其中&、 和n 分别为按位与、按位取反和按位左移运算符(下同 .问题是如何判断是否已有其它课程安排在同一个时间段上. 设人工调整的时间段分配字为T1 ,则该问题描述为:判断时间段分配字T 1 与 T2 , T 3 , ., T n 中的某个分配字是否存在相同课程分配位上的相等的非零时间段值, 或者说 T 2 , T 3 , .,T n 中是否存在与T 1 冲突的时间段分配字. 为简化起见,在以下算法描述中假设所有时间段分配字的最高位为0.EmxvxOtOco算法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.算法分析 此算法以课程为中心，进行搜索匹配，取最先匹配的值；具有占有空间少，运算速度快的特点。但其未对数据进行择优选取，所以不能对教案资源教师、教室）合理分配，也不能满足一些特殊要求 , 98 级(N 2 , 97 级(N 3 , 96 级(N 4 , 而对每一个等价类N 1、N 2、N 3、N 4 又可以按院系分为若干个子类, 然后对每个子类分别进行排课处理, 这样做就可以大大降低算法的复杂性y6v3ALoS892教室分类为了合理使用教室, 我们采用了教室分类的办法, 以便尽可能在课程编排过程中避免上课人数少的课程盲目强占容量大的教室现象。M2ub6vSTnP首先将教室按照其类型分为若干个等价类, 如下所示,然后, 根据教室的容量再分别对每个教室等价类进行划分: 如分为0 30 人、30 60 人、6090 人、90 120 人、120 180 人等若干种0YujCfmUCw 教室等价类的划分:教室类型等价类R 教室类型等价类R普通教室R1 听力教授R5投影教室R2 物理实验室R6多媒体教室R3 化学实验教室R7制图教室R4 计算机实验教案R83.时间预处理1 构造时间模式库时间模式是根据教务人员的经验, 为各种周学时数不同的课程指定的一种时间组合方式.例如, 一门课程的周学时数为4, 那么它的时间组合方式可以有:“11”,“41”。 表示该课程一周上两次, 分别为周一的12 节和周四的12 节L同时, 为了达到较好的上课效果, 也要对这些时间模式进行分级.如下 所示eUts8ZQVRd 时间模式分级举例周学时优先级周一周二周三周四周五4 1 11 414 2 22 43: :其中, 将周一至周五用数字1 5 表示, 上课节次: 12 节、34 节、56 节、78 节、晚12 节、晚34 节分别用数字1 6 表示。 例如数字“42”表示周四的34 节sQsAEJkW5T这个时间单元。这样, 对于每种周学时数, 可以将所有合理的时间组合形式存入模式库中。以便进行时间处理时可以用时间模式库中的各种模式进行匹配。GMsIasNXkA2 时间数组为了表示班级、教师、教室的可排课时间, 分别为他们建立一维数组L例如, 某位教师的初始可排课时间数组为(123456123456123456123456 123456。 其中共有五组数据, 分别表示一周中的五天。 而一组数据共有6 个字符“1、2、3、4、5、6”分别表示一天中的六个时间单元。 当为某位教师分配时间后, 相应的那位字符就置为0L 例如, 某位教师的可排课时间数组为( 020456 103456 003456 120456023456 , 则表示这位教师在周一的12 节和56 节, 周二的34 节, 周三的12 节和34 节, 周四的56 节, 周五的12 节已经安排了课程, 如果要再安排课程的话, 就应该安排在非0 的时间单元L对于班级和教室也可以进行同样的处理, 分别标出可排课时间。TIrRGchYzg2每一子类的排课处理在对每个子类的排课处理中, 我们结合了分治法、贪婪法、回溯法三者的思想L首先, 根据分治法的思想把整个排课过程分成时间分配和教室分配两个阶段。然后, 依据贪婪法的算法思想, 在时间分配时,总是在尚未分配的时间单元中选择上课效果最好的7EqZcWLZNX单元。而在时间分配发生死锁时, 会向上回溯搜索到发生冲突的最近一个记录, 然后对它进行重排以解决冲突。 具体处理过程如下:lzq7IGf02E1设定优先级对子类中的课程计算优先级L设优先级函数为:D (g = J (g *C1 + T (g * C2 + P (g * C3 ( 1 zvpgeqJ1hk其中, J (g 表示课程级别, 选修课的课程级别设置为1, 必修课的课程级别设置为2。 T (g 表示该课程的周学时数。 P (g 表示该课程的参与人数。 C1、C2、NrpoJac3v1C3 是可以调整的参数。 由式(1 可以看出课程级别越高、周学时越多、参加人数越多的课程, 其D (g 值越大, 其优先级也越高。 反之, D (g 值越小, 其优先级越低。这样, 就可以根据计算的优先级的高低对课程进行排序, 优先级高的优先调度。1nowfTG4KI2查询可用时间单元第1 步, 初始化某门课程的最大可安排时间数组, 为( 123456 123456 123456 123456 123456。第2 步, 找出参加该课程学习的所有班级。第3 步, 查询每个班级的时间数组, 得到班级的已排课时间, 并将其与课程的最大时间数组相“与”, 从而得到该课程不能安排的时间单元。第4 步, 依次处理教师时间数组和相关教室时间数组, 这样, 该课程最终的可安排时间数组就是班级、教师、教室可排课时fjnFLDa5Zo间的交集。3查找适当的时间模式找到可排课时间后, 就应根据课程的周学时数在时间模式库中匹配适当的时间模式。完成以上工作后, 就确定了课程的上课时间和地点。如果在处理中发生死锁, 则可根据回溯法的思想向上回溯搜索到发生冲突的最近一个记录, 然后对它进行重排以解决死锁, 如果仍不能解决死锁问题, 则可以将该课程信息输出到冲突列表中。tfnNhnE6e53 人工干预的处理计算机自动排课也需要进行人工干预, 以便可以使得各个高校能够根据自己的具体要求对排课算法中的一些参数进行设置和调整, 并对计算机排出的课表进行调整L本算法所设计的人工干预过程有:HbmVN777sL等价类划分中参数的设置, 教室类型的设置, 时间模式库的设置, 优先级函数中参数的设置。用户可以根据自己的具体要求对这些参数和库进行设置。另外,对于计算机排出的课程表, 用户也可以通过人机交互进行适当调整, 从而得到用户满意的课程表。V7l4jRB8Hs4性能分析 此算法对班级及教室划分等价类，对学校资源进行了合理的利用。但对一些特殊要求还是无法具体体现出来。3 基于时间片优先级排课算法描述与分析 排课问题实质上是时间、教师、班级、教室、课程这五维关系的冲突问题，要合理的解决这个问题首先要了解排课中的一些基本原则以及排课的一些基本要求。83lcPA59W931排课中的基本原则在课程的编排中应遵循一定的规则, 只有按照基本规则来进行课程的编排才能够减少冲突的发生, 这些基本规则主要有以下几条:mZkklkzaaP1 同一班级的学生在同一时间(某些特定的选修课时间除外 不能安排两门课程2 同一教师在同一时间不能安排两门课程3 同一教室在同一时间不能安排两门课程4 同一时间安排的课程总数不能大于所能提供的教室总数5 某一课程参加学习的总人数不应大于所安排教室的座位数6 所提供教室的属性与课程所需教室的属性一致在时间、教师、班级、教室、课程这五维关系中, 时间、教师、班级三者之间存在着紧密关系。相对而言, 教室与它们关系就不那么密切。AVktR43bpw32排课的基本要求课程的安排不是任意的, 为了达到最好的教案效果应遵循一定的要求。这些要求主要有:1 要尽量为所排课程安排上该类课效果最好的时间2 课程在一周上多次时, 要有一定的间隔性3 公共课等涉及面广、学时多的课程应优先处理4 对同一教师, 同一上课对象应尽量选择相对固定的几个教室5 对同一个班级的课程应选择相对固定的教室6 连着的课的教室选择不应相隔太远7）同一天有几门课时尽量把课分散8 优先满足一些特殊要求比如有些教室喜欢上上午的课，可以优先满足）33基于时间片优先级排课算法描述在描述算法之前我们把一些概念先讲清楚。在这里我们把从行政角度分的班叫自然班，把在同一个教室上课的班叫做排课班。在大学里有些公共课是几个排课班通过多媒体来一起上的，我们把这个排课班的总和叫做公共班。班级、教室、教师、课程都维护着自己的一张课表。对课表的每个表元的时间表选择合适的时间片。1算法流程图 2算法的伪代码描述 输入：教师teacher1,teacher2,.teachern） 教室room1,room2,roomn） 班级class1,class2,.classn） 课程2MiJTy0dTT 输出：已经排好课表的教师、教室、班级Procedure schudeling(teacher,room,class,course,schudel_class,public_classgIiSpiue7A/初始化一张空的时间表，对该时间表的每个时间片的优/先级初始化为高级Init Time_table /对排课班进行处理 For every schudel_class do: If(!Check_Have_despose(schudel_class /假如该排课班尚未排课uEh0U1Yfmh Begin: Time_table=Time_table & get_all_class_time_table(schudel_classIAg9qLsgBX Time_table=Time_table & get_room(schudel_class。 Time_table=Time_table & get_teacher(schudel_class。WwghWvVhPE Course=get_course(schudel_class。 /假设只有两节连堂及三节连堂那种课 Int iCount2=0。/那门课两节连堂的次数 Int iCount3=0。/那门课三节连堂的次数 /得到课程每周的课时数Int course_count=get_couse_count(Course。/得到每周的连课情况 Parse_couse_count(course_count,&iCount2,&iCount3。/根据iCount2,iCount3,以及Time_table为该排课班选择N个/(N=iCount2+iCount3适当的时间片,保存在CPoint变量中 CPoint po。LList* cpInt priority7=0。/得到每天的优先级的总和 Loop:I=0 until I=6 do: Loop: J=0 until J=6 do: Begin: PriorityI =PriorityI+ Time_table.time_pieceIjasfpsfpi4k End Begin /得到优先级总和最大的那天，我们认为那一时间最闲/适宜安排课程 int number=get_number(priority7。 BOOL fail While iCount20 do: Begin: fail=Get_Time_Pieces(2,&number,po。 if(!fail then do begin: iCount2-。 cp-append_list(po。 end begin else break。 End Begin While iCount30 do: Begin: fail=Get_Time_Pieces(3,&number,po。 if(!fail then do: begin:ICount3-。 Cp-append_list(po。 End begin Else Break。 End Begin/根据*cp的数据及schudel_class的数据对schudel_class中的自然班，所得到的教室，ooeyYZTjj1/ 老师的课表进行回写if(!fail doWriteBack(schudel_class,cp。Else then RollBack(schudel_class,cp。/把先前选好的教室，老师给”擦除”掉 End Begin End Schudeling算法里面有到的一些函数解释：BOOL check_for_dispose(schudel_class:以排课班为参数，判断该排课班是否已经排好课，排好了返回treu，否则返回falseBkeGuInkxI&操作:该操作是对两个课表的运算，返回一个新课表；得到的课表的时间片为所运算的课表对应时间片的较小值PgdO0sRlMoCTime_table& get_all_class_time(schudel_class:以排课班为参数，得到该排课班所有自然班课表的&，返回得到的新课表3cdXwckm15CTime_table& get_room(schudel_class:以排课班为参数，为该排课分配所有合适的教室，并把所得到