（计算机应用技术专业论文）‘雷区行走’排课算法的研究与应用.pdf

摘要 摘要 二十世纪五十年代，国外就有人着手研究用计算机来编制课表，1 9 7 5 年e v e n 等人证明了课表问题属于n p 完全问题，是典型的组合优化和不确定性调度问题， 时间和空闻作为临界资源的一种不定型分配，这是一类困难问题。但是这类问题 有它固有的数学模型，对于这类问题，人们至今还没有得到其通用的算法，而是 更倾向于去寻找一种有效的近似算法。一个可行的课表满足以下条件： ( 1 ) 同一时间，一个教师只能上一门课程； ( 2 ) 同一时间，一个学生只能上一门课程； ( 3 ) 同一时间，一个教室只能上一门课程； 国内外许多专家和学者从不同的侧重点设计出各种排课算法，其中不凡优 秀。但大多算法有其不足之处，存在局限性。经过反复认真和冷静的思考， 雷 区行走排课算法诞生了。在实际排课应用中，雷区行走排课算法扮演了 一个排雷专家的角色，把矛盾和冲突一一化解，在复杂的排课领域缔造没有 矛盾和冲突的排课世界。雷区行走排课算法主要有以下两个特点： ( 1 )雷区行走排课算法本质就是编排课表，但并不是编排工作的全部， 只是很小的部分。雷区行走排课算法只是有选择的编排课表，把产生矛盾和 冲突的可能消除。雷区行走排课算法下如一位心理学家，把性格不合可能引 发打架的学生分到不同的班级一样。 ( 2 ) 雷区行走排课算法也是一个理想模型，在实际应用中单独使用不能 起作用，雷区行走排课算法要发挥效能，必须和辅助算法捆绑( 辅助算法在 第三章给出) 。 排课是一个学校教务工作的核心环节，其重要性不言而喻。在一周内，一位 老师，要上几个班级的课程，一个班级需要几个老师授课。客观上教室，电脑室 等公共资源是有限的，众多限制和多维冲突问题的存在使得高校排课成为令人头 痛的事，本人在大量阅读相干论著基础上，在总结和创新中提出的雷区行走 算法，能有效在错综复杂的矛盾和冲突中走出来。 关键字：学校排课问题：排课算法：排课模型 a b s t r a c t a b s t r a c t s i n c et h e1 9 5 0 s ，s o m ep e o p l eh a v eg o td o w nt or e s e a r c h i n gm a k i n gs c h o o l t i m e t a b l ew i mt h eh e l po f c o m p u t e r i n1 9 7 5 e v e na n do t h e rp r o v e dt h a tt h ea s p e c to f s c h o o lt i m e t a b l eb e l o n g st on pc o m p l e t ep r o b l e m s ，w h i c hi st h et y p i c a lc o m b i n a t i o n a n di n d e f i n i t e a s s i g n m e n t ，a n dw h i c h i s r e g a r d e d a st h ei n d e f i n i t er e s o u r c e a r r a n g e m e n ti nt i m ea n ds p a c e i ti si n d e e dad i f f i c u l tp r o b l e m h o w e v e r , i th a sa f i x e dm a t h e m a t i c a lm o d e l s of a rp e o p l eh a v e n tf o u n dag e n e r a la l g o r i t h ma b o u tt h e p r o b l e m i nf a c t ，t h e yt e n dt os e a r c hf o ra ne f f e c t i v ea p p r o x i m a t i o na l g o r i t h m a p r a c t i c a b l es c h o o lt i m e t a b l em u s t m e e tt h ef o l l o w i n gc o n d i t i o n s ： ( 1 ) a tt h es a m et i m e , o n et e a c h e ro n l yh a so n es i n # ec o u r s e ( 2 ) a tt h es a n l et i m e , o n es t u d e n to n l ya t t e n d so n es i n g l ec o u r s e ( 3 ) a tt h es 舡r t l et i m e ，o n ec l a s s r o o mi so n l yf i tf o ro n es i n g l ec o u r s e m a n ye x p e r t sa n ds c h o l a r sa th o m ea n da b r o a dd e s i g nv a r i o u sa l g o r i t h m so f c l a s ss c h e m ef r o md i f f e r e n ta s p e c t s ，s o m eo fw h i c ha r eq u i t ee x c e l l e n t b u tm o s to f t h e mr e f l e c tt h i sa n dt h a td e f e c ta n dl i m i t a f t e rc a r e f u lt h i n k i n go n c ea n da g a i n ，ip u t f o r w a r dt h ea l g o r i t h mo fc l a s ss c h e m e ：w a l k i n gi nt h em i n ef i e l d s ，w h i c hp l a y sar o l e o fm i n ec l e a r e ri nt h e a c t u a lc l a s ss c h e m ea n ds o l v e so n ea n da n o t h e rc o n f l i c t t h e r e f o r et h ea l g o r i t h ma v o i d sc o n f l i c t sa n do v e r l a p si nc o m p l i c a t e df i e l d so fc l a s s s c h e m e t h e r ea r et w oc h a r a c t e r i s t i c sa b o u tt h ea l g o r i t h m s 船f o l l o w s ： ( 1 ) t h ea l g o r i t h mo fc l a s ss c h e m e w a l k i n gi nt h em i n ef i e l d s ，i np r a c t i c e ，i s t h el a y o u to fc l a s ss c h e m e ，b u ti ti sn o tt h ew h o l el a y o u t t h ea l g o r i t h mo fc l a s s s c h e m e w a l k i n gi nt h em i n ef i e l d s i sj u s tt h eo p t i o n a la r r a n g e m e n to f c l a s ss c h e m e ， r e m o v i n gt h ee x i s t i n g c o n f l i c t sa n do v e r l a p s t h ea l g o r i t h ml i k eap s y c h o l o g i s t ， a s s i g n st h es t u d e n t sw i t hd i f f e r e n tc h a r a c t e r i s t i c si nd i f f e r e n tc l a s s e s ( 2 ) t h ea l g o r i t h mi sa l s oa ni d e a lm o d e l ，s oi td o e s n tw o r ka t o n e ，i tc o m b i n e s t h ea u x i l i a r ya l g o r i t h mi n s t e a d ( d e t a i l si nc h a p t e rt h r e 曲 i ti st h ec a ) r ea n di m p o r t a n tt a s kt ot h es c h o o le d u c a t i o n a la d m i n i s t r a t i o n d e p a r t m e n tt oa r r a n g et h ew h o l ec l a s s e so fas c h 0 0 1 f o re x a m p l e ：h o wm a n yc l a s s e s w i l lat e a c h e rg i v ei no n ew e e k ? o rh o wm a n yt e a c h e r sd o e so n ec l a s sn e e d ? a sw e a l lk n o wt h a tt h ep u b l i cr e s o u r c e sa r ev e r yl i m i t e d s om u c he x i s t i n gl i m i t a t i o ne n d c o n f l i c t sh a v em a d ed o i n gt h ec l a s ss c h e m ev e r yt r o u b l e s o m ea n dh e a d a c h y h a v i n g r e a dm a n yr e l a t i v et h e o r i e s ，ih a v ef o u n da ne f f e c t i v ew a yt os o l v et h ep r o b l e m t h a t 雷区行走捧 谭算法的研究与应用 i s ：t h ea l g o r i t h mo f c l a s ss c h e m e ：w a l k i n gi nt h em i n ef i e l d s k e yw o r d s ：s c h o o lt i m e t a b l i n gp r o b l e m ；a l g o r i t h mo f c l a s ss c h e m e ； m o d d so f c l a s ss c h e n l e 第一章绪论 第一章绪论 无论是企业还是政府机关，各行各业都会有大量的文案需要处理，复杂的工 作流程需要安排，对高等学校而言，教务工作者需要依据纷乱又离散的信息整合 成一个排课表，手工工作效率低下众人皆知，制造一个优秀的排课系统自然成了 需要。然而何谓优秀? 这就需要提出一个好的排课软件和算法的通用原则， 这个原则既要体现效率，又要体现节约成本：包括教室和公共实验室。 1 1 排课算法设计原则 一、有效原则。这是排课的总原则。在效率高的黄金时间里，如上午一二节 课应当安排基础课程，这个时间段人的思维较为敏捷，精力较为充沛如高等数 学、算法研究、编程等课程应该放在其它时间段之前。上午的最后两节或者下午 课程可以安排一些体育和实验课程等 二、开放设计原则。多年来，国内很多高校为追求更高的教务管理工作效率、 效益，针对自身的教学机制运行特点和管理工作需要，着力开发或引进适合自己 本校的排课软件。有明显的本土性，但由于校际之间开课和专业设置等差异， 这些软件来到新的学校就水土不服，这样不少高校的开课工作目前仍沿用传 统的“手工作业”方式。 三、以人为本的原则。有一些老教师行动不方便或者家庭距离学校较远，排 课软件应该体现人文关怀。再比如说，学生教室距离实验室很远，学生下课后要匆 忙赶路到实验室这种情况应该避免。要安排好校内的集体活动时间，如教工会议、 行政会议、教研组长会议、班主任会议等都应照顾。对特殊困难的教师要主动照 顾，如哺乳的女教师、体弱多病的教师、上有老下有小中午需要回家做饭的教师， 尽可能不排第一节，也不排最后一节课。 四、错位原则。班主任是班级的管理者，排课软件应该考虑这个问题，以便 教育和教学两不误。 五、设备原则。排课要有利于各种教学设备的充分使用，如实验室、实验仪 器、多媒体教室、体育器材、实验场地的合理安排，轮流使用：由于受设备条件限 制，对有特殊要求的课程要优先安排和分配好资源，避免冲突。 六、试用原则。排好课表后，及时请学校领导、科组长、班主任来审核，看是否体 雷区行走排译算法的研究与应用 现“统筹安排，兼顾各方”的原则。如有缺点，再作修改，然后试用一周。教师有 意见，提得对要接受，提得不对或办不到的要解释清楚。 1 2 信息表 计算机排课是一个模拟人工的较为复杂的信息组合、信息调整的过程。需要 从开课信息、教师授课信息、教室资源信息及班级信息中提取基础数据，经过用 户既定的数据流优先级控制、调配、编排，生成理想的排课结果。其中： 1 原始信息表：记录开课情况，它的每一条记录应该有班级、课程名、授 课教师、是否安排、班主任，段次等信息。 2 教师信息表：可安排上课时间片。 3 教室信息表：教室名、时间片、是否占用，类型。 4 班级信息表：班级名、时间片等。 其具体的信息表关系见图： 1 3 定义问题 在高校学习和工作过的人都知道，大学的课程是非饱和的，也就是说大学生 不是象高中学生一样，整天都在上课，他们有自由学习的时间。换一句话说，有 一些时间片里，没有安排授课。但是照样会出现课程排列冲突，比如：一个教师在 同一时间上两门课，有两个教师同时去一个教室上不同的课程，同样一个班级不 可能在同一时间上两门课等，如果没有很好地解决这些冲突，必将产生混乱的教 第一章绪论 学现象。可见，排课算法的正确性、高效性是非常关键的。为此，本人提出一个简 单而有效的雷区行走算法。此问题在第四章作出详细介绍。 1 3 1 基本事实 ( 1 ) 一个学校下面由a l ，a 2 ，a 3 a n 专业班级组成。 ( 2 ) 学校有t l ，t 2 ，t 3 t n 专业授课教师。 ( 3 ) 校内有c l ，c 2 ，c 3 c n 教室和d 1 ，d 2 ，d 3 d n 电随机房。 ( 4 ) 一个学生不能同一时问上两门及两门以上的课程。 ( 5 ) 同一个老师不能同一时间上两门及两门以上的课程。 ( 7 ) 同一个教室在同一时间只能给某一个班级的学生上课。 1 3 2 章节安排 为了更清晰解剖问题，分析问题和找到解决问题的算法，采用整体到局部， 从上而下的原则。首先从总课表入手，分析总课表，找到问题的突破口。其次分 析问题的特征，找到解决问题的算法，证明算法的可行性和正确性。最后实验对 比，分析算法的有用性。 雷区行走排课算法的研究与应用 第二章排课模型 生活在一个复杂的世界里，人们在考虑问题和分析事物的时候总是从理想的 模式和状态出发，进而细化，理解直到消化。排课问题是一个复杂的资源优化组 合的问题，同样得先制作一个理想模型。 2 1 理想排课流程图 d 第二章排课模型 2 2 实际问题的提出 之所以说理想模型，是因为： 第一：没有体现课程安排在什么时间片段，是上午还是下午或者是晚上上 课? 在流程图中没有得到体现。 第二：这种自由排课基于一个假设，那就是有足够的条件满足流程图中的三 重判断。这就出现了第一个需要求证的充分条件：满足什么条件能够自由排课? 这要求排课算法对各种冲突和矛盾先前处理好，也可以说是预先排雷。让 自由排课成为可能。 接下来的第三章探讨和分析第一个问题。第四章探讨和分析第二个问题， 分析和解决这个雷。 在实际的排课程序中，各种类型的雷都会出现，人们需要智慧去理解问 题和解决问题。 雷区行走排谍算法的研究与应用 第三章分治策略的运用 3 1 分治算法的基本思想 分治算法的思想是将一个规模为n 的问题分解为k 个规模较小的子问题，这 些子问题相互独立且与原问题性质相同。任何一个可以用计算机求解的问题所需 的计算时间都与其规模n 有关。问题的规模越小，越容易直接求解，解题所需的 计算时间也越少。将一个难以直接解决的大问题，分割成一些规模较小的相同问 题，以便各个击破，分而治之。求出子问题的解，就可得到原问题的解。 3 2 分治法的适用条件 分治法所能解决的问题一般具有以下几个特征： ( 1 ) 该问题的规模缩小到一定的程度就可以容易地解决； ( 2 ) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结 构性质； ( 3 ) 利用该问题分解出的子问题的解可以合并为该问题的解； ( 4 ) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共 的子问题。 分治法解题的一般步骤： ( 1 ) 分解，将要解决的问题划分成若干规模较小的同类问题； ( 2 ) 求解，当子问题划分得足够小时，用较简单的方法解决； ( 3 ) 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。 本章就要回答前章提出的第一个问题，为了更好的说明和解释雷区行走 排课算法，在这里给出几个名词的解释： 时间段：就是在一周内把上课时间分为四个段，即上午两个段( 一二节课为 一个时间段，三四节为一个时间段) ，下午一个段，晚上一个段。一个时间段包 含几个时间片，如说晚上时间段包含从周一到周日的晚上。时间段是一个集 合。 时间片：就是一个时间段里的具体元素。如周一晚上是集合晚上时间段 的元素，也就是称为时间片。 课程元：就是原始表中的一条记录，它包含课程名，任课教师，班级， 6 第三章分治簧略的运用 也就是排课任务中最小单元。一门课程可以有很多个课程元，如a 班有- f j 课程 高等数学，在一周内上三次高等数学课，这三次高等数学课就是三 个课程元。 下面的课程元分布示意图：( 课程元分布结构示意图) 星期一星期二星期三星期四星期五星期六星期日 1 ，2 节为一段 上午 3 ，4 节为一段 下午下午段 晚上晚上段 从以上示意图可以得出以下三点： a 教务管理者的角度说来，在一天内，课程安排分四个时间段( 上午两段， 下午一段，晚上一段) ，一周七天。 b 满足分治法的适用条件。 c 用分治策略把全院的课程元均匀分配到这四个时间段，也就是说把排课问 题分成四个子问题，当然全院的课程元分配到四个子结构时间段时考虑的因素有 以下几个： 一、一个教师授课数在每一个子结构时间段的数量，这个时候要体现以 人为本的精神，如哺乳的女教师、体弱多病的教师、上有老下有小中午需要回 家做饭的教师，尽可能不排在第一时间段，也不排最后时间段。这种分治策略为电 脑排课人性化提供了可能。 二、班级课程元数量，要尽可能避免某一个班级的课程太集中在某个时闻 段，尽可能均匀。 每一个子结构时间段理解成一个最优子结构。将各个子问题的解合并为原 问题的解。 3 3 数据库结构模型 最优予结构的提出，就排除了纵向排课的干扰。这就可以一心一意安排好一 个时间片，为了叙述方便，就安排晚上这个时间片为例。这实际是全国电大系统 的排课问题，因为电大是成人教育，学生大都是上班族，白天上班，晚上进修。 7 雷区行走排课算法的研究与应用 在实际编程过程中，具体程序借助v i s u a l - b a s i c 和数据库相结合，数据库程序设 计是v b 应用程序设计中一个重要的部分，v b 提供了强大的数据库功能，在v b 中可 以用m i c r o s o f ta c t i v e xd a t eo b j e c t s ( a d o ) 来完成操作数据库格式中的数据。 数据访问功能接口是一个对象模型，它代表了访问数据的各个方面。v b 可以在任 何应用程序中通过编程来控制连接、语句生成器和供使用的返回数据。现给出数 据库的几个表字段结构： 一个时间段总课程表字段 星期一星期二星期三星期四星期五 班班班班班 班 课教教班课教教班课教教鞋课教教功课教教 主主主主主 级 程师室级程 师室级程 师室勃程师室级程师 室 任任任任任 原始表格( 上课信息收集表) l 班级课程教师周次教室是否安排班主任段次 1 教师信息表 l 教师名星期一星期二星期三星期四星期五周六周同 2 教室信息表 教室名星期一星期二星期三星期四星期五星期六周日类型 3 4 辅助算法约束条件 在排课的初期，对课程元自动的分配到各个时问段中，这可以给出一个辅助 算法，这个算法应该可以手工的参与，也可以不需要手工参与，但是分配应该有 一个约束条件，并不是可以随意安排，这也是动态和不定型的分配。 1 在一个时间段里，老师上课的次数不能超过理论值最大值，如一位教师 在一周内晚上时间段不能超过七次。也就是下一章提到的公式中的x z 2 各个时间段的课程元个数应该基本平衡，从而减轻公共资源的压力，如 图书馆。 第三章分治策略的运用 3 人文关怀，如上面说的哺乳的女教师、体弱多病的教师、上有老下有小 中午需要回家做饭的教师，尽可能不排第一节，也不排最后一节课，这也是手工调 节的地方。 现在可以给出一个基本的辅助算法如下： 第一步：计算全校一周内的总课程元数。 第二步：总课程元数分成四份，分别放入各时间段。 第三步：检查这种分配是否满足约束条件。如果不能成立，那么就重新随 机分配。直到满足约束条件。 第四步：人工干预。 注意：这里的人工干预后的分配也要满足约束条件。 辅助算法流程图 雷区行走排课算法的研究与应用 第四章雷区行走算法 4 1雷区行走算法定义 所谓的雷区行走，就是士兵行军在一片雷区时候，为了避免无谓 的伤亡，后面的士兵前进时踩着前面的士兵的脚印。雷区行走算法就是把班 级的一门课程元( 课程名，班级，教师，班主任) 比喻成士兵，安排一个课程元， 为了避开班级和教师( 该教师不属于该课程元，是该班级其他课程元的任课教师) 的时间冲突，这里把冲突比喻成雷，课程元授课时间片尽可能选择在这个教 师的非空闲时间，从而减少了一个冲突的可能。现在就认真分析这些雷吧。 雷：教师和班级的冲突 特征：教师可以安排的时间片，相干班级没有时间片，图例说明如下：( 教 师t 任教班级a 一门课程m 而且是一个时间片) 教师t 的时间安排( 有五段) 星期一星期二星期三星期四星期五星期六星期日 黝黝燃黝 m ? 班级a 的时间安排( 有四段) 星期一星期二星期三星期四星期五星期六星期日 m ? 燃黝黝 从上面的图示说明m 这课程元没有办法安排，这是因为教师t 有空的时问片 对班级a 毫无用处。也就是说教师t 和班级a 时间片的交集为空。 分析： 1 出现这个雷，完全是排课过程中制造出来的，当教师t 的b ，c ，d ，e 课程元占据的时间片，班级a 没有利用好这个“脚印”，从而触雷。 2 上课任务的教师应该优先得到安排，因为该教师最有可能触雷。 3 一周内课程元数多的班级也应该优先得到安排，因为该班级最有可能触 雷。 第四章雷区行走算法 解决办法：排课的过程实质上就是对课程元分配时间片的过程。以教学任务重的 教师优先安排，当安排教j | i l i t 和课程元a 在一个时间片的时候，和教师t 相干的班 级也尽可能在这个时间片排课。如图所示： 教师t 周一安排了课程元b ，相干班级p 也在周一安排f 。 教师t 的时问安排( 有五段) l 星期一星期二星期三星期四星期五星期六星期日 l 燃黝黝黝 m 班级p 的时间安排( 有四段) 星期一星期二星期三星期四星期五星期六星期日 黝 m 黝黝 4 2 重要命题及证明 命题的必要性：从上面的图示中得出结论：并不需要课程元g 和课程元h 也要这么听话，一个课程元f 跟随教师t 就足够了，那么这就提出了一个问 题：满足什么条件，就不需要跟随了? 这需要寻找其中的规律或法则，利用规律 和法则来确定一个临界点，当跟随到达这个点时，程序完全可以进入自由排 课阶段，不再有矛盾和冲突。 经过反复的研究和实践，大胆地提出以下命题 命题：假设教师t 在一周内一共有x 个课程元。 设在一个子结构里有z 个时间片。 设和教师t 相干的班级未安排的课程元数的最大数为y y = m a x ( y ( c 1 ) ，y ( c 2 ) ，y ( e 1 1 ) ) ( c l ，c 2 c n 是班级，y ( c n ) 是未安排的课程元数) 那么：x + y = z + l 证明： 第一步：考虑一种完全饱和的情况，即老师和班级没有空闲时间片。这也是 最坏的情形，如下图： 教师t 的时间安排( 有七段) 雷区行走排课算法的研究与应用 星期一星期二星期三星期四星期五星期六星期日 黝燃黝黝黝黝 m 班级a 的时间安排( 有七段) 根据算法，每当安排教师t 在星期x 一个课程元授课任务，和教师t 相干 的班级a 也在星期x 安排了课程元，安排班级a 的机会直到最后。从图中看出 即使只有一个机会，而且是最后一个机会，但已经足够了。 教师t 在一周内一共有课程元x = 7 和教师t 相干的班级未安排的课程元数的最大数为y = 1 子结构里有时间片z = 7 公式得证：x + y = z + i 第二步：( 反证法) 假设教师t 和未安排的课程元数第二大，课程元数为y l 的相干班级p 发生 冲突。即y 1 z ，或者y i y ，这显然和算法存在的条件( x 7 ：判断每一个班级在晚上时间段，授课课程元 总数是否 7 ；根据教室资源条件，一个晚上最多安排3 个班级上课。这个辅助算 法和程序虽然不是排课的核心，但它的作用举足轻重。 2 根据雷区行走算法的思想，首先选择授课任务最重的教师张三优先 排课，由随机函数产生四个晚上( 因为张三有四个课程元) ，在这里假设星期一 到星期四。当然不一定要连续，从七个晚上随机抽取四个晚上，这种随机也有利 于动态排课，而随机函数在编程语言中大都是自带的。 3 当安排张三星期一上课时，星期一晚上也要安排二班和三班有课，因为 张三也任教两个班级。这是雷区行走算法思想的关键所在，也就是说和张三 有关的班级这个晚上都有安排上课，这样张三为其他班级上课提供了更多的选 择，从而减少了冲突的可能，即排课中的雷。第一轮排课如下图所示。 ( 第一轮排课课程表) 星期一星期二星期三 星期四 班班班班 班 课教教班课教教班课教教班课教教 主主主主 级程师室级程师室级程师 室级程师室 任任任任 张 m 1lt 1 班三 王 m 52t 2 班 五 = 李。 m 93t 3 班 四 6 第四章雷区行走算法 ( 第二轮捧课课程表) 星期一星期二星期三星期四 班班班班 班课教教 班课教教班课教教班课 教教 主主主主 级程师 室 级程师室 级程师室 级程师室 任任任任 张 “ 张 m 11t 1m 3lt l 班三班三 王 王 m 52t 2 。 m 72t 2 班五班五 = ： 李 m 93t 3 班四 ( 第三轮捧课课程表) 星