自动排课算法分析

1   绪 论

1．1课题背景与研究意义

1．2课题的应用领域

1．3 课题的现状

1．4解决NP问题的几种算法及其比较

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

2．1. 自动排课算法

2．2 基于优先级的排课算法

3   基于时间片优先级排课算法描述与分析

3．1排课中的基本原则

3．2排课的基本要求

3．3基于时间片优先级排课算法描述

3．4算法分析

参 考 资 料

1   绪 论

 1课题背景与研究意义

排课问题早在70年代就证明是一个NP完全问题，即算法的计算时间是呈指数增长的，这一论断确立了排课问题的理论深度。对于NP问题完全问题目前在数学上是没有一个通用的算法能够很好地解决。然而很多NP完全问题目具有很重要的实际意义，例如。大家熟悉地路由算法就是很典型的一个NP完全问题，路由要在从多的节点中找出最短路径完成信息的传递。既然都是NP完全问题，那么很多路由算法就可以运用到解决排课问题上，如Dijkstra算法、节点子树剪枝构造网络最短路径法等等。

   目前大家对NP 完全问题研究的主要思想是如何降低其计算复杂度。即利用一个近似算法来代替，力争使得解决问题的时间从指数增长化简到多项式增长。结合到课表问题就是建立一个合适的现实简约模型，利用该简约模型能够大大降低算法的复杂度，便于程序实现，这是解决排课问题一个很多的思路。

在高等院校中，培养学生的主要途径是教学。在教学活动中，有一系列管理工作，其中，教学计划的实施是一个重要的教学环节。每学期管理人员都要整理教学计划，根据教学计划下达教学任务书，然后根据教学任务书编排课程表。在这些教学调度工作中，既有大量繁琐的数据整理工作，更有严谨思维的脑力劳动，还要填写大量的表格。因此工作非常繁重。

加之，随着教学改革的进行及“211”工程的实施，新的教育体制对课表的编排提出了更高的要求。手工排课时，信息的上通下达是极其麻烦的，而采用计算机排课，教学中的信息可以一目了然，对于优化学生的学习进程，评估每位教师对教学的贡献，领导合理决策等都具有重要的意义，必将会大大推进教学的良性循环。

 2课题的应用领域

本课题的研究对开发高校排课系统有指导作用。

排课问题的核心为多维资源的冲突与抢占，对其研究对类似的问题（特别是与时间表有关的问题：如考试排考场问题、电影院排座问题、航空航线问题）也是个参考。

   3 课题的现状

年代末，国外就有人开始研究课表编排问题。1962年，Gotlieb曾提出了一个课表问题的数学模型，并利用匈牙利算法解决了三维线性运输问题。次后，人们对课表问题的算法、解的存在性等问题做了很多深入探讨。但是大多数文献所用的数学模型都是Gotlieb的数学模型的简化或补充，而至今还没有一个可行的算法来解决课表问题。

     近40年来，人们对课表问题的计算机解法做了许多尝试。其中，课表编排的整数规划模型将问题归结为求一组0-1变量的解，但是其计算量非常大。解决0-1线性优化问题的分支一定界技术却只适用也规模较小的课表编排，Mihoc和Balas（1965）将课表公式化为一个优化问题，Krawczk则提出一种线性编程的方法。Junginger将课表问题简化为三维运输问题，而Tripathy则把课表问题视作整数线性编程问题并提出了大学课表的数学模型。

     此外，有些文献试图从图论的角度来求解排课表的问题，但是图的染色问题也是NP完全问题，只有在极为简单的情况下才可以将课表编排转化为二部图匹配问题，这样的数学模型与实际相差太远，所以对于大多数学校的课表编排问题来说没有实用价值。

     进入九十年代以后，国外对课表问题的研究仍然十分活跃。比较有代表的有印度的Vastapur大学管理学院的ArabindaTripathy、加拿大Montreal大学的Jean Aubin和Jacques Ferland等。目前，解决课表方法的问题有：模拟手工排课法，图论方法，拉格朗日法，二次分配型法等多种方法。由于课表约束复杂，用数学方法进行描述时往往导致问题规模剧烈增大，这已经成为应用数学编程解决课表问题的巨大障碍。国外的研究表明，解决大规模课表编排问题单纯靠数学方法是行不通的，而利用运筹学中分层规划的思想将问题分解，将是一个有希望得到成功的办法。

     在国内，对课表问题的研究开始于80年代初期、具有代表性的有：南京工学院的UTSS（A University Timetable Scheduling System）系统，清华大学的TISER（Timetable SchedulER）系统，大连理工大学的智能教学组织管理与课程调度等，这些系统大多数都是模拟手工排课过程，以“班”为单位，运用启发式函数来进行编排的。但是这些系统课表编排系统往往比较依赖于各个学校的教学体制，不宜进行大量推广。

