基于层次分析法的自动排课课程优先级模型

王俊生 戴云龙

【摘要】该文在分析了影响排课效果的非技术性因素基础上,提出了一个自动排课的课程优先级计算模型,并通过层次分析法确定了各影响因素的权重和取值。通过实验证明,该文模型可以提高自动排课系统的排课效果。

【关键词】自动排课;课程优先;AHP;教学管理

【中图分类号】G420 【文献标识码】B 【论文编号】1009—8097(2009)11—0032—04

排课是高校教学运行管理中的一个重要环节,课表安排是否合理直接关系到学校教学工作的有序性和稳定性。自动排课系统就是在教师、教室和时间这3大资源数量有限,约束不同的条件下,由计算机根据一定的算法,合理安排班级的课程,使得学生和教师获得较为合理的上课时间和空间,是一个多目标的调度问题,在运筹学中被称为时间表问题(Timetable Problem,简称TTP)。随着高校学分制教学管理的不断深入及招生规模的不断扩大,排课过程中的矛盾也凸显出来,如何合理高效地完成课表的安排成为学校教学管理人员关注的一个重点问题。

对自动排课系统产生影响的因素有两类,一类为技术因素,主要指排课模型、排课算法对排课效果的制约;另一类为非技术性因素,主要指排课过程中,教学计划、课程学分学时、教师、教室等非技术性因素对排课效果的制约。近几年,我国有很多学者对自动排课进行了探讨,热点集中在对排课算法的研究及排课整体模式的构建,即技术因素上,例如将人工智能算法如遗传算法[1-2]、禁忌搜索算法[3]运用到排课系统中,取得了不错的效果。而对课程本身性质对排课的影响讨论较少。合班是否合理是影响排课效果的因素之一,郭俊柏[4]等建立合班的数学模型,且通过非线性规划的方法求解,得出了课程和班级较少情况下的较为合理的合班状态,但对高校排课中合班的复杂的实际情况是否实用还待验证。陆如秋[5]分析排课过程中的基本要素主要有教学计划、教师、教室、学生及时间,比较全面,但却没有对如何将这些基本要素运用到自动排课中提出合理的建议。本文正是基于此,分析非技术性因素对排课系统的影响,且提出了将非技术性因素应用到实际自动排课系统中的方案,实践证明可以获得较为理想的排课结果。

一 非技术性因素对排课的影响

排课系统是一个由教学计划维护、教学进程编排、下达教学任务、教学任务审核、开课任务维护、预排课表、排定课表、手工课表调整等流程组成,是由教务处和二级学院共同完成的一项复杂的系统工作,只有分析了各个环节中非技术性因素的影响,才能排定出合理的课表。

1教学计划。教学计划规定了各个专业的课程及其各学期课程的分布情况,是安排教学进程、落实教学任务的基础性文件,具有一定的稳定性和权威性,它对排课效果的影响是明显的。教学计划中课程分为必修课、限选课和任选课,一般来说必修课应该被优先安排,获得较好的上课时间,其次是限选课和任选课。课程具有学分和学时性质,一般一个学分为16-18学时,从排课效果来说大学分和大学时的课程应该被优先安排。

2教师资源。教师资源对排课效果的影响主要体现在两个方面:教师工作量的不平衡和教师的个性化要求。当前高校教师数量存在较为不平衡现象,有的专业特别是基础课教师工作量非常大,而有的专业教师却工作量严重不足,从而对排课系统产生了较大的影响。特别是大工作量的教师的课表就较难安排,于是从排课效果的角度来说就应该优先安排。教师个性化需求的满足是高校“以人为本”的一个具体体现,在满足班级课表合理的情况下,应该考虑教师的个性化需求。

3合班问题。合班问题是困扰高校排课人员的一个难点问题,对排课的影响主要体现在两个方面:合班的方式和合班的数量。合班的方式是不同课程的合班组合方式,实践证明一般一个班级如果有3门及3门以上课程合班不同时,课表将非常难安排,安排出的课表可能会较不合理。合班的数量是指一门课程合在一起上课班级的数量,合班数量越多课表越难安排,从排课效果的角度来说合班数量多的课程应该优先安排。

4教室资源。教室资源是限制排课效果的因素之一。这里的教室包括高校的体育场地、实验室、设计教室、多媒体及非多媒体教室等用于教学的场所。一般高校中体育场体、实验室及多媒体教室比较短缺,对其需求课程应该优先安排 。

5课程的时间分布。主要指课程在课表中的横向分布和纵向分布。横向分布指的课程周学时,纵向分布指课程的上课周次。相对于课程上课周次,周学时对排课的影响更大。一般周学时分为:2、3、5、6及以上学时,学时越大课程应该该被优先安排,特别是当一门课程学时大于6时,应该获得较高的优先级。

