高校智能排课系统的算法设计

摘要：以教学任务为基本单位，在计算教学任务排课优先级的基础上，对教学任务的时间和教室的安排均采用优化资源查找的算法，对课程变法的算法进行了设计，降低了排课过程中产生错误的几率。

关键词：课程编排；优先；算法

中图分类号：TP301 文献标识码：A 文章编号：1001-828X（2013）03-0-01

一、引言

课程编排在高等学校教务管理中是一项非常重要并且繁重的工作，通常来说，其主要实质就是对下学期开设的各门课程合理地分配时间和教室资源的过程。涉及到教室、教师、学生和时间等各方面因素，其中人为要求的因素也比较多。由于近多年的高校扩招直接导致教室的（包含多媒体教室、机房等）资源非常紧张，上述诸多的因素增加了课程编排工作的难度。若编排课表完全由人工来做，不仅费时费力，而且其科学性、准确性、方便性更是难以保证，所以利用计算机程序进行自动排课非常快捷方便。

二、问题的描述

排课最大的难点是对时间的安排，另外受到教学场地的要求、教师时间的冲突、特殊教师（机房、多媒体教室、实验室）等因素的制约，并且学校的近几年扩招，导致师资力量薄弱，一位教师要带多个班级的课程，造成教师上课的时间冲突，上述原因导致总的排课任务量很大。手工编排方法一直是限制学院教务系统发展的一大难题，虽然市面上也有众多的排课软件能解决排课问题，但是从实施的角度看，采购软件成本与自行开发的成本几乎持平。因为在实际应用中，若没有软件的核心源代码，很难适应学院教学工作的高速发展与变化的需要。

（1）自然班与教学班。综合考虑到我国高等院校普遍存在合班上课的情况，及仅仅依赖自然班进行教学存在的诸多缺陷，本系统同时引入教学班和自然班的概念，自然班定义为传统意义上的班级，教学班定义为多个班级一起上大课的班级，一个教学班可以包含一个系部或多个系部的一个甚至多个自然班。例如，机电工程系班级分别为1125786班和1125787班的两个自然班合上计算机基础课程，则称1125786班和1125787班共同组成了计算机基础的一个教学班，此教学班号被定义为计算机基础教学1班。

（2）教学任务、时空片与时间片。某一门课程所对应的每个教学班则称为一个教学任务，每个周次编排课程的每个节次称为一个时间片，时间片是个三元组（星期几、周次、节次）。课程的任务时间片和其对应上课的地点统称为时空片。在现实情况下，高等学校每个学期各门课程的起止周并不完全一样，所以要把时间片直接精确到某一周，例如1125786班2—9周需上“计算机基础”课程，10—18周需上“高等数学”课程，假如这两门课的其它上课条件的要求全部相同，那么可以将这两门课都安排在一周内的同一时间段，例前8周上“计算机基础”课程，后8周上“高等数学”课程。假如时间片没有直接精确到周次，仅仅是个二元组 （星期几、节次），就无法做到这一点，则无法充分利用时间资源。另外，在课程编排的过程中的基本单位为教学任务。

排课系统必须要满足下面几个基本条件：①在每个教学场中的同一个时间片段只能有一个教学任务。②每位任课教师在同一个时间片段中只能有唯一的教学任务。③每个班级在同一个时间片段只能有唯一的教学任务。④同一天不能安排属于同一门课程的不同课元。⑤若课元教学对教学场地大小及其功能有特殊要求的，必须要满足其最低需求。⑥同一班级相近的两个课元所选择的教学场地距离应该足够近，以确保学生能在下个课元上课开始之前到达教学场地。⑦同一教师连续的两个课元所选择教学场地的距离应该足够近，以确保教师能在下个课元上课开始之前到达教学场地。

在满足上述基本条件的前提下，该系统应该尽量满足教学任务的优化安排需要，以便课程的安排尽可能的科学、合理。对于同一课程的多个课元时间要间隔均匀，而教学场地要尽可能相同。

三、课程编排的算法设计

我院每学期的教学任务约为700多个，为减少课程编排的复杂性，因此在排课过程中设计规范、合理的顺序尤为重要。故需要先设置教学任务的优先级别，而教学任务的优先级与教学任务的属性是相同的所以是静态的。智能排课根据各系部教学秘书的积累的排课方式，设计出教学任务的优先级表达方式如下：

排课优先级=年级优先度（1位）+ 指定教学楼（0或1）+指定教室（0或1） +指定教室类型（0或1）+指定时间（0或1） +核心课程（0或1） +考试课（0或1）+必修课（0/1） +任务复杂度（4位）。

说明：

（1）所列的7个因素其后后括号的数值为该因素的取值，若“否”，则取“0”， 若“是”，则取“1”，（2）年级优先度=年级号（依据模糊原则）。（3）任务复杂度=该教师完成的教学任务总数*该教学任务的自然班总数*周学时。（4）教学任务的排课优先级的表达式中“+”号不是算术中的直接相加，而是上述九个因素值的连接。然后最终计算出的优先级一共为12位。例如一个教学任务的排课优先级情况为：指定教学楼、指定教室、未指定教室类型、指定时间、不为核心课程、考察课、必修课、一年级、任务的复杂度为30，根据公式所得出的教学任务的排课优先级则为“110100140030”。

根据上述公式计算完教学任务的排课优先级后，再将教学任务以优先级降序排列进行排序，然后，根据此顺序进行课程的编排。

因为每个教学任务可用的教室与时间片都不可能唯一，所以为了尽可能避免出现死锁，则通过动态计算教室的优先级与等待分配的时间片进行合理分配资源。在选择时间时，从教学记录中查找包含任课教师和自然班的在一周内最空闲的一天。在选择教室时，在教学记录中查找符合要求的最小容纳量，且时间最空闲的教室。这样可以保证对每个教学任务分配的教室和时间片都是相对于当前可用的资源集合中最优化的，从而使整个排课结果都是优化的。

四、结束语

排课系统具有相当特殊的复杂性，如何进一步对算法进行丰富、修正，充分利用计算机最新发展技术，设计出更适合我国高校实际情况的算法，是本人日后将要开展的进一步工作。

作者简介：胡静静（1982-），女，安徽淮南人，现任淮北职业技术学院计算机系讲师。