在高等院校中，培养学生的主要途径是教学。在教学活动中，有一系列管理工作，其中，教学计划的实施是一个重要的教学环节。每学期管理人员都要整理教学计划，根据教学计划下达教学任务书，然后根据教学任务书编排课程表。在这些教学调度工作中，既有大量繁琐的数据整理工作，更有严谨思维的脑力劳动，还要填写大量的表格。因此工作非常繁重。
加之，随着教学改革的进行及“211”工程的实施，新的教育体制对课表的编排提出了更高的要求。手工排课时，信息的上通下达是极其麻烦的，而采用计算机排课，教学中的信息可以一目了然，对于优化学生的学习进程，评估每位教师对教学的贡献，领导合理决策等都具有重要的意义，必将会大大推进教学的良性循环。
2课题的应用领域
本课题的研究对开发高校排课系统有指导作用。
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）系统，大连理工大学的智能教学组织管理与课程调度等，这些系统大多数都是模拟手工排课过程，以“班”为单位，运用启发式函数来进行编排的。但是这些系统课表编排系统往往比较依赖于各个学校的教学体制，不宜进行大量推广。
从实际使用的情况来看，国内外研制开发的这些软件系统在实用性上仍不尽如人意。一方面原因是作为一个很复杂的系统，排课要想面面俱到是一件很困难的事；另一方面每个学校由于其各自的特殊性，自动排课软件很难普遍实用，特别是在调度的过程中一个很小的变动，要引起全部课程的大调整，这意味着全校课程大变动，在实际的应用中这是很难实现的事。
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。
（三）回溯法
回溯法有“通用的解题法”之称。用它可以求出问题的所有解或任一解。概括地说，回溯法是一个既带有系统性又带有跳跃性的搜索法。它在包含问题所有解的一颗状态空间树上，按照深度优先的策略，从根出发进行搜索。搜索每到达状态空间树的一个节点，总是先判断以该节点为根的子树是否肯定不包含问题的解。如果肯定不包含，则跳过对该子树的系统搜索，一层一层地向它的祖先节点继续搜索，直到遇到一个还有未被搜索过的儿子的节点，才转向该节点的一个未曾搜索过的儿子节点继续搜索；否则，进入子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根的所有儿子都已被搜索过才结束；而在用来求问题的任一解时，只要搜索到问题的一个解就可结束。
1.问题的描述
我们讨论的自动排课问题的简化描述如下:
n≤20,(1)
N=6n，i=1，Ni≤20.(2)
2.主要数据结构
3.排课算法
在上述假设下,自动排课算法的目标就是确定{C1,C2,.,Cn}所对应的{T1,T2,.,Tn}.
和{T1,T2,.,Tn}也采用同样的表示法.
算法1排课算法
输入{C1,C2,.,Cn}、{N1,N2,.,Nn}.
输出{T1,T2,.,Tn}.
①初始化:
星期值week=1
②新一轮扫描课程:
置继续处理标志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且week增1
否则:segment增1
检测是否已全部安排完毕:
如果flag=1
则:转②
否则:转③
③检测是否成功:
则:开课次数过多
否则:课程安排成功
④算法结束
4.冲突检测算法
T[i]=T[i]&(～(7<<(week-1)*3))+(segment<<(week-1)*3),
其中&、～和n分别为按位与、按位取反和按位左移运算符(下同).
算法2冲突检测算法
输入T1和{T2,.,Tn}.
①对c-index=2,3,.,n做以下操作:
初始化屏蔽字mask=7
对星期值week=1,2,3,4,5做以下操作:
如果T[1]&mask等于T[c-index]&mask,而且二者不等于0
则:T[1]与T[c-index]相冲突,转①
mask左移3位(或乘8)
②算法结束
5.算法分析
此算法以课程为中心，进行搜索匹配，取最先匹配的值；具有占有空间少，运算速度快的特点。但其未对数据进行择优选取，所以不能对教学资源（教师、教室）合理分配，也不能满足一些特殊要求（比如有些老师喜欢上午上课，有些老师偏向于集中式上课；有些课程安排到上午会更合适些，有些课程不能安排到上午等）。
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．教室分类
为了合理使用教室,我们采用了教室分类的办法,以便尽可能在课程编排过程中避免上课人数少的课程盲目强占容量大的教室现象。
首先将教室按照其类型分为若干个等价类,如下所示,然后,根据教室的容量再分别对每个教室等价类进行划分:如分为0～30人、30～60人、60～90人、90～120人、120～180人等若干种
教室等价类的划分:
教室类型等价类R教室类型等价类R
普通教室R1听力教授R5
投影教室R2物理实验室R6
多媒体教室R3化学实验教室R7
制图教室R4计算机实验教学R8
周学时优先级周一周二周三周四周五
411141
∶∶
422243
::
其中,将周一至周五用数字1～5表示,上课节次:12节、34节、56节、78节、晚12节、晚34节分别用数字1～6表示。例如数字“42”表示周四的34节
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)值越小,其优先级越低。这样,就可以根据计算的优先级的高低对课程进行排序,优先级高的优先调度。
间的交集。
3．人工干预的处理
计算机自动排课也需要进行人工干预,以便可以使得各个高校能够根据自己的具体要求对排课算法中的一些参数进行设置和调整,并对计算机排出的课表进行调整L本算法所设计的人工干预过程有:
4．性能分析
此算法对班级及教室划分等价类，对学校资源进行了合理的利用。但对一些特殊要求还是无法具体体现出来。
在课程的编排中应遵循一定的规则,只有按照基本规则来进行课程的编排才能够减少冲突的发生,这些基本规则主要有以下几条:
5)某一课程参加学习的总人数不应大于所安排教室的座位数
6)所提供教室的属性与课程所需教室的属性一致
课程的安排不是任意的,为了达到最好的教学效果应遵循一定的要求。这些要求主要有:
2)课程在一周上多次时,要有一定的间隔性
3)公共课等涉及面广、学时多的课程应优先处理
4)对同一教师,同一上课对象应尽量选择相对固定的几个教室
5)对同一个班级的课程应选择相对固定的教室
6)连着的课的教室选择不应相隔太远
7）同一天有几门课时尽量把课分散
8)优先满足一些特殊要求（比如有些教室喜欢上上午的课，可以优先满足）
1．算法流程图
2．算法的伪代码描述
输入：教师（teacher1,teacher2,…………….teachern）
教室（room1,room2,…………………roomn）
班级（class1,class2,………………….classn）
课程（course1,course2,………………coursen）
排课班(schudel_class1,schudel_class2………schudel_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个
CPointpo;
LList
Intpriority[7]=0;
//得到每天的优先级的总和
Loop:I=0untilI=6do:
Loop:J=0untilJ=6do:
Priority[I]=Priority[I]+Time_table.time_piece[I][j]
EndBegin
//适宜安排课程
intnumber=get_number(priority[7]);
BOOLfail
WhileiCount2>0do:
fail=Get_Time_Pieces(2,&number,po);
if(!fail)thendo
begin:
iCount2--;
cp->append_list(po);
endbegin
else
break;
WhileiCount3>0do:
fail=Get_Time_Pieces(3,&number,po);
if(!fail)thendo:
ICount3--;
Cp->append_list(po);
Endbegin
Else
Break;
//根据*cp的数据及schudel_class的数据对schudel_class中的自然班，所得到的教室，
//老师的课表进行回写
if(!fail)do
WriteBack(schudel_class,cp);
Elsethen
RollBack(schudel_class,cp);//把先前选好的教室，老师给”擦除”掉
EndSchudeling
算法里面有到的一些函数解释：
BOOLcheck_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):以排课班为参数，为该排课班选择一合适的教师，并返回该教师的课表
Ccourseget_course(schudel_class):以排课班为参数，得到该排课班的课程，并返回之
Intget_course_count(Ccourse):以课程为参数，得到该课程每周所需上的课时数，并返回之
Parse_course_count(int&,int&,int&):分析get_course_count所返回的数值，把该数值以2节连堂和3节连堂分开(在这里假设只有2节连堂和3节连堂两种情况)
IntGetNumber(int*):传进一整型数组，得到该整型数组中的最大值的下标，并返回之
RollBack(schudel_class,Llist
计算机排课是个复杂的过程，在数据量大，约束条件多的条件下，通过人工干涉达到合理排课是非常重要的。人工干涉包括在排课前的一些数据输入工作，人工进行些预排课，排完课后对课表进行适当的调课。
此算法属于贪心算法。每次对教师、教室资源的选取都是取当前最优的数据。此算法对按照教师、教室、班级的优先级取最优值，所以对各对象的一些特殊要求会很明显的体现出来，在教师、教室资源不紧缺的情况下，此算法能排出相对合理的课程。相对于上一章介绍的两个算法，在处理各种特殊要求的能力上有明显的优势。