基于关联规则算法的排课系统设计与实现

摘 要:为达到教学资源利用的最优化,在分析高校排课需求及目前排课系统现状的基础上,基于 FP_Growth关联规则算法,设计和实现基于C/S模式的高校自动排课系统。该系统实现课表的自动生成、动态调整,解决了教务部门的迫切需要。

关键词:排课系统;FP_Growth算法;资源冲突;C/S模式

中图分类号:TP311文献标识码:A

文章编号:1004-373X(2010)02-060-05

Design and Implementation of Online Course Arrangement System

Based on Association Rule Algorithm

ZHANG Jian′an,YANG Xuejun,WU Wenyi

(Kunming Branch of Electronic Technology,Institute PLA Information Engineering University,Kunming,650231,China)

Abstract:In order to achieve the optimization of teaching resources usage,on the basis of analysing class demands of university and the present situation of course arrangement system,based on FP_Growth association rule algorithm,C/S pattern_based university automatic course arrangement system is designed and realized.This system realizes class schedule automatic production,dynamic alignment,the educational administration department′s urgent need is solved.

Keywords:course arrangement system;FP_Growth algorithm;resource conflict;C/S mode

0 引 言

随着高校扩招力度的加大,目前高等院校中普遍存在着学生基数大、专业设置多而教学资源(教师、场地、器材等)有限的瓶颈问题。加之高校课程设置的特殊性和复杂性,使得人工调配资源生成课表的工作量大,且难以做到资源利用最优化。而现有的排课系统大多功能单一,且主要面向中小学,不适应高校的复杂需求。随着高校校园网络的普及,利用校园网资源,开发面向高校、自动调配教学资源的智能排课系统已迫在眉睫,对于促进教学管理科学化、降低劳动强度、实现教学资源最大效益具有重大的意义[1]。

1 排课问题分析

1.1 排课问题的规则分析

实用的课表编排应是符合教学计划和任务安排的,满足教室资源、时间、空间以及一些特殊要求的,并让学生和教师满意的。因此,对于学期课表的编排需要遵循的原则可分为如下几类[2]:

(1) 正确性。要求所排课表准确无误地反映出每个班级各门课程及任课教师的上课时间和教室,满足以下基本要求:

① 一个班(教师或教室)不能安排同时上两门课;

② 合班上同一课程的不同班级应安排相同时间、相同教室上该门课;

③ 一个班级分若干个小班上某门课程应安排在相同时间;

④ 一个班(如分班则指小班)的一门课只安排一个教室,且学生人数不得超过教室的容量。

(2) 合理性。要求所排课表符合教学规律,有利于学生有效地学习知识,以保证教学质量,主要表现在:

① 一个班级的课表是均匀的,首先在每周内每天上课的课时数是均匀,其次整个学期每周安排的课时数也应基本相等;

② 每门课程的时间安排均匀的,在一周内两次课之间的间隔应基本相等,每周该课的上课时间也应基本稳定;

③ 一些难度较大的重要课程一般安排在上午。

(3) 适用性。对由于不确定因素影响而提出的要求应尽量给与满足:

① 为了教学上的要求需要某一些班级的某一课程安排在相同时间上课,即所谓同步上课;

② 有时需要某课程安排在每周的指定时间或指定的每次内;

③ 有时需要某教师(或某教室)只被安排在每周指定时间或指定的周次内上课。

(4) 限制性。根据不同要求,其课程安排和使用不很相同:

① 教师在某一时间段不能上课时,不要安排课程;

② 教师与系统管理员的权限的分配要不同。

1.2 排课算法研究

排课问题早在20世纪70年代就证明是一个NP完全问题,即排课算法的计算时间是呈指数增长的,这一论断确立了排课问题的理论深度[3]。

目前,解决排课问题的方法有:遗传算法、贪心算法、蚁群算法、回溯算法、FP_Growth关联规则算法等[4]。

1.3 FP_Growth关联规则算法

1.3.1 算法框架描述

该系统由以下几个主要的过程组成:

(1) 系统数据初始化,形成本期教学信息二维数据库;(包含数据属性、条件属性及信息编码等)。

procedure Tzypneoform1.firststep_initialize (sender:object)