从实际使用的情况来看，国内外研制开发的这些软件系统在实用性上仍不尽如人意。一方面原因是作为一个很复杂的系统，排课要想面面俱到是一件很困难的事；另一方面每个学校由于其各自的特殊性，自动排课软件很难普遍实用，特别是在调度的过程中一个很小的变动，要引起全部课程的大调整，这意味着全校课程大变动，在实际的应用中这是很难实现的事。

  4解决NP问题的几种算法及其比较

    解决NP完全问题只能依靠近似算法，所以下面介绍几种常用算法的设计思想，包括动态规划、贪心算法、回溯法等。

动态规划法是将求解的问题一层一层地分解成一级一级、规模逐步缩小的子问题，直到可以直接求出其解的子问题为止。分解成的所有子问题按层次关系构成一颗子问题树。树根是原问题。原问题的解依赖于子问题树中所有子问题的解。动态规划算法通常用于求一个问题在某种意义下的最优解。设计一个动态规划算法，通常可按以下几个步骤进行：

    1. 分析最优解的性质，并刻划其结构特征。

    2. 递归的定义最优解。

    3. 以自底向上的方式计算出最优解。

    4. 根据计算最优解时得到的信息，构造一个最优解。

步骤1~3是动态规划算法的基本步骤。在只需要求出最优解的情形，步骤4可以省去。若需要求出问题的一个最优解，则必须执行步骤4。此时，在步骤3中计算最优解时，通常需记录更多的信息，以便在步骤4中，根据所记录的信息，快速地构造出一个最优解。

（二）贪心算法

当一个问题具有最优子结构性质时，我们会想到用动态规划法去解它，但有时会有更简单、更有效的算法，即贪心算法。顾名思义，贪心算法总是做出在当前看来最好的选择。也就是说贪心算法并不是整体最优上加以考虑，他所作出的选择只是在某种意义上的局部最优的选择。虽然贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解，如图的算法中单源最短路径问题，最小支撑树问题等。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解。

在贪心算法中较为有名的算法是Dijkstra算法。它作为路由算法用来寻求两个节点间的最短路径。Dijkstra算法的思想是：假若G有n个顶点，于是我们总共需要求出n-1条最短路径，求解的方法是：初试，写出V0(始顶点)到各顶点(终顶点)的路径长度，或有路径，则令路径的长度为边上的权值；或无路经，则令为∞。再按长度的递增顺序生成每条最短路径。事实上生成最短路径的过程就是不断地在始顶点V何终顶点W间加入中间点的过程，因为在每生成了一条最短路径后，就有一个该路径的终顶点U，那么那些还未生成最短路径的路径就会由于经过U而比原来的路径短，于是就让它经过U。

（三）回溯法

回溯法有“通用的解题法”之称。用它可以求出问题的所有解或任一解。概括地说，回溯法是一个既带有系统性又带有跳跃性的搜索法。它在包含问题所有解的一颗状态空间树上，按照深度优先的策略，从根出发进行搜索。搜索每到达状态空间树的一个节点，总是先判断以该节点为根的子树是否肯定不包含问题的解。如果肯定不包含，则跳过对该子树的系统搜索，一层一层地向它的祖先节点继续搜索，直到遇到一个还有未被搜索过的儿子的节点，才转向该节点的一个未曾搜索过的儿子节点继续搜索；否则，进入子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根的所有儿子都已被搜索过才结束；而在用来求问题的任一解时，只要搜索到问题的一个解就可结束。

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