6排课时间模式。排课时间模式是一种排课时间的组合形式,分为:一般模式、单元模式、特殊模式及公选课模式等。一般模式安排周学时为2、3、5、6等学时的课程;单元模式则安排一个上午或一个下午的半天课;特殊模式根据自己的实际定义的排课时间模式;公选课模式是定义了只能安排在公选课上课时间的排课模式。一般来说,单元模式和特殊模式被优先安排,容易产生理想的排课效果。

二 自动排课课程优先级计算模型

自动排课系统中课程的安排顺序是影响排课效果的关键因素。一个班级排课顺序影响着本班课表编排的合理性;整个学校的排课顺序影响着整个学校所有班级课表合理性。为此,本文引入影响排课效果的非技术性因素,为每一个预排课程设置优先级,建立了一种课程优先级计算模型,用于决定课程被安排的顺序,优先级高的课程被优先安排。本文选取7个具有代表性的非技术性因素用于课程优先级计算模型,包括课程性质、周学时、教室类型、学分数、分班数、教师工作量及排课时间模式,用Wi表示, ,且用Ci表示第i个影响因素的具体取值,从公式(1)可以看出,影响PCF取值大小的有各影响因素权值的大小及具体取值。如何确定各影响因素的权重及取值对课程优先级的计算非常重要。

层次分析法(Analytical Hierarchy Process 简记AHP)是由美国运筹学家T.L.Satty于20世纪70年代末提出的。它是一种结合了定量与定性分析的系统分析方法,尤其在多因素系统评价的指标权重确定中应用非常广泛[6-7]。为此,本文引入AHP法,以扬州大学为例介绍课程优先级各影响因素的权重和具体取值计算过程。

1 确定各影响因素的权重

(1)层次结构模型设计

依据影响课程优先级因素分析,构建如图1所示的层次结构模型。

(2)判断矩阵构建

判断矩阵构建是层次分析法最为关键的环节。分为两步:选取专家和构建判断矩阵。选取专家的过程中,专家的学科结构和职业结构对判断矩阵的构建具有决定性的作用。为了保证判断矩阵构建的合理,选取计算机、教育及具有排课经验的专家共10人来构建判断矩阵。构建判断矩阵实际是请专家对图1中所示的所有的因素都进行俩俩比较的过程,如果分层中有n个因素,一般需要n(n-1)/2次比较,图1第二层有7个因素,故需21次比较。为了表示比较的结果,层次分析法提出了相对重要性的比例标度,两个元素相对重要性的比较可变化得到一个衡量的数。为了说明问题,现设有n个因素对目标有影响,用aij表示影响因素Bi与Bj对目标的相对重要性比例标度,则表1给出了aij值定义。

易知A为互反矩阵, aii = 1,aij =1/ aji ,i,j = 1,2, …,n 。第一行第二列值表示影响因素V1(课程性质)与V2(周学时)对评价目标排课效果影响大小进行比较,其结果3表示专家认为“课程性质比周学时略为重要”,相反第二行第一列的值就应该取1/3。第一行第四列的7表示“课程性质比学分数确实重要”, 同样第四行第一列就的值就应该为1/7。

(3)排序向量的计算与一致性检验

对判断矩阵A进行特征值λ和特征向量Wi计算,将特征向量规范化,结果见表2,P1-P10表示10个专家,W1,W2,…,W7表示各因素评价指标权重, 表示最大特征值。表2表明:各个专家对非技术性因素对课程优先级影响的观点并不完全一致,P1专家认为教室类型(W3=0.358)对排课的影响最大,而学分数(W6=0.025)影响最小;P3专家认为课程性质(W1=0.295)对排课的影响最大,而排课模式(W7=0.021)影响最小。

为了保证判断矩阵的一致性,对每个判断矩阵进行一致性检验。由矩阵理论知: 越接近影响因子数量n,得到的解(特征向量)越接近于正确的排序,所作的判断也越准确。故层次分析法引入随机一致性比率CR=CI/RI,作为评价一致性的标准,其中CI=( -n)/(n-1),RI见表3。RI在10%附近及以下时,一般认为判断矩阵是具有满意的一致,在判断矩阵较为复杂(大于7阶)的情况下,可以放到20%。否则必须调整。表2表明:P7的CR最大为9.8%,P5的CR最小为4.2%,所有判断矩阵具有满意的一致性。

(4)排序向量综合