(2) 课程定位,按照预排算法,形成无任何决策信息的课表样本视图。

procedure Tzypneoform1.secondstep_orient station(sender:object)

(3) 按构建规则对课表样本库进行课表混排。

procedure Tzypneoform1.thirdstep_pred eject (sender:object)

(4) 用FP_growth 算法定位课表混排库中出现的冲突。

procedure Tzypneoform1.forthstep_trans(sender:object)

(5) 按优先处理冲突计数值最高元素的原则消除冲突。

procedure Tzypneoform1.fifthstep_collies ion(sender:object)

(6) 系统综合检测原始信息和约束条件,输出结果。

procedure Tzypneoform1.sixthstep_inspect(sender:object)

1.3.2 算法描述

排课问题是典型的资源调度问题,该问题已被证明为一个NP完全问题。由于排课调度算法涉及到教室、教师、班级、课程和时间等信息对象,要满足各种约束关系,需实现合理的资源分配,所以具有相当的难度[5]。这里认为:虽然排定课表问题及其复杂,但可以采用一种分而治之的观点来看待它。将其分为两个不同的部分,分阶段来解决它。即将排课算法分为两个子算法:按权均值算法排定基本课表;通过建立冲突树对资源冲突进行处理算法。

(1) 基本课表的排定。设“可安排教学时间集”为H,“班级集”为S(|S|=ns),“教师集”为T,“课程集”为L(|L|=nk),“场地集”为R。

对于每个班级Si(教师t∈T),有一个“未排定时间集”A(Si)H(A(t)H);对于每门课程有一个可安排时间集A(l)H(集合中含nk个元素),对于每一个门课程有一个场地集r(l)R(其包含有nk个元素),并且对于每一个四元组(Si,t,l,r)∈S×T×L×R,有一个“要求教学时间数目”X(Si,t,l,r)∈Z+0(Z+0表示非负整数集)。且X(Si,t,l,r)A(l)。要排定课表,即求函数f(Si,t,l,r,h){0,1}(其中f(Si,t,l,r,h)=1表示班级Si,教师t,在时间h内,场地r上课程l)。

课表排定应满足:

① 给定Si时,第一门课程排定时应满足:hi∈H(在整个教学时间内抽取随机时间点)。取li∈L使得A(li)=max{A(l)}在整个A(Si)=H内使f(Si,t,l,r,h)=1。以后课程的排定则循环:lj(j≠i),A(lj)=max{A(l)-A(li)}(每排出一门课程lm,A(lj)为原{A(l)}除去已排课程A(lm))。在A(Si)=H-A(li)(每排出一门课程lm,A(Si)为原H除去A(lm))中使f(Si,t,l,r,h)=1,直至A(Si)=0,其中f(Si,t,l,r,h)=1仅需Si∈S,t∈T,l∈L,h∈H,r∈R。

② 对于i∈[1,ns],Si依次循环步骤①,直至A(Si)=0(i∈[1,ns])。

(2) 资源冲突的处理。按权均值算法,使得每个班级排定课表更自动,高效。但由于制约条件多,各班级初次混排的课表中按权均值算法并没有解决资源冲突问题。该系统采用了第二个子算法对该问题进行处理:查找和定位课表中的冲突元素,对冲突元素按其冲突次数值降序排列,并将各个班级的冲突元素集生成相应的冲突树,再对树进行遍历查找,按照冲突最高的元素优先处理原则进行处理,直至冲突树的节点为空。即采用FP_growth关联规则思想,使得该系统能高效,正确排出满足所有约束条件的课表,使算法更具智能化[6]。

输入:混排课表数据库D。

输出:以冲突计数值降序排列的冲突元素集。

方法:

① 扫描数据库D,查找冲突元素Cij并计数(这里的下标用于对冲突元素C定位);按冲突计数值降序排列冲突元素存入L表中;

L={C11,C12,…,Cij,…,Cnm}

(2) 创建FP_tree的根节点标记为null,对每一个班级的课表执行如下操作:

依据L中的冲突元素及其顺序对每个班课表中的Cij作选择和排序操作;

形成各班课表的冲突元素集Tran=a|A。这里的a是Tran中的第一个元素,A是Tran的剩余部分;

