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

2目前流行的几种排课算法的介绍2.1.自动排课算法1 问题的描述我们讨论的自动排课问题的简化描述如下:1,C2,.,Cn,课程总数为n,而各门课程每周安排次数（每次为连续的2学时）为N1,N2,.,Nn教学日最多安排4次课程教学，即12节、34节、56节和78节（以下分别称第1、2、种假设下，显然每周的教学总时间段数为5X4=20，并存在以下约束关系:n<20,（1）?N=6n,i=1,Ni<20.（2）适当的数据结构和算法，以确定C1,C2,.,Cn中每个课程的教学应占据的时间段，并且保证任何一个时据.2 .主要数据结构配2个字节的时间段分配字”无符号整数）：T1,T2,.,Tn.其中任何一个时间段分配字（假设为Ti格式定义为:unsignedint.Ti的最高位是该课程目前是否是有效的标志,0表示有效,1表示无效（如停课等）占连续的3个位（bit）,表示某教学日（星期一星期五）安排该课程的时间段的值,0表示当日未安排，1时间段（超过4的值无效）.时间段分配字的值应小于32768（十六进制8000）,而大于等于32768的时间段分配字对应于那些当前无配位已设置好也如此），因此很容易实现停课/幵课处理.3 .排课算法在上述假设下，自动排课算法的目标就是确定C1,C2,.,Cn所对应的T1,T2,.,Tn.共有即有A（20,（N-20）20!/（20-N）!种排法（N的含义见（2）式）.如果有4门课,每门课一周上就会龛0!/(20-8)!=5079110400，即50多亿种.如果毫无原则地在其中选择一种方案，将会耗费巨确定的排课原则我们采用轮转分配法作为排课原则：从星期一第1时间段幵始按C1,C2,.,Cn中所列，再按该顺序继续向后面的时间段进行安排，直到所有课程的幵课次数符合N1,N2,.,Nn中给定的值用C1,C2,.,Cn表示C1,C2,.,Cn,对N1,N2,.,Nn和T1,T2,.,Tn也采用同样的表示法.算法1排课算法输入C1,C2,.,Cn、N1,N2,.,Nn.输出T1,T2,.,Tn. 初始化:星期值week=1时间段值segment=1 T1,T2,.,Tn中各时间段分配字清零新一轮扫描课程:置继续处理标志flag=0对课程索引值c-index=1,2,.,n进行以下操作:如果Nc-index>0，则做以下操作:把segment的值写入Tc-index的第(week-1)33week33-1位中Nc-index的值减如果Nc-index>0,则置flag=1女口果week=5并且segment=4则:置flag=1并转否贝9:女口果segment=4则:置segment=1且week增1否则:segment增1检测是否已全部安排完毕: 如果flag=1则:转否则:转检测是否成功:如果flag=1则:幵课次数过多否则:课程安排成功4 算法结束时间复杂度为0(N)(N为每周总幵课次数，见(2)式)，而存储时间段分配字所用空间为2n个字节(r.冲突检测算法雋要人工调整某些课程的安排时间，如把第i门课程在人工干预下改成星期数为week、时间段为segmen据结构需做如下运算:Ti=Ti&(7<<(week-1)*3)+(segment<<(week-1)*3),其中&、和n分别为按位与、按位取反和按位左移运算符(下同).问题是如何判断是否已有其它课程安排在同一个时间段上.设人工调整的时间段分配描述为判断时间段分配字T1与T2,T3,.,Tn中的某个分配字是否存在相同课程分配,T3,.,Tn中是否存在与T1冲突的时间段分配字.为简化起见，在以下算法描述中假设所有时为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则:T1与Tc-index相冲突，转mask左移3位（或乘8）算法结束本算法时间复杂度为0（n）（n为课程门数）5算法分析，进行搜索匹配，取最先匹配的值；具有占有空间少，运算速度快的特点。但其未对数据进行择优选取，所也不能满足一些特殊要求（比如有些老师喜欢上午上课，有些老师偏向于集中式上课；有些课程安排到上程不能安排到上午等）。2基于优先级的排课算法是一个在时间、教师、学生和教室四维空间，以教学计划和各种特殊要求为约束条件的组合规划问题。其实的冲突。在设计算法时，为了降低课程调度的算法复杂性，我们主要采用了化整为零的思想及优先级算法:1. 排课的预处理1. 等价类的划分任务划分在同一等价类中，在每个等价类之间只存在地点上的冲突，而没有时间上的冲突。然后按照的大小等价类的划分可以先按年级分，然后再按系别分，如下所示:听课对象等价类的划分自控系机械系化工系管理系.99级N1子类1子类2子类3子类4.98级N2子类5子类6子类7子类8.97级N3子类9子类10子类11子类12.96级N4子类13子类14子类15子类16.个类99级(N1),98级(N2),97级(N3),96级(N4),而对每一个等价类N1、N2、N3、N4个子类，然后对每个子类分别进行排课处理，这样做就可以大大降低算法的复杂性2. 教室分类用教室我们采用了教室分类的办法，以便尽可能在课程编排过程中避免上课人数少的课程盲目强占容量大的分为若干个等价类，如下所示，然后，根据教室的容量再分别对每个教室等价类进行划分:如分为030丿0人、90120人、120180人等若干种教室等价类的划分:教室类型等价类R教室类型等价类R普通教室R1听力教室R5投影教室R2物理实验室R6多媒体教室R3化学实验教室R7制图教室R4计算机实验教学R8#7楼得分：0回复于：2008-07-1416:08:58时间预处理1）构造时间模式库时间模式是根据教务人员的经验，为各种周学时数不同的课程指定的一种时间组合方式.例如，一门课程它的时间组合方式可以有：“11”,“4表示该课程一周上两次，分别为周一的12节和周四的12节L同课效果，也要对这些时间模式进行分级.如下所示时间模式分级举例周学时优先级周一周二周三周四周五其中，将周一至周五用数字15表示，上课节次:12节、34节、56节、78节、晚12节、晚34节示。例如数字“42表示周四的34节这个时间单元。这样，对于每种周学时数，可以将所有合理的时间组合形式存入模式库中。以便进行时式库中的各种模式进行匹配。2）时间数组为了表示班级、教师、教室的可排课时间，分别为他们建立一维数组L例如，某位教师的初始可排课时。其中共有五组数据,分别表示一周中的五天；而一组数据共有6个字分别表示一天中的六个时间单元。当为某位教师分配时间后，相应的那位字符就置为0L例如，某位教则表示这位教师在周一的12节和56节，周二的34节，周四的56节，周五的12节已经安排了课程，如果要再安排课程的话，就应该安排在非0的时间室也可以进行同样的处理，分别标出可排课时间。每一子类的排课处理在对每个子类的排课处理中，我们结合了分治法、贪婪法、回溯法三者的思想L首先，根据分治法的思时间分配和教室分配两个阶段。然后，依据贪婪法的算法思想，在时间分配时，总是在尚未分配的时间单的单元。而在时间分配发生死锁时，会向上回溯搜索到发生冲突的最近一个记录，然后对它进行重排以解程如下:1.设定优先级对子类中的课程计算优先级L设优先级函数为:2. D(g)=J(g)*C1+T(g)*C2+P(g)*C3(1)其中，J(g)表示课程级别，选修课的课程级别设置为1,必修课的课程级别设置为2;T(g)表示该课表示该课程的参与人数；C1、C2、C3是可以调整的参数。由式(1)可以看出课程级别越高、周学时越多、参加人数越多的课程，其D(越高；反之，D(g)值越小，其优先级越低。这样，就可以根据计算的优先级的高低对课程进行排序，查询可用时间单元课程学习的所有班级。第3步，查询每个班级的时间数组，得到班级的已排课时间，并将其与课程的最而得到该课程不能安排的时间单元。第4步，依次处理教师时间数组和相关教室时间数组，这样，该课组就是班级、教师、教室可排课时间的交集。查找适当的时间模式找到可排课时间后，就应根据课程的周学时数在时间模式库中匹配适当的时间模式。完成以上工作后，间和地点。如果在处理中发生死锁，则可根据回溯法的思想向上回溯搜索到发生冲突的最近一个记录，决死锁，如果仍不能解决死锁问题，则可以将该课程信息输出到冲突列表中。2. 人工干预的处理计算机自动排课也需要进行人工干预，以便可以使得各个高校能够根据自己的具体要求对排课算法中的调整，并对计算机排出的课表进行调整L本算法所设计的人工干预过程有:等价类划分中参数的设置，教室类型的设置，时间模式库的设置，优先级函数中参数的设置。用户可以这些参数和库进行设置。另外，对于计算机排出的课程表，用户也可以通过人机交互进行适当调整，从而表。性能分析此算法对班级及教室划分等价类，对学校资源进行了合理的利用。但对一些特殊要求还是无法基于时间片优先级排课算法描述与分析排课问题实质上是时间、教师、班级、教室、课程这五维关系的冲突问题，要合理的解决这个问题首2. 基本原则以及排课的一些基本要求1排课中的基本原则在课程的编排中应遵循一定的规则，只有按照基本规则来进行课程的编排才能够减少冲突的发生，这些几条:1）同一班级的学生在同一时间（某些特定的选修课时间除外）不能安排两2）同一教师在同一时间不能安排两门课程3）同一教室在同一时间不能安排两门课程4）同一时间安排的课程总数不能大于所能提供的教室总数5）某一课程参加学习的总人数不应大于所安排教室的座位数6）所提供教室的属性与课程所需教室的属性一致在时间、教师、班级、教室、课程这五维关系中，时间、教师、班级三者之间存在着紧密关系。相对而不那么密切。3.2排课的基本要求课程的安排不是任意的，为了达到最好的教学效果应遵循一定的要求。这些要求主要1）要尽量为所排课程安排上该类课效果最好的时间2）课程在一周上多次时，要有一定的间隔性3）公共课等涉及面广、学时多的课程应优先处理4）对同一教师，同一上课对象应尽量选择相对固定的几个教室5）对同一个班级的课程应选择相对固定的教室6）连着的课的教室选择不应相隔太远7）同一天有几门课时尽量把课分散8）优先满足一些特殊要求（比如有些教室喜欢上上午的课，可以优先满足）3.3基于时间片优先级排课算法描述在描述算法之前我们把一些概念先讲清楚。在这里我们把从行政角度分的班叫自然班，把在同一个教室在大学里有些公共课是几个排课班通过多媒体来一起上的，我们把这个排课班的总和叫做公共班。班级都维护着自己的一张课表。对课表的每个表元（如星期一的第一节课）在这里称做时间基于时间片优先级排课算法以排课班为单位，围绕着各对像（自然班、教室、教室）的时间表选择<!-if!supportLists->1.<!-endif->算法流程图<!-if!vml-><!-endif-><!-if!supportLists->2.<!-endif->算法的伪代码描述输入：教师(teacher1,tea(her2,.teache)教室(room1,room2,roomn班级(class1,class2,.c)ssn课程(course1,course2,cou)en各教师、教室、班级、课程时间片的优先级排课班（schudel_class1,schudel_class2schudel_classn）输出：已经排好课表的教师、教室、班级Procedureschudeling（teacher,room,class,course,schudel_class,public_class）/初始化一张空的时间表，对该时间表的每个时间片的优先级初始化为高级InitTime_table对排课班进行处理lf(!Check_Have_despose(schudel_class)/假如该排课班尚未排课Begin:Timetable二Timetable&getallclasstimetable(schudelclass)Time_table=Time_table&get_room(schudel_class);Time_table=Time_table&get_teacher(schudel_class);Course二get_course(schudel_class);假设只有两节连堂及三节连堂那种课IntiCount2=0;那门课两节连堂的次数IntiCount3=0;那门课三节连堂的次数得到课程每周的课时数Intcourse_count=get_couse_count(Course);得到每周的连课情况Parse_couse_count(course_count,&iCount2,&iCount3);/根据iCount2,iCount3,以及Time_table为该排课班选择N个(N=iCount2+iCount3)适当的时间片保存在CPoint变量中CPointpo;LListvCPoint>*cpIntpriority7=0;得到每天的优先级的总和Loop:I=0untilI=6do:Loop:J=0untilJ=6do:Begin:PriorityI=PriorityI+Time_table.time_pieceIjEndBegin/得到优先级总和最大的那天，我们认为那一时间最闲适宜安排课程intnumber二get_number(priority7);BOOLfailWhileiCount2>0do:Begin:fail二Get_Time_Pieces(2，&number,po);if(!fail)thendobegin:iCount2-;cp->append_list(po);endbeginelsebreak;EndBeginWhileiCount3>0do:Begin:fail二Get_Time_Pieces(3，&number,po);if(!fail)thendo:begin:ICount3-;Cp->append_list(po);EndbeginElseBreak;EndBegin根据*cp的数据及schudel_class的数据对schudel_class中的自然班，所得到的教室/老师的课表进行回写if(!fail)doWriteBack(schudel_class,cp);ElsethenRollBack(schudel_class,cp);把先前选好的教室，老师给”擦除”掉EndBeginEndSchudeling算法里面有到的一些函数解释：BOOLcheck_for_dispose(schudel_class)以排课班为参数，判断该排课班是否已经排好课，排好了返回，&?操作:该操作是对两个课表的运算，返回一个新课表；得到的课表的时间片为所运算的课表对应CTime_table&get_all_class_time(schudel_class)以排课班为参数，得到该排课班所有自然班课表的&CTime_table&get_room(schudel_class)以排课班为参数，为该排课分配所有合适的教室，并把所得到的新课表CTime_table&get_teacher(schudel_class)以排课班为参数，为该排课班选择一合适的教师，并返Ccourseget_course(schudel_class)以排课班为参数，得到该排课班的课程，并返回Intget_course_count(Ccourse)以课程为参数，得到该课程每周所需上的课时数，并返Parse_course_count(int&,int&,int&):分析get_course_count所返回的数值，把该数值以2节连堂和3节连堂2节连堂和3节连堂两种情况)IntGetNumber(int*):传进一整型数组，得到该整型数组中的最大值的下标，并返回WriteBack(schudel_class,Llist<CPoint>*):根据Llist<CPoint>*中的时间片值，更新public_class中的教师信息RollBack(schudel_class,Llist<CPoint>*):擦除前面步骤在排课班、教师、班级、教室中写下计算机排课是个复杂的过程，在数据量大，约束条件多的条件下，通过人工干涉达到合理排课是非常重在排课前的一些数据输入工作，人工进行些预排课，排完课后对课表进行适当的调课3.4算法分析此算法属于贪心算法。每次对教师、教室资源的选取都是取当前最优的数据。此算法对按照教师、教室优值，所以对各对象的一些特殊要求会很明显的体现出来，在教师、教室资源不紧缺的情况下，此算法程。相对于上一章介绍的两个算法，在处理各种特殊要求的能力上有明显的优势。参考文献：1 “AnAverageCaseApproximationBoundforCourseSchedulingbyGreedyBipartiteMatching”(2 akashOjha2,JenniferRizzo1,andAbigailWalker1XavierUniversity,MathematicsandComputer“Acolumngenerationschemeforfacultytime-tabling“PaoloSera.ni,UniversityofTimetablingusingaSteadyStateGeneticAlgorithmEnderOzcan,AlpayAlkYeditepeUniversityDepartmentofComputerEngineering,基于优先级自动排课算法PCSA的设计与实现方案陈谊，杨怡，张国龙，王尚忠北京基于课元相关运算的高校排课算法董艳云钱晓群张宇舒西南交通大VisualC+.NET宝典TomArcher,AndrewWhitechapel编著，电子工业出版VisualC+6.0网络及Interner幵发指南李博轩著清华大学出版社2(VisualC+6.0项目案例导航扬小平著科学出版社学用VisualC+6.0美DavisChapman著骆长乐译清华大学出版社西蒙与舒斯特6数据库系统概念美AbrahamSilberschatzHenryF.Korth著机械工业出