每个专家的评价权重结果计算完毕,需计算综合评价权重。计算方法有两种:加权算数平均法及加权几何平均法(公式略)。将之规范化就可以得到综合评价权重向量。计算结果见表2,加权算数平均计算结果W算=(0.169,0.094,0.306,0.043,0.199,0.108,0.088),加权几何平均计算结果W几=(0.161,0.098,0.336,0.038,0.203,0.091,0.073),两种算法计算结果比较相近,但不完全一样。加权算数平均计算结果显示对排课影响从大到小依次为:教室类型、分班数、课程性质、教师工作量、周学时、排课时间模式及学分数。加权几何平均法计算结果则认为周学时(0.098)较教师工作量(0.091)重要,其它与加权算数平均计算的排序结果相同。教室类型被认为是制约排课结果最为重要的因素,体现出学校的实际情况:实验室、体育场、设计教室及部分校区的多媒体教室的缺乏制约了排课。合班被认为是次重要的因素,显示出我校在教学任务落实的过程中,每个课程合班数量较大,且不科学,特别是通修课程更为严重,也从侧面体现出我校现在通修课师资不够的现象。本文选择了加权几何平均法计算的结果进行下面的分析。

2 确定各影响因素的取值Ci

影响课程优先级顺序的另外一个因素就是各影响因素的具体取值Ci。我们仍然选取上面的10个专家,利用AHP法确定影响因素的具体取值,整体计算过程同上。计算结果为:C课程属性(必修课,限选课,任选课)=(0.48,0.38,0.14); C周学时(2-3,4-5,6及以上)=(0.25,0.35,0.4);C教室类型(体育场地,实验室,多媒体,非多媒体)=(0.4,0.4,0.18,0.02);C学分数(2下,2-3,4,5及以上)=(0.06,0.24,0.32,0.38);C合班数(1,2,3,4及以上)=(0.03,0.24,0.33,0.4);C教师工作量(4及以下,5-8,9-12,13及以上)=(0.05,0.15,0.35,0.45);C排课模式(一般模式,特殊模式,单元模式,公选课模式)=(0.22,0.35,0.38,0.05)。

3 实验及分析

以扬州大学2008-2009秋季学期,3307门课程,近700班级,1580教师参与排课为例进行实验。用AHP法确定了影响课程优先级多因素的权重和具体取值以后,根据公式(1)计算每门课程的优先级PCF,然后利用冒泡排序算法[8]对每门课程的PCF排序,得到所有课程的优先级排序结果。按照PCF从大到小的顺序由自动排课系统排课,结果有105门课程没有安排成功,其它课程都有了较好的排课结果,比未计算PCF之前的排课结果有(358未安排成功)较大幅度的提高。同时课程安排分布较为合理,达到计算机自动排课的目标。

三 结论

影响自动排课系统的非技术性因素主要有教学计划、教师资源、合班问题、教室资源、课程的时间分布及排课的时间模式等。文中构建了一种排课课程的优先级计算模型,并通过AHP法分析得出影响我校排课效果因素的权重和具体取值,给出AHP法的详细计算过程。各因素对排课效果的影响,从大到小的依次为:教室类型、分班数、课程性质、周学时、教师工作量、排课时间模式及学分数。体现出教室类型特别是体育场地、实验室及多媒体教室直接制约我校的自动排课系统的排课结果;分班情况是否合理也是影响排课效果的重要因素;而学分大小则对排课的效果影响较小。各影响因素的具体取值中:必修课、体育场地、学分在5以上、周学时在6及以上、合班数在4及以上,教师周工作量在13及以上及时间模式为单元模式的课程获得了较高的取值,应该被优先安排。最后通过实践证明,基于AHP的自动排课课程优先级计算模型可以有效地提高排课的效率和获得较为理想的排课效果,为自动排课系统完善提供了新的思路。

参考文献

[1] 王俊生.基于遗传算法的排课系统研究[J].中国教育信息化,2008,(9):51-53.

[2] 韦玉,冯速.免疫遗传算法在排课问题中的应用[J].北京师范大学学报,2008,(4):168-172.

[3] 丁振国,赵宏维.禁忌搜索求解排课问题的应用研究[J].微电子学与计算机,2008,(4):31-34.

[4] 郭俊柏,邢永丽.高校排课中的合班问题[J].湘潭师范学院学报,2008,(4):8-9.

[5] 陆如秋.浅谈高校学分制管理中排课的制约因素及模式[J].广西师范学院学报,2007,(10):53-55.

[6] 郭向勇,傅国强,周玉芬.基于层次分析法的网络课程学习评价模型[J].电化教育研究,2008,(3):72-76.

[7] 刑红宇. 基于AHP法和Delphi 法的网络课程评价指标体系设计研究[J].中国电化教育,2006,(9):78-81.

[8] 严蔚敏,吴伟民.数据结构[M],北京:清华大学出版社,1997.