2．1. 自动排课算法

1 .问题的描述

我们讨论的自动排课问题的简化描述如下:

设要安排的课程为{ C1 , C2 , ., Cn} ,课程总数为n , 而各门课程每周安排次数(每次为连续的2 学时) 为{ 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 } 中每个课程的教学应占据的时间段,并且保证任何一个时间段仅由一门课程占据.

2 .主要数据结构

对于每一门课程,分配2 个字节的“时间段分配字”(无符号整数) :{ T1 , T2 , ., Tn} . 其中任何一个时间段分配字(假设为Ti ) 都具有如下格式:

Ti 的数据类型C 语言格式定义为:unsigned int . Ti 的最高位是该课程目前是否是有效的标志,0 表示有效,1 表示无效(如停课等) ;其它各位称为课程分配位, 每个课程分配位占连续的3 个位(bit) ,表示某教学日(星期一～ 星期五) 安排该课程的时间段的值,0 表示当日未安排,1 ～ 4 表示所安排的相应的时间段(超过4 的值无效) .

在这种设计下, 有效的时间段分配字的值应小于32 768 (十六进制8000) , 而大于等于32 768 的时间段分配字对应于那些当前无效的课程(既使课程分配位已设置好也如此) , 因此很容易实现停课/ 开课处理.

3 .排课算法

在上述假设下,自动排课算法的目标就是确定{ C1 , C2 , ., Cn} 所对应的{ T1 , T2 , ., Tn} .

从安排的可能性上看,共有20 !/ (20 - N) !种排法( N 的含义见(2) 式) . 如果有4 门课,每门课一周上2 次,则N = 8 ,这8 次课可能的安排方法就会有20 !/ (20 - 8) ! = 5 079 110 400 ,即50 多亿种. 如果毫无原则地在其中选择一种方案,将会耗费巨大量的时间. 所以排课的前提是必须有一个确定的排课原则. 我们采用轮转分配法作为排课原则:从星期一第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} .

①　初始化:

　　星期值week = 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) 3 3～week 3 3 - 1 位中　　N[c-index ]的值减1

　　　　如果N[c-index ] > 0 ,则置flag = 1

　　　　如果week = 5 并且segment = 4

　　    则:置flag = 1 并转③

　　否则:如果segment = 4

　　　　则:置segment = 1 且week 增1

　　　　否则:segment 增1

　　　　　　检测是否已全部安排完毕:

　　如果flag = 1

　　则:转②

　　否则:转③

③　检测是否成功:

　　如果flag = 1

　　则:开课次数过多

　　否则:课程安排成功

④　算法结束

显然,本算法的时间复杂度为O ( N) ( N 为每周总开课次数, 见(2) 式) , 而存储时间段分配字所用空间为2 n 个字节( n 为课程门数) .

4 .冲突检测算法

有时在自动排课完毕后,需要人工调整某些课程的安排时间,如把第i 门课程在人工干预下改成星期数为week 、时间段为segment 的位置,则根据上述数据结构需做如下运算:

