课程安排问题的数学模型及评价方法x27

1、第15卷第4期I99B年 11月Vokl5.No.4Nov. 1998贵州大学学报(自然科学版)Journal of Guizhou University( Natural Science)课程安排问题的数学模型及评价方法驾道云_（贵恍大学计算机科学系550025）q俗牛0223摘 要 本文建立了课程安排问题的数学模型.给出了课程安排优劣的童化评 价方法.关键词一课程安您 敛学楼弩 逊方法中图分為&2扌-1问题的引入课程安排是通常教学任务安排中的常见问题，到目前为止都是手工进行，即使某些单位 使用计算机排课，也仅仅是在人工干预下，安排好后打印机输出而已，并未对这-问题作出 过科学分析.

2、其实，这个看似简单的问题，却涉及到资源合理分配、多任务交叉安排、冲突 协调及组合优化等问题.是一个较为复杂的数学问題，在一般的课程安排中，涉及如下冋题：（1）资源集合（即教师集合）；某教师餡上哪些课程，所上每门课程的效果.（2）任务集合（即课程集合）：某门课哪些教师能讲授，上课的效果（3；刈象集合（即班级集合）：栗班级开课时间、课程、每门课的重复次数.（4）时间表的约束：当划定排课时间（如一周按丘天，每天按四个时间段：上午2次、下午1次、晚间1次）后，有些时间是不能排课的（如政治学习时 何、固定公共课时间等）.（5）时间安排与上课效果的关系.（6）约東条件： 同一教师在不同班级上课时间不能冲突

3、、 同一班级中，同一课程重复多次时，每相邻的两次课的时间间隔要求. 每个教师开课数目相对平均. 排课次数不能多于容许安排的时间次数.（7）课程安排合理性的评价手段.收黏斎学廉喘馥资助课题第4期许道云：课程安排问题的数学模型一及评价方法 265 2数学模型针对上述问题，町以用如下数学模型来描述排课问题2.1 T矩阵（刻划教师资源库）T= （qhxn其中：OMqMlq： i教卿上j课程的评价指标2.2 C矩阵（刻划排课结果，即课程表）C = （c/lod其中：Cy = < Cl , C2 >G： 0到m的一个正整数；0列“的一个正整数；G,第i天的第j时间段，由G教师上Q课程；记x （

4、cy） =G,y （cQ =c2.2.3 W矩阵（刻划排课时间与上课效果）W=（VV”）,其中：OMwjMl眄八第i天第j时间段的上课效果指标.2.4 C矩阵序列（刻划多个班级排课结果）C，C，cp（C,叽C严 VC（, Cj> q = l, 2, ,Pc/c：第q个班，第i天的第j时间段，由G教师上G课程；2.5 S矩阵（刻划排课时间与具体课程上课效果）S-（说）2其中：OMs”Ml司：i课程在第j时间段的上课效果指标.2.6 B矩阵（刻划课程总体安排）B二（b（j）pxn英中：b”为0或一个正整数木学期i班级j课程每周排课次数.2.7初始条件2.7.1 初始化C矩阵序列初始化C（q）

5、= （C絆）3q=l, 2,，pc2> = <1, 0>：第q个班级，第i天的第j时间段不能排课 4q>=<ci. c2>=<0, 0>：第q个班级，第i天的第j时间段可以排课2.7.2 初始化B矩阵2.7.3 初始化T矩阵、W矩阵、S矩阵2.8约束条件2.8.1对C矩阵的内部约束（a）初始化C矩阵序列后的不能排课的时间段上不能排课.（b）同一班级同一课程的时间间隔要求殆广 二啦其中：r为重复次数第4期许道云：课程安排问题的数学模型一及评价方法 269 r=bqy（ <：'>）（后兰<iJ条件：hMiw-LW"

6、即相同谍程的相邻两次的时间间隔（如：可以取h = 2, 12 = 3, 也可以用平均值k/r作参照）.（bl）同一班级同一课程的时间安排总体要求（如不能都安排在F午）t SlJo>r * a其中：0<a<l（如：取 a=0.7）2.8.2 对C矩阵间的外部约束（同一教师不能在不同班级的同一时间上课） = <c 1，c，2>,cj = <c, c2>当qHq时，c'iHc）2.83师数，iU =本学期开课数，INT （x）为取整函数.INT （nl/m） M每个教师开深数MINT （nl/m） + 12.9目标函数2.9.1 单目标函数（一个班级

7、课程安排的评价）maxZ - max 三斗叫 *2.9.2多目标函数（几个班级课程安排的总体评价）maxZ = max虫盘抽八虫）“）'饲3评价方法（以单个班级为例）3d建立教师资源库根据本教学单位教师及开设课程.以及以往教师上课记录制定教师资源库.即确定W 矩阵.格式如下：（此外m =8, n7）程01234567000000000100-950.90.80000.«20050003000.70.800.850.90400.80.900.7000.9500.7000.60.90060Q0.950.800.70.707000.950.70.8000.8800

8、00.90.9500-70.73.2时间表初始设置即初化C矩阵.星V段12341<OtO><0,0><0.0><1,0>2<0.0><0>0><0»0><1,0>3<0,0><0.0><0.0><1,0>4<0.0><0.0><0»0><E0>5<0,0><0,0><hO><1.0>3.3上课效果时间表设置即确定W矩阵.星V段期、1

9、234t10.90.850.9210.90.850.9310.90 850.9410.90.850.9510.8课程与上课时间的效果设置 即确定S矩阵.1234110.850.80.8210.850.80.8310.850.80.8410.850.80.8510.850.70.7610.850-80.8710. 850.70.7第4期许道云*课程安排问题的数学模型及评价方法 271 3.5确定排课方案即确定B矩阵班閉程号级、112345671203->0223.6条件限制由于仅有一个班级，故只考虑 间RS条件几“一兰3单科分布条件：SS,*0.8 G为重复次数）】*

10、M教师均匀分布条件：INT8）M每个敎师开课数MINT8） + 1<2.3><3,6>< L0>5<3,6><8,4><0,0>< 1,0><2.3><1.0><1,0>38安排方案的评价结果54Z- 气号严 &= 1*0.9*1+0.9*0.95 *1 + 0. 85 » 0.9*0.85Z值越大，方案越好.3.9最佳方案对应的评价结果maxZ =巾词百严。-（屮叫心*少4算法设计本文提供了一种排课问题的量化评价方法，当班级不多的情况下，很容易得到冋题的最优 解.在班级较多，任务交叉比较复杂的情况F,可以使用贪心算法得到冋题的一个近似较优解.参考文献1许国志尊运绅学 北凉：濟华大学岀版社.19882张益新尊 算法引论北京，国防科技大学出版社,1983A Mathematics Model and Estimate Methodabout Course ArrangementXu Dayun(Deparanent of Computer Science. Guizhou Universicy. Guiyang 550025)Abstract This paper presents a m