挤压插入式算法在排课系统中的应用研究

闫英琪，景 丽，刘淑红

（兰州城市学院，甘肃 兰州 730000）

挤压插入式算法在排课系统中的应用研究

闫英琪，景 丽，刘淑红

（兰州城市学院，甘肃 兰州 730000）

为解决西部农村地区中小学排课难问题，开发基于挤压插入式算法的排课系统，并分析排课过程中遇到的各种问题及解决方案。该排课系统有效减轻了人工排课的繁重工作，为中小学排课人员带来了很大方便。

挤压插入式算法；排课系统；中小学

笔者在参与“甘肃省网络环境建立城乡互动教师专业化能力协同发展的策略研究”项目以及在“甘肃省中小学教师信息技术能力培训内容及体系建构研究”项目实施过程中，曾调研近百所甘肃农村中小学的教学环境、教学资源及教学辅助设备。在调查教学环境时发现大多数中小学排课都是人工完成的，主要由学校教务处工作人员经过长时间的分析、统计，做出表格后通过电脑录入，不但工作量大，且非常繁琐，容易出错。各学校每学期通常要花费一个星期甚至更多时间排课，既浪费人力，也浪费时间。那么，有没有切实可行的办法解决这个问题呢？

21世纪是信息化的计算机文化时代。计算机不仅是一种信息处理工具，而且能改变人类生存方式。那么利用计算机能否为学校排课呢？在肯定计算机能够迅速且准确排课的条件下，项目组成员决定针对项目学校开发一个简单易行的排课系统。

1 系统概述

依据Windows操作系统环境，用Visual Basic 6.0软件开发工具制作排课系统[1，2]。以项目学校的课程安排为依据，按照课程要求进行排课。排课后，输出的课表如有不合理的地方，可以直接对其进行调整。

系统结构如图1，系统分为3部分：输入、排课和课表输出。其中输入部分实现本学年的课程安排，教师带课计划的输入，以及对输入数据合法性进行检查，如班主任的唯一性，每班只有一个，且必须有一个班主任；班级课程的唯一性，每班的每门课只能由一位教师教授；课时数的校验等。系统核心部分排课模块是基于挤压插入式算法，其原理是模拟人工排课，综合教师、班级与课程3者因素，按照各门课程的排课要求进行排课，之后再进行重排处理，如排出的课表不合理可以进行微调。输出部分分为屏幕输出及手工调整和打印形成文档输出2部分。系统数据流程见图2[3]。

2 挤压插入式算法设计

挤压插入式算法的总体思路是，以课程为核心，以班级为单位扫描3张课表，这3张课表均标记为“F”且符合课时要求。如果各种条件都满足，教师在这个时间点空闲，并要求教室或公用教室必须在这个课时点空闲，即不产生冲突，则在3张课表找到的课时点填上课程安排；如果产生冲突，可以扫描其他课时点，再检测冲突情况进行排课。如果最终因不能找到合适的课时点而未能安排本次课程，那么它的课时计数器将大于0，即这门课程没有排完，留到最后重排，重排的算法与第一次排课扫描插入算法相似，只是稍修改了一些地方。

具体来看，挤压插入式算法的实现，可根据对课程属性的分析划分为六大集合，以及各种课程的排课要求，将课程人为地确定优先级，也就是排课顺序。其顺序为：双周课（健康、国防、体活）、英语、作文、数学、语文讲读、公用教室课、特色课，最后为副课。优先级的确定原则：（1）几个教师同时空闲才能安排的课程优先级高，如双周课；（2）兼课多的教师的课程优先级高；（3）有特殊要求的课程优先级高；（4）外聘教师的课程优先级高；（5）涉及相关因素多的课程优先级高。

排课顺序确定后，可采取2种扫描顺序扫描课表课时点：横向扫描和纵向扫描。这2种扫描顺序可以互补。下面就横向扫描和纵向扫描作一解释。横向扫描，即每个课时点，先横向从星期一到星期五进行扫描，待扫完一轮后，再对下一个课时点进行横向扫描。纵向扫描是对每天的课时点进行纵向扫描，然后每星期隔2天或3天进行跳跃式扫描，避免同一课程连续2天有课。这里又可以分为正扫和逆扫，正扫是从上午第一节到第三节进行扫描，逆扫是从下午第七节到上午第四节进行扫描。根据不同课程的排课要求，我们对不同课程采取不同的扫描策略。双周课、体育课、公用教室课采用纵向逆扫，主课采用纵向正扫，活动课、副课使用横向扫描，以弥补纵向扫描造成中间课时空闲的不足。

最后再将那些初排未安排的课程依次抽出来，以班为单位进行横向扫描，查找合适的课时点，进行冲突检测，重排这些课程。

3 遇到的问题及解决方案

3.1 课程不能全部排完

由于课程种类繁多，且排课时间要求不一样，主次顺序也不同。所以先排的课程较容易排完，而后排的课程由于各种条件的限制很难找到适当位置，使得课程不能全部排完。

解决这一问题的方法是在课程初排后查询是否存在没有排完的课。如果有则依次扫描课表，少考虑一些冲突，没排完的课程由再排模块重新排。

3.2 课表空洞

所谓课表空洞是指课程排完后，从课表上看有的前一课时没有排课而后一课时却排了课，排出来的课不够紧凑。出现这一问题主要是因为有些课程限制了排课时间。例如语文课要排在英语和数学之后，而且2节课不能连上；课时超过5时上午和下午各排一节课；副课尽量不排在上午1、2节；公用教室课必须排在统一、指定的课时等。

解决这一问题的方法是采用不同的课表扫描方式进行排课。先排的课进行纵向扫描，后排的课进行横向扫描。由于排课时间点的限制和冲突几率的限制，纵向扫描又分为从上往下扫描和从下往上扫描方式。例如英语、数学、语文等主课采用从上往下扫描方式，而体育、音乐等冲突几率较高的课程则采用从下往上的扫描方式。后排的课程如副课则采用横向扫描方式。这样，对各种不同要求的课程采用不同课表扫描方式可以有效解决课表空洞问题。

3.3 排出的课不合理

电脑排课是人工智能排课过程的模拟，因此，排出的课不一定符合学校的具体要求或某位教师的实际要求，这也是直接影响排课有效性和实用性最关键的问题。

解决这一问题的最好方法是在课程排完后按照实际需求进行调整，就是微调。本系统的微调算法是在课表上直观调换2门课程或者将一门课程调换到课表上没有排课的地方，微调模块自动检测调课的教师有没有带课时间冲突，如果是公共教室课则要考虑公共教室使用是否有冲突，只有在没有任何冲突的前提下才能进行课程调换。微调模块有效解决了排课不合理问题，同时也大大增强了整个排课系统的实用性。

在课表上进行微调有2种情况：将2门课程进行调换和将一门课程调换到课表上没有排课的地方。

（1）2门课程之间的调换，流程见图3。

（2）将一门课调换到课表上没有排课的地方。这种调换比将2门课程进行调换更简单，只需判断带课教师有无带课时间冲突即可。

这样既能将所有课程排入课表，又能在课表上直接进行微调，达到了完全实用的目的。

[1]刘甫迎.VB教程[M].北京：电子科技大学出版社，1998.

[2]江高举.VB6.0开发人员指南[M].北京：清华大学出版社，1997.

[3]林立域.Access 97[M].北京：清华大学出版社，1999.

G43

B

1671-1246（2011）05-0043-02

甘肃省教育科学“十一五”规划课题“甘肃省中小学教师信息技术能力培训内容及体系建构研究”（GSBG[2009]GXG067）之系列研究成果