排课问题的数学模型

崔　妍，王　权，王　康，车玉军

(沈阳工程学院 信息学院，辽宁 沈阳 110136)



排课问题的数学模型

崔妍，王权，王康，车玉军

(沈阳工程学院 信息学院，辽宁 沈阳 110136)

对适合于计算机编程的排课问题的数学模型进行了初步的探索，应用抽象代数中的cartison理论和图论中的二部图理论对排课资源进行合理的抽象，最终建立了两种排课问题的数学模型。针对高校排课系统的现状，将学生、课程、教师、教室4个集合进行了配对，利用层次扫描的方法，成功地解决了排课中的撞课问题。

cartesian积；层次扫描；边着色；二部图

1　研究背景

随着高校年年扩招，学生的人数逐渐增多，而与之配套的教师﹑教室等硬件资源增长相对落后。这样的变化对教务处每学期的排课来说变得“头疼和难以下手”。 传统的手工排课方法可以应对班级少﹑课程变化小的情况，而辛苦排出来的课表又常出现这样或那样的问题。例如，一个教室在同一时间分配给了上不同课程的几个班级；一位教师在同一时间安排了两门课等等。一错动全局，既耗费了时间又降低了工作效率。

随着高校办公软件的应用、校园网的建立，校内所属各单位的许多资料、数据都可以通过校园网传送。重新设计排课系统不仅可以从根本上避免人力、物力资源的极大浪费，而且还可以适应数据动态变化。

2　排课问题的数学模型

2.1cartesian积

定义：设A、B为集合，用A中元素为第一元素、B中元素为第二元素构成有序对，所有这样的有序对组成的集合叫做A与B的cartesian积。

cartesian积的符号化为：A×B={|x∈A∧y∈B}。例如，A={a,b},B={0,1,2},则A×B={,,,,,,}。

2.2问题的转化

排课系统可归结为班级﹑课程﹑教师﹑教室的关系问题。现设有班级集B,B={b1,b2,…,bm}，课程集C，C={c1,c2,…,cn},教师集T,T={t1,t2,…,tq},教室集R,R={r1,r2,…,rp}。其中，m为班级数，n为课程总数，q为本学期任课教师的人数，p为教室数。显然，排课问题成了4个集合之间的关系问题，如图1所示。

图1　排课关系

班级集合和课程集合的关系如图2所示。

图2　班级与课程关系

于是，得出班级与课程结合后的集合：

B_C=B×C={|bi与cj满足排课条件}

上式中，i=1,2,…,m;j=1,2,…,n。其中bi与cj的约束条件：

1)班级人数在25～35之间；

同理，将班级课程集与教师集结合，得

B_C_T=B_C×T={|bi,cj和

tl满足排课条件}

其中，l=1,2,…,q。约束条件为

最后，将B_C_T集与教室集结合得到排课所需的集合：

B_C_T_R={(bi,cj,tl,re)|bi,cj,tl和

re和满足排课条件}

其中，e=1,2,…,p。约束条件为课程是否允许合堂、教室的容量等等。

2.3模型的建立

排课表的过程是按单元将班级按顺序给出适合的教室和教师。因此，从理论上来说只要给出一门课和学习该门课的所有班级与教师的安排就可以排出整个学校所有班级的课程表。而单位课程的安排过程就是将班级集、课程集、教师集和教室集的配对再配上时间的过程。

第一步，结合班级和课程集合。在集合B中选取具体的班级组成新的班级集B′，在集合C中选取与其对应的课程组成新的课程集C′，做B′与C′的二维cartesian积：K1=B′×C′={(bi,cj)|bi与cj满足排课条件}。K1集合中的每一个元素都满足排课条件，称为班级课程对。

第二步，把K1与对应的教师结合，按排课条件生成三维cartesian积：K2={(bi,cj,tl)|bi，cj和tl满足排课条件}。K2集合中的元素称为班级课程教师对。

第三步，把K2与对应教室结合，按排课条件生成四维cartesian积：K3={(bi,cj,tl,re)|bi,cj,tl和re满足排课条件}。K3集合中的元素称为班级课程教师教室对。这里K3中包含的元素，是排课表时所需要的数据，它同时也是最后所要生成的课表集合。

2.4算法的描述

