基于關聯規則算法的排課系統設計與實現

摘 要:為達到教學資源利用的最優化，在分析高校排課需求及目前排課系統現狀的基礎上，基于 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|=ns)，“教師集”為T，“課程集”為L(|L|=nk)，“場地集”為R。

對于每個班級Si(教師t∈T)，有一個“未排定時間集”A(Si)H(A(t)H);對于每門課程有一個可安排時間集A(l)H(集合中含nk個元素)，對于每一個門課程有一個場地集r(l)R(其包含有nk個元素)，并且對于每一個四元組(Si，t，l，r)∈S×T×L×R，有一個“要求教學時間數目”X(Si，t，l，r)∈Z+0(Z+0表示非負整數集)。且X(Si，t，l，r)A(l)。要排定課表，即求函數f(Si，t，l，r，h)→{0，1}(其中f(Si，t，l，r，h)=1表示班級Si，教師t，在時間h內，場地r上課程l)。

課表排定應滿足:

① 給定Si時，第一門課程排定時應滿足:hi∈H(在整個教學時間內抽取隨機時間點)。取li∈L使得A(li)=max{A(l)}在整個A(Si)=H內使f(Si，t，l，r，h)=1。以后課程的排定則循環:lj(j≠i)，A(lj)=max{A(l)-A(li)}(每排出一門課程lm，A(lj)為原{A(l)}除去已排課程A(lm))。在A(Si)=H-A(li)(每排出一門課程lm，A(Si)為原H除去A(lm))中使f(Si，t，l，r，h)=1，直至A(Si)=0，其中f(Si，t，l，r，h)=1僅需Si∈S，t∈T，l∈L，h∈H，r∈R。

② 對于i∈[1，ns]，Si依次循環步驟①，直至A(Si)=0(i∈[1，ns])。

(2) 資源沖突的處理。按權均值算法，使得每個班級排定課表更自動，高效。但由于制約條件多，各班級初次混排的課表中按權均值算法并沒有解決資源沖突問題。該系統采用了第二個子算法對該問題進行處理:查找和定位課表中的沖突元素，對沖突元素按其沖突次數值降序排列，并將各個班級的沖突元素集生成相應的沖突樹，再對樹進行遍歷查找，按照沖突最高的元素優先處理原則進行處理，直至沖突樹的節點為空。即采用FP_growth關聯規則思想，使得該系統能高效，正確排出滿足所有約束條件的課表，使算法更具智能化[6]。

輸入:混排課表數據庫D。

輸出:以沖突計數值降序排列的沖突元素集。

方法:

① 掃描數據庫D，查找沖突元素Cij并計數(這里的下標用于對沖突元素C定位);按沖突計數值降序排列沖突元素存入L表中;

L={C11，C12，…，Cij，…，Cnm}

(2) 創建FP_tree的根節點標記為1，對每一個班級的課表執行如下操作:

依據L中的沖突元素及其順序對每個班課表中的Cij作選擇和排序操作;

形成各班課表的沖突元素集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.