调用insert_tree(a|A,Tran)过程将Tran中的元素加入到FP_tree中。如果Tran中有一个分枝N它的节点名与a相同,则对N的计数值加1,否则为Tran创建一个新的分枝N,该N中各节点的计数值为1;

如果A非空,再次调用insert_tree(A,N)过程处理。

与遗传算法、蚁群算法等相比,FP_Growth算法是所有搜索算法中最为基本的一种算法,相对比较简单些,且较适于开发该高校排课的实际要求,所以本排课系统选择FP_Growth算法[7]。

采用具有智能概念的FP_Growth算法思想设计的按权均值随机排课算法方案,比常规的递归排序方法设计的方案效率提高近10倍,显著提高了系统效率。

2 系统设计与实现

2.1 模块划分

该系统由应用程序服务器、客户端程序、远程数据库、数据库引擎BDE四部分组成。系统在Delphi 开发平台上编制,采用Borland公司BDE数据库驱动引擎,Paradox数据库,基于DCOM+和MIDAS技术,实现多层分布式体系结构。其体系结构图如图1所示,客户端程序结构框图如图2所示。

图1 排课系统体系结构

图2 客户端程序结构框图

(1) 应用程序服务器。应用程序服务器主要提供远程数据模块,其中封装有所有的数据表。客户端程序通过DCOM接口组件与之相联。远程数据模块还提供了数据表中数据的维护功能,尽可能减小客户端,以形成“瘦客户”。

(2) 客户端程序。客户端程序又分为系统功能模块、代码维护模块、课表排定模块、课表查询模块、课表生成模块及系统帮助模块。客户端程序主要实现对高校复杂课表的自动排定、调整、查询及课表的自动生成和打印、辅助信息管理等。软件设置用户身份管理模块,用户身份等级分为系统管理员、普通级和最低级,各级用户有不同的操作权限。

2.2 数据结构

2.2.1 数据库结构

该系统建立了一个数据库,所有具体的数据项都以表的形式存放在该数据库中。这些表中包括:班级信息表、教师信息表、课程信息表、教室信息表、时间模式表,还有两个代码表分别记录教师和课程、班级课程和周课时量[8]。如图3所示。

图3 层次结构图

2.2.2 数据类型实体及属性

(1) 数据模型实体。系统中包含的数据模型实体主要有:班级、课程、教室、教师。

(2) 实体属性

① 班级:班级编号、班级人数、所属专业、所属年级。

② 课程:课程编号、课程名称、课程性质、考查方式、学分、总学时、周学时。

③ 教师:教师编号、教师姓名、教师所属教研室、教师简介、周课时量。

④ 教室:教室编号、教室名称、教室类型、教室容量。

(3) 数据字典及数据表的构造。基本信息设置需要10个数据表,有班级信息表、上课时间表、课程信息表教师信息表、教室信息表、教研室信息录入表、管理员表、用户表、两个代码表分别记录教师与课程和教室与课程[9]。

① 班级信息表:存放全校各班级的基本情况,见表1所示。

表1 班级信息表

字段名称数据类型说明

ID自动编号班级编号

CID文本班级号

GRADE文本年级

PROFESSION文本专业

NLJM数字人数

定义:班级信息表 = 班级编号+班级号+人数+专业+年级

② 上课时间表:用来存放上课的时间模式,如表2所示。

定义:上课时间表=星期+节数

表2 上课时间表

字段名称数据类型说明

DAY文本星期

TIME数字节数

③ 课程信息表:存放所有课程和与之相应的属性,如表3所示。

定义:课程信息表=课程编号+课程名+专业+课程简介+课程类别+周课时+电算化标志

表3 课程信息表

字段名称数据类型 说明

CID文本课程编号

COURSE_NAME文本课程名称

COURSE INTRO文本课程简介

PROFESSION文本专业

TYPE数字课程类别

W EEKNUM数字周课时量

ELECTRONIC数字电算化标志

④ 教师信息表:存放全校教师的基本情况,如表4所示。

定义:教师信息表=教师编号+教师姓名+教师简介+已安排完课时量+教研

表4 教师信息表

字段名称数据类型说明