　　　　T [ i ] = T [ i ] &(～ (7

2．算法的伪代码描述

           输入：教师（teacher1,teacher2,…………….teachern）

                 教室（room1,room2,…………………roomn）

                 班级（class1,class2,………………….classn）

                 课程（course1,course2,………………coursen）

                 各教师、教室、班级、课程时间片的优先级

          排课班(schudel_class1,schudel_class2………schudel_classn)

          输出：已经排好课表的教师、教室、班级

Procedure schudeling(teacher,room,class,course,schudel_class,public_class)

//初始化一张空的时间表，对该时间表的每个时间片的优//先级初始化为高级

Init Time_table

         //对排课班进行处理

   For every schudel_class do:

    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);

            //假设只有两节连堂及三节连堂那种课

            Int iCount2=0;//那门课两节连堂的次数

            Int iCount3=0;//那门课三节连堂的次数

            //得到课程每周的课时数

Int course_count=get_couse_count(Course);

//得到每周的连课情况

            Parse_couse_count(course_count,&iCount2,&iCount3);

//根据iCount2,iCount3,以及Time_table为该排课班选择N个

//(N=iCount2+iCount3)适当的时间片,保存在CPoint变量中

            CPoint po;

LList* cp

Int priority[7]=0;

//得到每天的优先级的总和

    Loop:I=0 until I=6 do:

         Loop: J=0 until J=6 do:

          Begin:

               Priority[I] =Priority[I]+ Time_table.time_piece[I][j]

          End Begin

          //得到优先级总和最大的那天，我们认为那一时间最闲

//适宜安排课程

          int number=get_number(priority[7]);

          BOOL fail

          While iCount2>0 do:

              Begin:

                  fail=Get_Time_Pieces(2,&number,po);

                  if(!fail) then do

                    begin:

                       iCount2--;

                       cp->append_list(po);

                    end begin

                  else

                     break;

              End Begin

          While iCount3>0 do:

              Begin:

                  fail=Get_Time_Pieces(3,&number,po);

                  if(!fail) then do:

                    begin:

ICount3--;

                      Cp->append_list(po);

                    End begin

                   Else

                     Break;

              End Begin

//根据*cp的数据及schudel_class的数据对schudel_class中的自然班，所得到的教室，

// 老师的课表进行回写

if(!fail) do

WriteBack(schudel_class,cp);

Else then

  RollBack(schudel_class,cp);//把先前选好的教室，老师给”擦除”掉

        End Begin

     End Schudeling

算法里面有到的一些函数解释：

BOOL check_for_dispose(schudel_class):以排课班为参数，判断该排课班是否已经排好课，排好了返回treu，否则返回false

 ‘&’操作:该操作是对两个课表的运算，返回一个新课表；得到的课表的时间片为所运算的课表对应时间片的较小值

CTime_table& get_all_class_time(schudel_class):以排课班为参数，得到该排课班所有自然班课表的&，返回得到的新课表

CTime_table& get_room(schudel_class):以排课班为参数，为该排课分配所有合适的教室，并把所得到的教室的课表求&，返回新课表

CTime_table& get_teacher(schudel_class):以排课班为参数，为该排课班选择一合适的教师，并返回该教师的课表

Ccourse get_course(schudel_class):以排课班为参数，得到该排课班的课程，并返回之

Int get_course_count(Ccourse):以课程为参数，得到该课程每周所需上的课时数，并返回之

Parse_course_count(int&,int&,int&):分析get_course_count所返回的数值，把该数值以2节连堂和3节连堂分开(在这里假设只有2节连堂和3节连堂两种情况)

Int GetNumber(int*):传进一整型数组，得到该整型数组中的最大值的下标，并返回之

WriteBack(schudel_class,Llist*):根据Llist* 中的时间片值，更新public_class中的教师，班级，教室的时间表信息

RollBack(schudel_class,Llist*):擦除前面步骤在排课班、教师、班级、教室中写下的数据

计算机排课是个复杂的过程，在数据量大，约束条件多的条件下，通过人工干涉达到合理排课是非常重要的。人工干涉包括在排课前的一些数据输入工作，人工进行些预排课，排完课后对课表进行适当的调课。

3．4算法分析

此算法属于贪心算法。每次对教师、教室资源的选取都是取当前最优的数据。此算法对按照教师、教室、班级的优先级取最优值，所以对各对象的一些特殊要求会很明显的体现出来，在教师、教室资源不紧缺的情况下，此算法能排出相对合理的课程。相对于上一章介绍的两个算法，在处理各种特殊要求的能力上有明显的优势。