对学分制模式下排课系统的探讨

邹元杰

【摘要】排课问题是一个多约束、多目标的优化问题，本文通过对排课因素和约束条件的深入分析，对学分制模式下的排课系统的设计提供合理的模型建立。

【关键词】学分制模式 排课系统

一、前言

目前高校招生逐年扩张，学生人数不断增加，再加上大多数高校实行学分制，课程开设逐渐向着广度和深度扩展，但学校的教学资源及设备却得不到及时补充，这些都给教务处排课人员造成很大的压力。单纯采用劳动强度大、效率低的手工排课，已成为提高教学管理质量的瓶颈。随着计算机在教学工作中的普及应用，利用计算机进行自动排课已经成为一个重要的研究课题。

二、排课因素分析

排课工作是教学工作顺利进行的基础工作，排课问题涉及到的因素也几乎是全校性的。从排课可能引起的冲突的角度来考虑，排课涉及到的因素如下：

（1）时间因素。在排课问题中涉及到的时间因素主要有学年、学期、周、天、时段、节次等。一般我们按照周课表来上课，从开学第一周到第N周，高校每学期上课18周。一周上课天数M≤7，一般学校一周上课5天。每天上午下午晚上各分两个时间段（片），每个时间段两节课。这样一周有30个时间段。

（2）课程因素。课程有课程编号、课程名称、课程的周学时、课程学分、课程对教室类型的要求、所属学院等。每门课程可以有指定的老师授课，也可以没有。课程因素还包括开设的班级数及课程开设的校区等。

（3）教室因素。每个教室都有教室编号，教室代号及所属的教学区域。每个教室都有教室类型，教室类型包括普通教室、多媒体教室、语音教室、实验室、机房、体育馆等。每个教室都有一定的容量，教室的容量必须不小于上课的人数。

（4）教师因素。每个教师都有自己的编号及姓名，每个教师都隶属于一个学院，教师可以对上课时间提出自己的特殊要求。同一时间老师只能上一个教学班的课。

（5）班级因素。本文所涉及的班级均指的是教学班（选课班或行政班）。如前面的分析，教務处下达的教学任务书里规定了开设的课程名称、班别、开设的校区等。其中课程名称，班别，校区编号唯一决定一个选课班。每个选课班都有一个的最大选课人数的限制。

三、排课的约束条件

排课问题中，主要任务是将班级、教师、课程安排在一周内某一不发生冲突的时间和教室，保证课表在时间的分配上符合一切共性（时间上不存在冲突）和个性（不与老师的特殊时间要求冲突）的要求，在此基础上，使其安排在各个目标上尽量达到最优。

一张可行的课表首先要满足排课因素的约束。这里的约束条件主要是避免冲突。只有在满足全部约束条件和避免所有冲突的基础上，才能保证整个教学计划合理正常进行。对教师、班级、课程、时间、教室等几部分资源进行最优化配置，才能保证排课的顺利完成以及充分发挥各个资源的优势以达到提高管理水平和教学质量的目的。

根据是否必须满足，我们可以将约束条件分为硬约束和软约束。硬约束是指教师、班级、教室、校区在时空概念上发生了不可能发生的事情，也就是发生了冲突。它是在排课过程中需要满足的最基本的约束条件，是排课时必须遵循的原则，否则将会导致排课结果无意义。软约束则是指排课过程中若满足则更佳，不能满足也不影响教学的开展的约束条件。它能够使课表更加合理，更加具有人性化、，它影响排课结果的好坏。

通常，排课方案的标准有多个，以下是按照一般高校校情制定的约束条件。

（1）硬性约束条件：①同一时间同一班级只能上一门课；②同一时间同一教室只能上一门课；③同一时间同一教师只能上一门课；④教室的容量必须不小于或等于实际上课的人数；⑤所分配的教室类型必须与课程所要求的教室类型一致；⑥课程必须安排在教学任务书所规定的校区。

（2）软性约束条件：①每个时间段安排的课程数尽量均匀；② 一周的课表中每个上课时间都有一定的优度，尽量将课程安排在优度高的时间段；③一门课程的多次上课的时间尽量间隔并分布均匀；④教室容量适中，以充分利用教室；

四、排课系统中的算法设计

（一）教室调度算法

教室信息表用来记录教室编号、类型、容量。为了使教室资源得到最好的利用，在排课之前，先利用排序函数对教室信息表按教室容量进行升序排序。在为课程分配教室时，从教室信息表的第一条记录开始检索，从小到大依次匹配，匹配成功则返回该教室编号。这样可以减少教室的浪费，除非没有小教室，只有大教室。教室调度算法具体描述如下：①初始化i=0，countfalse=0（记录失败次数）；②判断i是否小于该校区教室的总数，若不小于则结束，没有找到要求的教室，提示错误；③判断第i个教室的教室类型、容量是否符合要求，若不符合，转⑥；④判断countfalse是否小于50，若小于，判断当前时间下，该教室是否可用；若可用，转⑤；否则重新产生一个可用的时间（该时间老师没有安排课程），countfalse=countfalse+1，转④；⑤判断教室已占用的时间段数目是否小于20，若小于，则教室i在该时间段被分配且重置countfalse=0；否则转⑥；⑥i=i+1，转②。

该算法可以有效避免一次判断时，某时间段一个教室不可用则该教室不可用的判断，在尝试50次后如果该教室仍不可用，则我们可以认为该教室基本上在每个时间段都被安排了课，则选择下一个教室。同时，一个教室可用，但是这个教室在30个时间段中已经安排了20或更多个时间段，则说明该教室已经负荷很重，若再给这个教室安排课程，很容易出现教室利用的冲突。为了避免这种情况的发生，如果某教室被安排的时间段超过20，则我们不再为该教室安排课程。

（二）冲突检测算法

在初始化课表时，产生的每一个课表均是满足所有硬性约束的可行课表。但是在进行交叉操作室，我们交换交叉点处两个课程的上课时间，其他不变。这样可能造成同一时间同一教师只能上一门课的约束。所以这里的冲突检测函数只要检测同一时间同一教师是否只上一门课。

①初始化i=0；②判断i是否小于课程总数，是则结束，没有冲突；③初始化j=i+1；④判断j是否小于课程总数，若不小于，则转⑧；⑤比较课程i与课程j的教师是否相同，相同则转⑦；⑥j=j+1，转④；⑦判断课程i与课程j的时间片是否有相同的，有则结束，返回冲突；⑧i=i+1，转②。