基于智能规划与矩阵运算的智能排课系统设计

2022-09-11

高校排课是一项非常复杂而艰巨的任务。关于高校排课算法的研究一直是一个热点问题。如何在现有教室资源和教师资源的情况下合理的完成高校的课表安排。本文提出了一种基于智能规划和矩阵运算的排课算法, 该算法先对课程与时间进行规划, 然后运用矩阵的运算实现自动排课。

1 排课问题的描述

高校排课问题就是将高校中所有班级某个学期的课程通过一定的方法, 在合理的时间将他们安排在合理的教室中。以上情况中涉及到5个主要元素:班级 (bj) 、课程 (kh) 、教师 (tc) 、教室 (js) 、时间 (tm) 。他们之间存在一定的关系与约束。关系: (1) 一个班级可以上n (n≥1) 门课程。 (2) 一门课程可以有一个或多个教师授课, 一门课程可以安排在一个或多个时间段, 一门课程可以安排在一个教室里 (该课程一星期只上一次课) , 也可以安排在不同教室里 (该课程一星期上多次课) 。 (3) 一个教师可以上一门或多门课程。 (4) 一个教室可以安排一门或多门课程。约束: (1) 一个班级在某个时间段只能上一门课程。 (2) 一名教师在某个时间段只能上一门课程。 (3) 一个教室在某个时间段只能安排一门课程。

2 算法的设计

智能排课是一个非常复杂的系统, 目前比较流行的基于图论的算法、利用人工智能的遗传算法、蚁群算法等。但由于这些算法存在着思路复杂、开发难度大、优化不确切等问题;因而, 软件除具有各自的一些优点外, 还不同程度地存在一些问题, 例如, 排课效率低下、排出的课程不够合理、缺乏完整性、通用性、且受多种条件的限制等。而本文的使用的算法实现简单、效率高、排出课表较合理。基本不需要太多改动, 学生和教师都能接受。

2.1 智能规划

(1) 课程规划:把需要智能排课的课程按等级进行分类, 分成0~N个等级, 其中0是有特殊要求的教师, 智能排课前已经用手动排课排定。智能排课中是不需要排的。1~N是要智能排课的, 数字越小等级越高 (专业课程1>必修课程2>选修课程3) 。 (2) 时间规划:高校上课时间段一般是2节或者3节。这样我们可以把一周时间按以上规则分成T块, 并定义一个等级 (0~N) 。0是不能排课的时间段。数字越低等级越高, 比如星期一的1~2节我们就可以定义为等级1, 而星期五的7~8节可以定义成最低的N级。并在每一块标上周次、起止节次、上课节数、上课长度、等级等信息存入一个二维数组中。 (3) 教室资源规划:同样把教室资源按照以上规则进行分类, 等级高的教室可以先用, 等级最低的教室在最后使用。这样等级高的课程优先排课, 优先享用好的时间与教室资源。排出来的课表就比较合理。

2.2 基于矩阵运算的空时间查找

如果规定每周的教学日是从周一到周五共5天, 每天一共上12节课 (上午5节、下午4节、晚上3节) 。其总共的教学时间段可以用一个5×12的二进制矩阵进行表示, 即Xij (1≤i≤5, 1≤j≤12) (i表示周一到周五, j表示1天中上课节次) , 在矩阵中, 1元素的位置表示没有安排课程, 0元素的位置表示安排了课程。

矩阵算法转换如下:

Sub KSJ (X) ‘X为参数是一个二维数组, 即Xij

X (i, j) =1‘初始化时每个时间段都为1

End Sub

有了这个矩阵的定义, 我们就可以表示出班级的空时间矩阵KSJ_BJij, 教师的空时间矩阵KSJ_TCij, 教室的空时间矩阵KSJ_JSij。当我们需要为某一门课程进行时间分配时我们就只需要找出这些矩阵的交集就可以。课程空时间集KSJ_KHij=KSJ_TCij∩KSJ_JSij∩KSJ_BJij。

班级、教师、教室矩阵转换算法如下 (班级、教师、教室的算法一样, 这里只列举班级矩阵算法, 教师、教室算法类推) :

Call KSJ (X) '先初始化班级的可以排课的空时间情况

F i n d_k c'该班级课表中已经排课的时间

Do While Not Find_kc.EOF'依次查询班级课表的时间

skzc=Find_kc.skzc'某一门课程的上课周次

skjc1=Find_kc.skjc1'某一门课程的起始节次

skjc2=Find_kc.skjc2'某一门课程的结束节次

X (skzc, i) =0'设置班级矩阵0表示该时间安排了课程

矩阵交集的算法:

X (i, j) =X1 (i, j) And X2 (i, j) ‘每个相同位置的元素进行与运算

End Function

课程空时间的矩阵算法:

End Function

有了以上时间矩阵的表示, 为寻找课程空余时间带来了很大的方便, 当我们找到了空余时间后得到的其实是一个二进制矩阵。在排课中我们还必须把这个矩阵再转化为高校对应的可以排课的时间块。即前面我们规划中定义的T块。

3 结语

自动排课是一个繁琐而复杂的过程, 本文运用智能规划和矩阵运算的简洁性, 将一个多元关系、多约束条件的复杂系统分解成几个简单系统的组合, 运用矩阵运算判断繁琐的排课冲突, 简化了系统和程序的设计过程。结果表明, 该算法能高效、快速、优化地实现自动排课。由于在实际编排课表过程中, 涉及更多的限制条件, 均可以利用智能规划的思想, 先将课程集合按优先级的高低顺序进行排列, 以尽可能地减少冲突发生的次数, 从而提高排课效率。

摘要：为解决目前高校自动排课系统设计复杂、排课效率低的问题, 提出了一种基于智能规划和矩阵运算的排课算法。该算法能高效、快速、优化地实现自动排课, 并简化了程序的复杂性。

关键词：自动排课,智能规划,智能排课