根据B_C集中对元素(班级bi，课程cj)的约束条件，首先对集合B与集合C中满足条件的元素做cartesian积，然后按系别层次扫描教师集中的元素教师tl，把适合讲授课程cj的教师分配给班级bi，形成一个新的集合B_C_T。这时与tl结合送入B_C_T集合中，并且从B_C集中删除点对。这样B_C集合中的点对足渐减少，当B_C中所有的点对都分配了教师，B_C集为空，此时一次层次扫描结束。同理可对B_C_T集分配教室得集合B_C_T_R。

最后将B_C_T_R集与上课时间做Cartison积。设每周有5个工作日，每天最多可以安排5个单元的课程(尽可能排在1～3单元)。当B_C_T_R集中的所有元素都安排了上课时间，则生成最终的课程表。算法对应的流程如图3所示。在排课的整个过程中，始终伴随着元素的层次扫描和元素从旧集合到新集合的迁移。这样的迁移保证了所有元素都会被使用且只使用一次。因此避免了排课过程中的撞课问题。

2.5图论模型的计算机算法

在这里给出匹配问题的算法和目前较为流行的指派问题的c++源程序，以便为日后的编程工作提供参考。

根据上述理论,设G=,V={v1,v2,…,vn},E={e1n,e2n,…,em}，记N(vi)表示与v1相邻的结点集，λ(vi)=c表示vi所着颜色为c，得到匹配问题的算法如下：

step1：任给初始匹配M；

step 2：若M饱和，则V1结束,否则转step 3；

step 3：在V1中找一非M饱和点x，置S={x},T=φ；

step 4：若N(S)=T，则停止，否则任选一点y∈N(S)-T；step 5：若y为M饱和点，转step 6，否则作求一条从x到y的M可增广路P，置M=M⊕P，转step2；

step 6：由于y是M饱和点，故M中有一边{y,u}，置S=S∪{u}，T=T∪{y}，转step4。

匹配问题的算法流程如图4所示。

3　结　论

课表的安排是排课问题的难点。它不仅要考虑到教室和教师的冲突问题，还要考虑到分段上课、单双周上课的资源合理利用问题。针对这一问

图3　算法流程

图4　匹配问题的算法流程

题，专门对原有的图论和运筹中的模型进行了改进，通过实例演示，无论从资源利用率、学生上下课转移量，还是排课速度上都取得了满意的效果。按此算法，软件一旦开发成功，可同时解决各高校以课程安排为中心的选课系统、成绩管理、教学检查等教务管理信息化建设中的种种问题。

[1]GoseE,JohnsonbaughR,JostS.Patternrecognitionandimageanalysis[M].Berlin：Springer，2013.

[2]王念桥，姚四改.基于改进粒子群优化算法的排课问题[J].计算机应用，2013，33(1):207-210.

[3]柯广利.基于优先选择算法的中职排课系统设计与实现[J].常州工学院学报,2014,27(1):43-46.

[4]王杨,丁向东,郭敏.基于提高学生学习效率的排课模型[J].科技信息,2014(2):54-55.

[5]王仲华,卢娇丽.图论在高校排课问题中的应用研究[J].太原师范学院学报：自然科学版,2010,9(1):39-42.

[6]王维宏.高校学分制教学管理体制下课表编排探析[J].沈阳工程学院学报:社会科学版,2006,2(4):540-541.

(责任编辑张凯校对佟金锴魏静敏)

MathematicalModelsforCourseScheduling

CUIYan,WANGQuan,WANGKang,CHEYu-jun

(SchoolofInformationEngineering,ShenyangInstituteofEngineering,Shenyang110136,LiaoningProvince)

Twomathematicmodelsforthecoursesarrangement,whichiseasilyprogrammedbycomputer,wereestablishedwithcartisontheoryandbipartitegraphtheory.Themodelssolvedtheschooltimetableconflictbyhierarchicalscanningthematched4setsofthestudents,courses,teachersandclassrooms.

cartesianproduct;levelscan;edgecoloring;bipartitegraph

2015-12-30

辽宁省自然科学基金项目(2015020020)；辽宁省社会科学规划基金项目(L15BGL035)；辽宁省教育厅一般项目(L2014514)；沈阳工程学院博士启动项目(LGBS-1401)；沈阳工程学院2014年大学生创新项目(201411632068)

崔妍(1982-)，女，辽宁沈阳人，讲师,博士,主要从事智能计算方法方面的研究。

10.13888/j.cnki.jsie(ns).2016.03.018

TP301.6

A

1673-1603(2016)03-0276-03