图论在排课问题中的研究.doc

前言这是我本科阶段做的毕业设计,之后不断有网友来邮件或留言询问算法的问题,所以在这里贴出与大家一起学习,有问题可以搬砖头(呵呵)1绪论11课题背景与研究意义12课题的应用领域13课题的现状14解决NP问题的几种算法及其比较2目前流行的几种排课算法的介绍21.自动排课算法22基于优先级的排课算法3基于时间片优先级排课算法描述与分析31排课中的基本原则32排课的基本要求33基于时间片优先级排课算法描述34算法分析1绪论1.1课题背景与研究意义排课问题早在70年代就证明是一个NP完全问题，即算法的计算时间是呈指数增长的，这一论断确立了排课问题的理论深度。对于NP问题完全问题目前在数学上是没有一个通用 的算法能够很好地解决。然而很多NP完全问题目具有很重要的实际意义，例如。大家熟悉地路由算法就是很典型的一个NP完全问题，路由要在从多的节点中找出最短 路径完成信息的传递。既然都是NP完全问题，那么很多路由算法就可以运用到解决排课问题上，如Dijkstra算法、节点子树剪枝构造网络最短路径法等 等。目前大家对NP完全问题研究的主要思想是如何降低其计算复杂度。即利用一个近似算法来代替，力争使得解决问题的时间从指数增长化简 到多项式增长。结合到课表问题就是建立一个合适的现实简约模型，利用该简约模型能够大大降低算法的复杂度，便于程序实现，这是解决排课问题一个很多的思 路。在高等院校中，培养学生的主要途径是教学。在教学活动中，有一系列管理工作，其中，教学计划的实施是一个重要的教学环节。每学期管理人员都要整理教学计 划，根据教学计划下达教学任务书，然后根据教学任务书编排课程表。在这些教学调度工作中，既有大量繁琐的数据整理工作，更有严谨思维的脑力劳动，还要填写 大量的表格。因此工作非常繁重。加之，随着教学改革的进行及“211”工程的实施，新的教育体制对课表的编排提出了更高的要求。手工排课时，信息的上通下达是极其麻烦的，而采用计算机排 课，教学中的信息可以一目了然，对于优化学生的学习进程，评估每位教师对教学的贡献，领导合理决策等都具有重要的意义，必将会大大推进教学的良性循环。1.2课题的应用领域本课题的研究对开发高校排课系统有指导作用。排课问题的核心为多维资源的冲突与抢占，对其研究对类似的问题（特别是与时间表有关的问题：如考试排考场问题、电影院排座问题、航空航线问题）也是个参 考。1.3课题的现状年代末，国外就有人开始研究课表编排问题。1962年，Gotlieb曾提出了一个课表问题的数学模型，并利用匈牙利算法解决了三维线性运输问题。次后， 人们对课表问题的算法、解的存在性等问题做了很多深入探讨。但是大多数文献所用的数学模型都是Gotlieb的数学模型的简化或补充，而至今还没有一个 可行的算法来解决课表问题。近40年来，人们对课表问题的计算机解法做了许多尝试。其中，课表编排的整数规划模型将问题归结为求一组0-1变量的解，但是其计算量非常大。解决0-1线性优化问题的分支一定界技术却只适用也 规模较小的课表编排，Mihoc和Balas（1965）将课表公式化为一个优化问题，Krawczk则提出一种线性编程的方法。Junginger将课表问题简化为三维运输问题，而Tripathy则把课表问题视作整数线性编程问题并提出 了大学课表的数学模型。此外，有些文献试图从图论的角度来求解排课表的问题，但是图的染色问题也是NP完全问题，只有在极为简单的情况下才可以将课表编排转化为二部图匹配问题，这样的数 学模型与实际相差太远，所以对于大多数学校的课表编排问题来说没有实用价值。进入九十年代以后，国外对课表问题的研究仍然十分活跃。比较有代表的有印度的Vastapur大学管理学院的ArabindaTripathy、加拿大Montreal大学的JeanAubin和JacquesFerland等。目前，解决课表方法的问题有：模拟手 工排课法，图论方法，拉格朗日法，二次分配型法等多种方法。由于课表约束复杂，用数学方法进行描述时往往导致问题规模剧烈增大，这已经成为应用数学编程解 决课表问题的巨大障碍。国外的研究表明，解决大规模课表编排问题单纯靠数学方法是行不通的，而利用运筹学中分层规划的思想将问题分解，将是一个有希望得到 成功的办法。在国内，对课表问题的研究开始于80年代初期、具有代表性的有：南京工学院的UTSS（AUniversityTimetableSchedulingSystem）系统，清华大学的TISER（TimetableSchedulER）系统，大连理工大学的智能教学组织管理 与课程调度等，这些系统大多数都是模拟手工排课过程，以“班”为单位，运用启发式函数来进行编排的。但是 这些系统课表编排系统往往比较依赖于各个学校的教学体制，不宜进行大量推广。从实际使用的情况来看，国内外研制开发的这些软件系统在实用性上仍不尽如人意。一方面原因是作为一个很复杂的系统，排课要想面面俱到是一件很困难的事；另 一方面每个学校由于其各自的特殊性，自动排课软件很难普遍实用，特别是在调度的过程中一个很小的变动，要引起全部课程的大调整，这意味着全校课程大变动， 在实际的应用中这是很难实现的事。1.4解决NP问题的几种算法及其比较解决NP完全问题只能依靠近似算法，所以下面介绍几种常用算法的设计思想，包括动态规划、贪心算法、回溯法等。（一）动态规划算法动态规划法是将求解的问题一层一层地分解成一级一级、规模逐步缩小的子问题，直到可以直接求出其解的子问题为止。分解成的所有子问题按层次关系构成一颗子 问题树。树根是原问题。原问题的解依赖于子问题树中所有子问题的解。动态规划算法通常用于求一个问题在某种意义下的最优解。设计一个动态规划算法，通常可 按以下几个步骤进行：1.分析最优解的性质，并刻划其结构特征。2.递归的定义最优解。3.以自底向上的方式计算出最优解。4.根据计算最优解时得到的信息，构造一个最优解。步骤13是动态规划算法的基本步骤。在只需要求出最优解的情形，步骤4可以省去。若需要求出问题的一个最优解，则 必须执行步骤4。此时，在步骤3中计算最优解时，通常需记录更多的信息，以便在步骤4中，根据所记录的信息，快速地构造出一个 最优解。（二）贪心算法当一个问题具有最优子结构性质时，我们会想到用动态规划法去解它，但有时会有更简单、更有效的算法，即贪心算法。顾名思义，贪心算法总是做出在当前看来最 好的选择。也就是说贪心算法并不是整体最优上加以考虑，他所作出的选择只是在某种意义上的局部最优的选择。虽然贪心算法不是对所有问题都能得到整体最优 解，但对范围相当广的许多问题它能产生整体最优解，如图的算法中单源最短路径问题，最小支撑树问题等。在一些情况下，即使贪心算法不能得到整体最优解，但 其最终结果却是最优解的很好的近似解。在贪心算法中较为有名的算法是Dijkstra算法。它作为路由算法用来寻求两个节点间的最短路径。Dijkstra算法的思想是：假若G有n个顶点，于是我们总共需要求出n-1条最短路径，求解的方法是：初试，写出V0(始顶点)到各顶点(终顶点)的路径长度，或有路径，则令路径的长度为 边上的权值；或无路经，则令为。再按长度的递增顺序生成每条最短路径。事实上生成最短路径的过程就是不断地在始顶点V何终顶点W间加入中间点的过程，因为在每生成了一条 最短路径后，就有一个该路径的终顶点U，那么那些还未生成最短路径的路径就会由于经过U而比原来的路径短，于是就让它经过U。（三）回溯法回溯法有“通用的解题法”之称。用它可以求出问题的所有解或任一解。概括地说，回溯法是一个既带有系统性又带有跳跃性的搜索法。它在包含问题 所有解的一颗状态空间树上，按照深度优先的策略，从根出发进行搜索。搜索每到达状态空间树的一个节点，总是先判断以该节点为根的子树是否肯定不包含问题的 解。如果肯定不包含，则跳过对该子树的系统搜索，一层一层地向它的祖先节点继续搜索，直到遇到一个还有未被搜索过的儿子的节点，才转向该节点的一个未曾搜 索过的儿子节点继续搜索；否则，进入子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根的所有儿子都已被搜索过才结 束；而在用来求问题的任一解时，只要搜索到问题的一个解就可结束。2目前流行的几种排课算法的介绍21.自动排课算法2.1.1.问题的描述我们讨论的自动排课问题的简化描述如下:设要安排的课程为C1,C2,.,Cn,课程总数为n,而各门课程每周安排次数(每次为连续的2学时)为N1,N2,.,Nn;每周教学日共5天,即星期一星期五;每个教学日最多安排4次课程教学,即12节、34节、56节和78节(以下分别称第1、2、3、4时间段).在这种假设下,显然每周的教学总时间段数为54=20,并存在以下约束关系:n20,(1)N=6n，i=1，Ni20.(2)自动排课问题是:设计适当的数据结构和算法,以确定C1,C2,.,Cn中每个课程的教学应占据的时间段,并且保证任何一个时间段仅由一门课程占据.2.1.2.主要数据结构对于每一门课程,分配2个字节的“时间段分配字”(无符号整数):T1,T2,.,Tn.其中任何一个时间段分配字(假设为Ti)都具有如下格式:Ti的数据类型C语言格式定义为:unsignedint.Ti的最高位是该课程目前是否是有效的标志,0表示有效,1表示无效(如停课等);其它各位称为课程分配位,每个课程分配位占连续的3个位(bit),表示某教学日(星期一星期五)安排该课程的时间段的值,0表示当日未安排,14表示所安排的相应的时间段(超过4的值无效).在这种设计下,有效的时间段分配字的值应小于32768(十六进制8000),而大于等于32768的时间段分配字对应于那些当前无效的课程(既使课程分配位已设置好也如此),因此很容易实现停课/开课处理.2.1.3.排课算法在上述假设下,自动排课算法的目标就是确定C1,C2,.,Cn所对应的T1,T2,.,Tn.从安排的可能性上看,共有20!/(20-N)!种排法(N的含义见(2)式).如果有4门课,每门课一周上2次,则N=8,这8次课可能的安排方法就会有20!/(20-8)!=5079110400,即50多亿种.如果毫无原则地在其中选择一种方案,将会耗费巨大量的时间.所以排课的前提是必须有一个确定的排课原 则.我们采用轮转分配法作为排课原则:从星期一第1时间段开始按C1,C2,.,Cn中所列顺序安排完各门课程之后(每门课安排1次),再按该顺序继续向后面的时间段进行安排,直到所有课程的开课次数符合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=1T1,T2,.,Tn中各时间段分配字清零新一轮扫描课程:置继续处理标志flag=0对课程索引值c-index=1,2,.,n进行以下操作:如果Nc-index0,则做以下操作:把segment的值写入Tc-index的第(week-1)33week33-1位中Nc-index的值减1如果Nc-index0,则置flag=1如果week=5并且segment=4则:置flag=1并转否则:如果segment=4则:置segment=1且week增1否则:segment增1检测是否已全部安排完毕:如果flag=1则:转否则:转检测是否成功:如果flag=1则:开课次数过多否则:课程安排成功算法结束显然,本算法的时间复杂度为O(N)(N为每周总开课次数,见(2)式),而存储时间段分配字所用空间为2n个字节(n为课程门数).2.1.4.冲突检测算法有时在自动排课完毕后,需要人工调整某些课程的安排时间,如把第i门课程在人工干预下改成星期数为week、时间段为segment的位置,则根据上述数据结构需做如下运算:Ti=Ti&(7(week-1)*3)+(segment(week-1)*3),其中&、和n分别为按位与、按位取反和按位左移运算符(下同).问题是如何判断是否已有其它课程安排在同一个时间段上.设人工调整的时间段分配字为T1,则该问题描述为:判断时间段分配字T1与T2,T3,.,Tn中的某个分配字是否存在相同课程分配位上 的相等的非零时间段值,或者说T2,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)算法结束本算法时间复杂度为O(n)(n为课程门数)2.1.5.算法分析此算法以课程为中心，进行搜索匹配，取最先匹配的值；具有占有空间少，运算速度快的特点。但其未对数据进行择优选取，所以不能对教学资源（教师、教室）合 理分配，也不能满足一些特殊要求（比如有些老师喜欢上午上课，有些老师偏向于集中式上课；有些课程安排到上午会更合适些，有些课程不能安排到上午等）。22基于优先级的排课算法从数学上讲,排课问题是一个在时间、教师、学生和教室四维空间,以教学计划和各种特殊要求为约束条件的组合规划问题。其实质就是解决各因素之间的冲 突。在设计算法时,为了 降低课程调度的算法复杂性,我们 主要采用了化整为零的思想及优先级算法:2.2.1排课的预处理2.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.2.1.2教室分类为了合理使用教室,我们采用了教室分类的办法,以便尽可能在课程编排过程中避免上课人数少的课程盲目强占容量大的教室现象。首先将教室按照其类型分为若干个等价类,如下 所示,然后,根据教室的容量再分别对每个教室等价类进行划分:如分为030人、3060人、6090人、90120人、120180人 等若干种教室等价类的划分:教室类型等价类R教室类型等价类R普通教室R1听力教授R5投影教室R2物理实验室R6多媒体教室R3化学实验教室R7制图教室R4计算机实验教学R82.2.1.3.时间预处理1)构造时间模式库时间模式是根据教务人员的经验,为各种周学时数不同的课程指定的一种时间组合 方式.例如,一门课程的周学时数为4,那么它的时间组合方式可以有:“11”,“41”;表示该课程一周上两次,分别为周一的12节 和周四的12节L同时,为 了达到较好的上课效果,也要 对这些时间模式进行分级.如 下所示时间模式分级举例周学时优先级周一周二周三周四周五411141422243:其中,将周一至周五用数字15表 示,上课节次:12节、34节、56节、78节、晚12节、 晚34节分别用数字16表 示。例如数字“42”表示 周四的34节这个时间单元。这样,对于每种周学时数,可以将所有合理的时间组合形式存入模式库中。以便进行时间处理时可以用时间模式库中 的各种模式进行匹配。2)时间数组为了表示班级、教师、教室的可排课时间,分别 为他们建立一维数组L例如,某位教师的初始可排课时间数组为(123456123456123456123456123456)。其 中共有五组数据,分别表示一周中的五天;而一组数据共有6个 字符“1、2、3、4、5、6”分别表示一天中的六个时间单元。当为某位教师分配时间后,相应的那位字符就置为0L例如,某 位教师的可排课时间数组为(020456103456003456120456023456),则 表示这位教师在周一的12节和56节,周 二的34节,周三的12节 和34节,周四的56节,周五的12节 已经安排了课程,如果要再安排课程的话,就应该安排在非0的 时间单元L对于班级和教室也可以进行同样的处理,分别标出可排课时间。2.2.2每一子类的排课处理在对每个子类的排课处理中,我们结合了分治法、贪婪法、回溯法三者的思想L首先,根 据分治法的思想把整个排课过程分成时间分配和教室分配两个阶段。然后,依 据贪婪法的算法思想,在时 间分配时,总是在尚未分配的时间单元中选择上课效果最好的单元。而在时间分配发生死锁时,会向上回溯搜索到发生冲突的最近一个记录,然后对它进行重排以解决冲突。具体处理过程如下:2.2.2.1设定优先级对子类中的课程计算优先级L设优先级函数为:D(g)=J(g)*C1+T(g)*C2+P(g)*C3(1)其中,J(g)表示 课程级别,选修课的课程级别设置为1,必修课的课程级别设置为2;T(g)表示 该课程的周学时数;P(g)表 示该课程的参与人数;C1、C2、C3是可以调整的参数。由式(1)可 以看出课程级别越高、周学时越多、参加人数越多的课程,其D(g)值越大,其优先级也越高;反 之,D(g)值越 小,其优先级越低。这样,就可以根据计算的优先级的高低对课程进行排序,优先级高的优先调度。2.2.2.2查询可用时间单元第1步,初始化某门课程的最大可安排时间数组,为(123456123456123456123456123456)。第2步,找出参加该课程学习的所有班级。第3步,查 询每个班级的时间数组,得到 班级的已排课时间,并将 其与课程的最大时间数组相“与”,从而得到该课程不能安排的时间单元。第4步,依 次处理教师时间数组和相关教室时间数组,这样,该课程最终的可安排时间数组就是班级、教师、教室可排课时间的交集。2.2.2.3查找适当的时间模式找到可排课时间后,就应根据课程的周学时数在时间模式库中匹配适当的时间模 式。完成以上工作后,就确 定了课程的上课时间和地点。如果在处理中发生死锁,则 可根据回溯法的思想向上回溯搜索到发生冲突的最近一个记录,然 后对它进行重排以解决死锁,如果 仍不能解决死锁问题,则可 以将该课程信息输出到冲突列表中。2.2.3人工干预的处理计算机自动排课也需要进行人工干预,以便 可以使得各个高校能够根据自己的具体要求对排课算法中的一些参数进行设置和调整,并 对计算机排出的课表进行调整L本算 法所设计的人工干预过程有:等价类划分中参数的设置,教室类型的设置,时间模式库的设置,优先级函数中参数的设置。用户可以根据自己的具体要求对这些参数和库进行设置。另外,对于计算机排出的课程表,用 户也可以通过人机交互进行适当调整,从而 得到用户满意的课程表。2.2.4性能分析此算法对班级及教室划分等价类，对学校资源进行了合理的利用。但对一些特殊要求还是无法具体体现出来。3基于时间片优先级排课算法描述与分析排课问题实质上是时间、教师、班级、教室、课程这五维关系的冲突问题，要合理的解决这个问题首先要了解排课中的一些基本原则以及排课的一些基本要求。31排课中的基本原则在课程的编排中应遵循一定的规则,只有按照基本规则来进行课程的编排才能够减少冲突的发生,这些基本规则主要有以下几条:1)同一班级的学 生在同一时间(某些特定的选修课时间除外)不能安排两门课程2)同一教师在同 一时间不能安排两门课程3)同一教室在同 一时间不能安排两门课程4)同一时间安排 的课程总数不能大于所能提供的教室总数5)某一课程参加 学习的总人数不应大于所安排教室的座位数6)所提供教室的 属性与课程所需教室的属性一致在时间、教师、班级、教室、课程这五维关系中,时间、教师、班级三者之间存在着紧密关系。相对而言,教室与它们关系就不那么密切。32排课的基本要求课程的安排不是任意的,为了达到最好的教学效果应遵循一定的要求。这些要求主要有:1)要尽量为所排 课程安排上该类课效果最好的时间2)课程在一周上 多次时,要有一定的间隔性3)公共课等涉及 面广、学时多的课程应优先处理4)对同一教师,同一上课对象应尽量选择相对固定的几个教 室5)对同一个班级 的课程应选择相对固定的教室6)连着的课的教 室选择不应相隔太远7）同一天有几门课时尽量把课 分散8)优先满足一些 特殊要求（比如有些教室喜欢上上午的课，可以优先满足）33基于时间片优先级排课算法描述在描述算法之前我们把一些概念先讲清楚。在这里我们把从行政角度分的班叫自然班，把在同一个教室上课的班叫做排课班。在大学里有些公共课是几个排课班通过 多媒体来一起上的，我们把这个排课班的总和叫做公共班。班级、教室、教师、课程都维护着自己的一张课表。对课表的每个表元（如星期一的第一节课）在这里称 做时间片。基于时间片优先级排课算法以排课班为单位，围绕着各对像(自然班、教室、教室)的时间表选择合适的时间片。3.3.1算法流程图（无原图）3.3.2算法的伪代码描述输入：教师（teacher1,teacher2,.teachern）教 室（room1,room2,roomn）班 级（class1,class2,.classn）课 程（course1,course2,coursen）各 教师、教室、班级、课程时间片的优先级排课班(schudel_class1,schudel_class2schudel_classn)输出：已经排好课表的教 师、教室、班级Procedureschudeling(teacher,room,class,course,schudel_class,public_class)/初始化一张空的时间表，对 该时间表的每个时间片的优/先级初始化为高级InitTime_table/对排课班进行处理Foreveryschudel_classdo:If(!Check_Have_despose(schudel_class)/假如该排课班尚未排课Begin:Time_table=Time_table&get_all_class_time_table(schudel_class)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;LList*cpIntpriority7=0;/得到每天的优先级的总和Loop:I=0untilI=6do:Loop:J=0untilJ=6do:Begin:PriorityI=PriorityI+Time_table.time_pieceIjEndBegin/得到优先级总和最大的那天，我们认为那一时 间最闲/适宜安排课程intnumber=get_number(priority7);BOOLfailWhileiCount20do:Begin:fail=Get_Time_Pieces(2,&number,po);if(!fail)thendobegin:iCount2-;cp-append_list(po);endbeginelsebreak;EndBeginWhileiCount30do:Begin:fail=Get_Time_Pieces(3,&number,po);if(!fail)thendo:begin:ICount3-;Cp-append_list(po);EndbeginElseBreak;EndBegin/根据*cp的数据及schudel_class的数据对schudel_cla