ID文本教师编号

NAME文本教师姓名

INTRODUCTION文本教师简介

OFFICE文本教研室

hasassign数字已安排完课时量

⑤ 教室信息表:存放全校所有教室的基本信息,如表5所示。

定义:教室信息表=教室编号+房间号+教室容量+是否电算化+占用标志

表5 教室信息表

字段名称数据类型说明

RID文本教室编号

RNAME文本房间号

CONTAIN数字教室容量

TYPE是/否是表示有电算化,否表示无

TAKE_UP是/否是表示占用,否表示无

⑥ 教师和课程代码表:用来记录教师所教课程,如表6所示。

定义:教师和课程代码表=编号+教师编号+课程编号+教师名称+课程名称

表6 教师和课程代码表

字段名称数据类型说明

ID自动编号编号

TID文本教师编号

CID文本课程编号

tname文本教师名称

cname文本课程名称

⑦ 班级和课程代码表:用来记录每个班级所要上的课程,如表7所示。

定义:班级和课程代码表=编号+班级编号+课程编号+已安排完课程标志+班级+课程

表7 班级和课程代码表

字段名称数据类型说明

ID1自动编号编号

CID文本课程编号

ID文本班级编号

hasassign数字已安排完课程标志

class文本班级

course文本课程

⑧ 管理员表:用来存放管理员的名称、口令。该表通过设置管理员的密码实现系统功能设计中分角色设计。不同的用户具有不同的权限级别,不同的级别则应对应不同的操作内容,如表8所示。

定义:管理员表=管理员编号+管理员用户名+密码

表8 管理员表

字段名称数据类型说明

ID自动编号管理员编号

NAME文本管理员用户名

MIMA文本密码

⑨ 教研室信息录入表:用来存放全校不同的教研室的信息的,如表9所示。

表9 教研室信息录入表

字段名称数据类型说明

ID自动编号教研室编号

NAME文本教研室名称

INTRODUCTION文本教研室简介

定义:教研室信息录入表=教研室编号+教研室名称+教研室简介

⑩ 用户表:用来设置用户的不同权限,如表10所示。

定义:用户表=编号+用户名+密码

表10 用户表

字段名称数据类型说明

ID自动编号编号

NAME文本用户名

MIMA文本密码

2.2.3 数据表之间的关系

数据库完整性规则的目的就是保证数据的一致性,正确性和符合业务规则。它主要包括四个方面:实体完整性、值域完整性、引用完整性和用户定义完整性。为了防止数据冗余,数据库的数据表中不包含所有需要的信息的,有些信息可以通过表之间的关系从其他的表中获得。出于这种考虑,在该系统的数据库设计中,主要建立如图4所示数据表之间的关系,并通过设置关键字将这些表联系在一起[10]。

3 结 语

基于C/S工作模型实现的自动排课系统,实现了大专院校教务部门的自动排课、动态调整和集中管理。系统功能全面完善,运行稳定可靠,操作简单易行,符合高校教务部门实际工作需求,极大地减轻了教务人员的劳动强度,实现了教务管理工作的自动化,达到了资源配置最优化的目标。

图4 数据表之间关系图

参考文献

[1]徐华成.管理信息系统\.北京:清华大学出版社,2006.

[2]吴金荣.关于大学课程表问题的研究[J].运筹与管理,2002,11(6):66_71.

[3]王能斌,钱祥根.大学课表调度系统――UTSS\.计算机学报,1984(5):383_389.

[4]吴志斌,陈淑珍,孙晓安.回溯算法与计算机智能排课[J].计算机工程,1999(3):792_801.

[5]高尚,杨静宇.群智能算法及其应用[M].北京:中国水利水电出版社,2006.

[6]傅清祥,王晓东.算法与数据结构[M].2版.北京:电子工业出版社,1996.

[7]周培德.算法设计与分析[M].北京:机械工业出版社,1996.

[8]萨师煊.数据库系统概论\.北京:高等教育出版社,1996.

[9]马小军,陈小宁.数据库实用技术\.北京:电子工业出版社,1994.

[10]Joseph J Bambara.SQL Server 开发指南\.牛力,译.北京:电子工业出版社,2000.