资源描述：
《教务处排课系统建模》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、教务处排课系统建模摘要：为解决教务处排课系统选课问题，通过对问题的分析，设计解决问题的主要数据结构，再设计出算法程序，从时间、教师、周开课次数、冲突检测及解决等方面处理排课问题。关键词：排课系统，数据结构，算法，冲突检测，建模。每年开学时需要选课，有时排课系统会出现各种各样的问题，一部分是因为排课系统本身的算法问题。设计一个合理算法对于学生选课方便至关重要，以下是一个排课系统的介绍。1.排课系统的基本要求：1.必修课尽可能的排在上午；例如，数学、英语、专业课等安排在上午，而体育、计算机、实验等安排在下午。2.一个教师如果上午连续上四节课，尽
2、可能的将四节课都安排在一个教室；3.一周上多次的课程尽可能间隔至少一天，比如高数，如果一周上六节课，则尽可能安排周1、3、5上午上课；因此同一节的课程一周最多上六节课，且只能在周一、周三、周五。4.同一专业的课程不能有冲突。2.问题的描述：根据排课的优先级，应该先将全校各个专业本学期的专业课安排好，再考虑教师的教学问题，即如果某一个教师某天上午或下午连续教四节课，确保后一节课的教室号与前一节相同。判断同一课程一周上几次，一次则可以在五天中无课程的时间中随机抽取一天安排课程，两次则可以分为周一和周三、周二和周四、周三和周五三周时间来排课，三次
3、则只能是周一、周三、周五一种排课时间。3.基本算法的描述：设要安排的课程为{C1,C2,.,Cn},课程总数为n,而各门课程每周安排次数为{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
4、}中每个课程的教学应占据的时间段,并且保证任何一个时间段仅由一门课程占据.4.主要数据结构对于每一门课程,分配2个字节的“时间段分配字”(无符号整数):{T1,T2,.,Tn}.其中任何一个时间段分配字(假设为Ti)都具有如下格式:Ti的数据类型C为:unsignedint。Ti的最高位是该课程目前是否是有效的标志,0表示有效,1表示无效(如停课等);其它各位称为课程分配位,每个课程分配位占连续的3个位(bit),表示某教学日(星期一～星期五)安排该课程的时间段的值,0表示当日未安排,1～4表示所安排的相应的时间段(超过4的值无效).在这种
5、设计下,有效的时间段分配字的值应小于32768(十六进制8000),而大于等于32768的时间段分配字对应于那些当前无效的课程(既使课程分配位已设置好也如此),因此很容易实现停课/开课处理.5.排课算法在上述假设下,自动排课算法的目标就是确定{C1,C2,.,Cn}所对应的{T1,T2,.,Tn}.从安排的可能性上看,共有20!/(20-N)!种排法。如果有4门课,每门课一周上2次,则N=8,这8次课可能的安排方法就会有20!/(20-8)!=5079110400,即50多亿种.如果毫无原则地在其中选择一种方案,将会耗费巨大量的时间.所以排
6、课的前提是必须有一个确定的排课原则。采用轮转分配法作为排课原则:从星期一第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}.① 初始化:星期值we
7、ek=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)33～week33-1位中 N[c-index]的值减1 如果N[c-index]>0,则置flag=1 如果week=5并且segment=4则:置flag=1并转③ 否则:如果segment=4 则:置segment=1且w
8、eek增1 否则:segment增1 检测是否已全部安排完毕: 如果flag=1 则:转② 否则:转③③ 检测是否成功: 如果flag=1 则:开课次数过多 否则:课程安排成
