教务处排课系统建模-

1、教务处排课系统建模摘要:为解决教务处排课系统选课问题,通过对问题的分析,设计解决问题的主要数据结构,再设计出算法程序,从时间、教师、周开课次数、冲突检测及解决等方面处理排课问题。关键词:排课系统,数据结构,算法,冲突检测,建模。每年开学时需要选课,有时排课系统会出现各种各样的问题,一部分是因为排课系统本身的算法问题。设计一个合理算法对于学生选课方便至关重要,以下是一个排课系统的介绍。1.排课系统的基本要求:1.必修课尽可能的排在上午;例如,数学、英语、专业课等安排在上午,而体育、计算机、实验等安排在下午。2.一个教师如果上午连续上四节课,尽可能的将四节课都安排在一个教室;3.一周上多次的课程尽

2、可能间隔至少一天,比如高数,如果一周上六节课,则尽可能安排周1、3、5上午上课;因此同一节的课程一周最多上六节课,且只能在周一、周三、周五。4.同一专业的课程不能有冲突。2. 问题的描述:根据排课的优先级,应该先将全校各个专业本学期的专业课安排好,再考虑教师的教学问题,即如果某一个教师某天上午或下午连续教四节课,确保后一节课的教室号与前一节相同。判断同一课程一周上几次,一次则可以在五天中无课程的时间中随机抽取一天安排课程,两次则可以分为周一和周三、周二和周四、周三和周五三周时间来排课,三次则只能是周一、周三、周五一种排课时间。3.基本算法的描述:设要安排的课程为 C1 , C2 , ., Cn

3、 ,课程总数为n , 而各门课程每周安排次数为 N1 , N2 , ., Nn ;每周教学日共5 天,即星期一至星期五;每个教学日最多安排4 次课程教学,即1 2 节、3 4 节、5 6 节和7 8 节(以下分别称第1 、2 、3 、4 时间段 . 在这种假设下,显然每周的教学总时间段数为5 ×4 = 20 ,并存在以下约束关系:n 20 (1N = 6n,i =1,Ni 20 (2自动排课问题是:设计适当的数据结构和算法, 以确定 C1 , C2 , , Cn 中每个课程的教学应占据的时间段,并且保证任何一个时间段仅由一门课程占据.4.主要数据结构对于每一门课程,分配2 个字节的“

4、时间段分配字”(无符号整数 : T1 , T2 , ., Tn . 其中任何一个时间段分配字(假设为Ti 都具有如下格式: Ti 的数据类型C为:unsigned int 。Ti 的最高位是该课程目前是否是有效的标志,0 表示有效,1 表示无效(如停课等 ;其它各位称为课程分配位, 每个课程分配位占连续的3 个位(bit ,表示某教学日(星期一星期五 安排该课程的时间段的值,0 表示当日未安排,1 4 表示所安排的相应的时间段(超过4 的值无效 .在这种设计下, 有效的时间段分配字的值应小于32 768 (十六进制8000 , 而大于等于32 768 的时间段分配字对应于那些当前无效的课程(既

5、使课程分配位已设置好也如此 , 因此很容易实现停课/ 开课处理. 5.排课算法在上述假设下,自动排课算法的目标就是确定 C1 , C2 , ., Cn 所对应的 T1 , T2 , ., Tn .从安排的可能性上看,共有20 !/ (20 - N !种排法。如果有4 门课,每门课一周上2 次,则N = 8 ,这8 次课可能的安排方法就会有20 !/ (20 - 8 ! = 5 079 110 400 ,即50 多亿种. 如果毫无原则地在其中选择一种方案,将会耗费巨大量的时间. 所以排课的前提是必须有一个确定的排课原则。采用轮转分配法作为排课原则:从星期一第1 时间段开始按 C1 , C2 ,

6、., Cn 中所列顺序安排完各门课程之后(每门课安排 1 次 ,再按该顺序继续向后面的时间段进行安排,直到所有课程的开课次数符合 N1 , N2 , ., Nn 中给定的值为止. 在算法描述中将用 C1 , C2 , ., 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 中各

7、时间段分配字清零新一轮扫描课程:置继续处理标志flag = 0对课程索引值c-index = 1 ,2 , ., n 进行以下操作:如果Nc-index > 0 ,则做以下操作:把segment 的值写入Tc-index 的第(week - 1 3 3week 3 3 - 1 位中Nc-index 的值减1如果Nc-index > 0 ,则置flag = 1如果week = 5 并且segment = 4则:置flag = 1 并转否则:如果segment = 4则:置segment = 1 且week 增1否则:segment 增1检测是否已全部安排完毕:如果flag = 1则:

8、转否则:转检测是否成功:如果flag = 1则:开课次数过多否则:课程安排成功算法结束6.冲突检测算法有时在自动排课完毕后,需要人工调整某些课程的安排时间,如把第i 门课程在人工干预下改成星期数为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 冲突的时间段分配字. 为简化起见,在以下算法描述中假设所有时间段分配字的最高位为0.算法2 冲突检测算法输入T1 和 T2 , ., Tn .输出与T1 冲突的 T2 , ., Tn 中的时间段分配字.对c-index = 2 ,3 , ., n 做以下操作:初始化屏蔽字mask = 7对星期值week = 1 ,2 ,3 ,4 ,5 做以下操作:如果T1 &