排课算法研究

分支定界算法在中学排课问题中的应用 摘要：在本文中我们主要研究了带约束有教案的中学排课程表问题。首先我们得到了有关该问题的中学课程表必须满足的几个条件，因为该排课程表问题是一个NP难解的问题，因此该问题没有多项式时间算法，通过分析，我们提出了一个求解该问题的分支定界算法，数值证明这是一个有效的算法。 关键词：课程表问题；NP难解问题；分支定界算法 Abstract : In this paper we focus on the time-table problem for middle schools with constraints on tearchers’ teaching-plans. We first give some necessary conditions for fcasible fime-tables of the problem, because this problem is NP-head, which means that there does not exist an algorithm that solves this problem in polynomial-time. We propose a branch-and-bound algorithm. Our experiment result shows that the proposed algorithm is both efficient and effective for this problem. Key words: Time-table, NP-problem, branch-and-bound method. 一个学校的教与学的安排是由学校的规模及一定的要求来决定，一个学校有自己的教学方向这在一定程度上决定了这个学校的教师分配及所教科目在一个学期内的课时数分配。为了适当安排好学校的教学进度，就必须要安排好教师的讲课、学生的授课和教室、体育场地等等的合理使用，以免出现冲突和不合理的安排。所以，合理的课表安排是学校工作的重要组成部分。 事实证明，课表的安排问题是一个NP完全问题，只能根据各个学校的特点来安排适当的课程表，我们发现，对于高中学校来说，很多时候，授课教师往往要考虑到对几个班他要同时上课，这就要求每个班的进度必须一致，所以在老师备课写教案的时候就要考虑到这个问题，本文也正是从老师的教案入手，采用分支定界算法来解决课表的安排问题。 我们来分析一下排课程表问题。我们可以把课程表问题看成在满足下列一系列条件的可行域中，寻找一个可行点的问题。而排课条件基本上可以很自然地归结为以下几条： 1、 教师的教案问题（指一天教案） 2、 每门课在一周内的均衡分配 3、 每门课在一周内的上下午的均衡分配 4、 每个教师的同一门课所有班的同等对待 5、 集中排课 6、 其他排课条件 （条件1） 在分析之后，我们发现，其实对于排课问题最简单的方法是采用原始枚举法进行求解。这实际上是对一棵庞大的树进行搜索（这棵树的根就是排课的起点），因此这样做非常费时。下面我们给出基于分支定界思想的算法。实际在枚举的过程中，将产生大量的分支是无可行点的分支。比如在排了一些课后，教师的教案问题不满足，主课不满足要求，副科排不了了等等。当不满足要求时，以下的所有分支都无可行点，所以可以大胆地把它们去掉。因而采用分支定界法来剪支。怎样定界？采用一种判别原则，也即在排课程表时，定义一种抽象的界，使得在排到某个课时，它是否超过了这个界，如果超过了这个界，就把它剪掉。同样，可以注意到，当先排某些课时将使得可行点很难找到，因为有各种排课条件。所以将适当调整这些课程的序列，使在枚举过程中尽早地出现可行点。我们将在下面给予具体的说明。 1、 分支的方法 不妨设每个班第i门课有li个课时。首先对这n个班的所有l门课按课程进行适当的排 序（根据每个学校的情况而定）。然后再对每门课程按教师进行排序。这样就得到了一个教案序列J=（J1，J2，……Ji）,其中Ji表示第i门课。而Ji=（Ji1,Ji2,…….jiti）表示第i门课共有ti个教师来教这n个班。排课时就按照这个序列进行。 现在开始排课。先排第一门课的第一个教师所教的第一个班，也就是树的根。这个课（n1,l11）的所有排法就是它的所有分支。当排定一个课后（也就是选定一个分支），不妨设排在一个位置（d,t），再排此教师的下一个班的这门课，当排完了此教师的此门课的所有班，再排此教师的此门课的第二轮教案。当排完了此教师的所有课程后，再排下一个教师的此门课的班，排完了这门课后，再排下一门课。如此建立了一课树，这棵树总共有S=n 层（如果有可行解的话）。 我们的目的是要找到一种搜索方法F，使得F尽可能快的走到这棵树的第S层。在这棵树上可以看到会有大量的分支将达不到S层。为了剪掉那些不能到达S层的分支，我们要定义一个界B，当搜索方法F搜索到一个分支T=（Ji,Jit,nijk,d,t）（即第i门课，第j个教师，第k个班，在位置（d,t），简记为[d,t]）时，已发现它的界已超过了界B，就往回走，当实时搜索到位置[d,t]时，已得到了一些有关这个搜索方法F在此位置的一些信息M，利用这些信息M决定F将撤回到哪一层，而不是只回撤一层，这样就大大地减少了需要搜索的分支，以提高速度。 2、 定界的方法 从上面的分析可以对分支定界法的界做一定义如下： （1） 界A1，A2，A3，A4，A5的定义： 对排课程表中的限制条件分别用A1，A2，A3，A4，A5来表示。我们不妨把它们作为 排课过程中的一些界。如果不满足它们就表示超出了这些界。此时的这个分支将无可行解。 （2） 界A6的定义： 设课表是w·v,w是一周中上课天数，v是一天中上课节数，对于每个班都有两个拆分： 第一拆分和第二拆分。而且必须满足：第一拆分≤第二拆分 这就是界A6。 （3） 界A7的定义： 界A7就是：在一个年级中，一周中未被使用的空的重复数必须小于等于可利用此空 的剩余教案的教案数。 （4） 界A8的定义： 界A8就是：整个年级剩余空的重复数和整个年级剩余教案数序的关系。 （5） 界A9的定义： 当已判断出在位置[d,t]已无可行解时，利用信息M（它主要包括：1、由哪些界导致 此课排不下，2、此课需要什么类型的位置[包括哪一天和上下午的的位置]），将判断出位置[d,t]的上一层是否与在排课有关，如果无关则再往上，一步一步往上走，直到发现与在排课有关为止（在实际人工调课时也是如此）。 3、 分支定界算法描述 从上面的讨论和分析，对求解排课问题可行解的搜索采用分支定界法，对每一个教案 逐一进行比配，其搜索过程如下： 从树的分支开始（选择了一个教案），首先判断此教案所涉及到的班级中空的情况，即 首先考虑禁止点的问题。再计算此教案每个班的第一拆分和第二拆分，判断它们是否满足 多连堂排课情况，再判断界A7和A8的情况，当这些班的那些空同时满足了教案的要求、周均衡性分配和天均衡性分配的条件，再判断是否要求和能否满足集中排课条件。当这些界都满足了，则进行排课。如果排此教案成功，则接着排下一个教案。如果排课没有成功（包括已判断出此时已超过某个或某些界{Ai}或者没有判断出超过某个界，但无法排下此教案），则根据这些信息，判断并计算出此时应该回撤到哪一层。这时对最后一个已排成功的教案搜索下一种排法。如此循环，直到排课成功或者第一个教案已无法排出下一种可能为止。 这样可以得到一个分支定界算法如下： 1、 开始排课； 2、 选择一个教案； 3、 如果所有教案都已被选择，即都已被排成，转到排课成功 4、 对此教案进行排课； 5、 排一种此教案的课表； 6、 找到了一种排法T； 7、 如果满足界A1，A2，A3，A4，A5，A6，A7和A8则； 8、 如果满足排课条件（条件1），则转到：选择一个教案 9、 否则转到：排一种此教案的课表 10、 否则转到：排一种此教案的课表 11、 没有找到下一种排法，如果此教案是第一个，则无解，转到结束 否则根据界A9判断将往上走到哪一层，并转到 排一种此教案的课表 12、 此教案排课成功，则转到选择一个教案 13、 排课成功 14、 结束 4、 分支定界算法的具体计算结果 对7个班、12门课、27个教师，满足条件（条件1）中的几个条件的三种情形： 星期一 星期二 星期三 星期四 星期五 第一节 第二节 高二（6） 高二（6） 第三节 高二（2） 第四节 高二（1） 高二（6） 第五节 高二（1） 高二（1） 高二（2） 高二（1） 第六节 高二（6） 高二（2） 高二（2） 第七节 表9 王老师的 语文 八上语文短文两篇二年级语文一匹出色的马课件部编版八上语文文学常识部编八上语文文学常识二年级语文一匹出色的马课件 授课表 星期一 星期二 星期三 星期四 星期五 第一节 高二（1） 第二节 高二（2） 高二（6） 第三节 高二（6） 高二（1） 高二（2） 第四节 第五节 高二（1） 高二（2） 高二（6） 第六节 高二（2） 第七节 高二（6） 高二（1） 表10 星期一 星期二 星期三 星期四 星期五 第一节 第二节 高二（2） 高二（6） 第三节 高二（1） 高二（6） 高二（2） 高二（1） 第四节 高二（1） 第五节 高二（6） 高二（2） 第六节 高二（6） 第七节 高二（2） 高二（1） 表11 第一种情形：只有条件（条件1）中的条件2和条件6时计算得到如表9的课表（只对杨老师的化学课进行比较）。 第二种情形：满足条件（条件1）中的条件1、2、3、4和6五个条件时计算得到如表10的课表。 第三种情形：当满足（条件1）、并且在集中排课条件中的n=2时计算得到如表11的课表 从上面可以看出，当条件加强时，排出来的课表也将更加满足实际的使用的要求。 5、 课程表的调整 当已排好的课程表中某个或某些教师的课程，由于某种原因不能上课或者需要调整， 也就是在已排好的位置被设成了禁止点。希望得到一个新的课程表，这是一类新的问题。它要求被调整的课程表上作最少的修改（调课）。它也是一个最优化的问题。也可以用分支定界法求解，只是界的定义要作适当的变化。 从上可以看到，对中学课程表问题要解决的几个主要问题是：教案问题（包括一天的教案）、教师教课的集中排课问题、同一班级不同科目的周均衡问题、同一年级同一科目的周均衡问题。但最关键的问题是对教师的合理安排，因为在我国通常学生的授课时间没有什么限制。而教师常常有这样和那样的限制（要求）。另外，我国的教学对一些科目比较重视，而对另外一些科目要求要低一些，这也产生了一些限制。 参考文献： 1、D.J.A. Welsh and M.B.Powell(1976).”An upper bound for the chromatic number of a graph znd its application to time-tabling problems”, Computer J,10,85-87 2、M.R.Garey and D.S.Johnson, Computers and Intractability:A Guide to the Theory of NP-Completeness, San Francisco, CA: Preeman, 1979. 3、M.A.H.Dempster, “Two Algorithms for the Time-table Problem”, Combinatorial Mathematics and its Applications, Academic Press, London and New York, 1971, p.63-85. _1234617944.unknown