民辦高校排課系統(tǒng)算法的研究與設(shè)計(jì)

西安歐亞學(xué)院基礎(chǔ)部 仲崇麗

引言

課程表是學(xué)校開展教學(xué)活動(dòng)的指令性文件。在傳統(tǒng)方式下，課表編排主要是靠手工完成的，排課人員需要花費(fèi)大量的時(shí)間和精力，并且容易出錯(cuò)，同時(shí)手工操作也不能滿足資源需求的經(jīng)常變化。利用計(jì)算機(jī)進(jìn)行自動(dòng)排課，不但能使教務(wù)人員從繁雜的排課任務(wù)中解脫出來，提高教務(wù)管理工作效率，而且能改善教學(xué)管理質(zhì)量，合理、高效地利用有限的教學(xué)資源。

綜合分析當(dāng)前的排課系統(tǒng)軟件，大多采用傳統(tǒng)方法進(jìn)行程序設(shè)計(jì)，把程序作為系統(tǒng)核心。系統(tǒng)中所使用的排課數(shù)據(jù)主要考慮了一般性排課原則，對(duì)于不同學(xué)校的特點(diǎn)考慮不足，并且數(shù)據(jù)與程序結(jié)合過于緊密，程序的修改維護(hù)有很大難度，不便于系統(tǒng)擴(kuò)充和升級(jí)，因此限制了系統(tǒng)的通用性，對(duì)特殊情形只能依賴于人工調(diào)整。

民辦高校聘有很多兼職老師，而兼職老師提供的上課時(shí)間是固定了的，所以課表編排問題不僅涉及教師、教室、學(xué)生、課程，更有教學(xué)時(shí)間等多種因素的組合規(guī)劃，具有規(guī)模大、約束條件復(fù)雜以及不斷變化等特點(diǎn)，是當(dāng)今計(jì)算機(jī)科學(xué)研究的熱點(diǎn)問題之一。

1.自動(dòng)排課的原則描述

1.1 基本原則

在課程的編排過程中應(yīng)遵循一定的規(guī)則，只有按照基本規(guī)則來編排，才能夠減少?zèng)_突的發(fā)生并滿足各種要求，這些基本原則主要有：

（1）同一班級(jí)的學(xué)生在同一時(shí)間段（必修課時(shí)段），只能安排一門課程。

（2）同一教師在同一時(shí)間段，最多只能安排一門課程。

（3）同一教室在同一時(shí)間段，只能安排一門課程。

（4）同一時(shí)間安排的課程總數(shù)，不能大于所能提供的教室總數(shù)。

（5）某一課程參加學(xué)習(xí)的總?cè)藬?shù)，不能大于所安排教室的座位數(shù)。

1.2 模糊原則

結(jié)合實(shí)際情況，為了使編排的課表更加優(yōu)化、合理，排課時(shí)還應(yīng)該考慮以下模糊原則：

（1）優(yōu)先安排全校公共基礎(chǔ)課程；

（2）優(yōu)先安排低年級(jí)的課程；

（3）優(yōu)先安排兼職教師的課程；

（4）對(duì)于一周內(nèi)有兩次或三次課的多學(xué)時(shí)課程，在時(shí)間安排上盡量隔天；

（5）同一個(gè)教學(xué)任務(wù)的不同節(jié)次盡量安排在同一個(gè)教室；

（6）同一自然班的課程盡量安排在固定的教室；

（7）同一教師所上的課程盡量安排在固定的教室；

（8）同一門課程盡量安排在固定的教室。

2.基于面向?qū)ο笏枷氲臄?shù)據(jù)結(jié)構(gòu)分析

在該算法中我們?cè)O(shè)立五個(gè)操作實(shí)體：課程、班級(jí)、教師、教室和時(shí)間。每個(gè)實(shí)體都對(duì)應(yīng)一種數(shù)據(jù)結(jié)構(gòu)，即五種新的類型為：Class Class_Course；Class Class_Class；Class Class_Teacher；Class Class_Room；Class Class_Time。

（1）課程類型包含7種屬性：課程ID號(hào)、課程名稱、上課的班級(jí)鏈表、任課教師、單次課時(shí)數(shù)、可用教室鏈表、可用時(shí)間。由于有的課程一周要上多次，因此在進(jìn)行排課之前，我們會(huì)將這類課程從基本數(shù)據(jù)中篩選出來進(jìn)行復(fù)制，一周要上幾次就存在幾個(gè)實(shí)例，并分配不同的單次課時(shí)數(shù)。這樣的課程將有相同的課程ID號(hào)和相同的課程名稱，在排課過程中將盡量將它們安排在同一個(gè)教室，并在時(shí)間上有一定的間隔。

（2）班級(jí)類型包含3個(gè)屬性：班級(jí)ID號(hào)、班級(jí)名稱、可用時(shí)間。可用時(shí)間主要是用來在排課過程中檢驗(yàn)該班級(jí)在上課時(shí)間上的沖突，因?yàn)?，同一個(gè)班級(jí)上的課程不能排在同一時(shí)間段。

（3）教師類型包含3個(gè)屬性：教師ID號(hào)、姓名、可用時(shí)間。對(duì)于排課系統(tǒng)來講，教師情況的多樣性對(duì)排課結(jié)果影響也是很大的。例如，兼職教師的上課時(shí)間是有限的。因此必須為每位教師建立自己的可用時(shí)間，同時(shí)和班級(jí)的可用時(shí)間相同。

（4）教室類型包含3個(gè)屬性：教室ID號(hào)、教室名稱、可用時(shí)間。同樣，教室作為教學(xué)資源也有它的可用時(shí)間。至于某一個(gè)課程是否適合安排在該教室上課，或該教室是否能容納上課的所有學(xué)生的問題，可以通過操作人員在進(jìn)行基本數(shù)據(jù)錄入的過程中屏蔽掉。

（5）時(shí)間類型是本算法中最重要的一個(gè)類型，以上四種類型中的可用時(shí)間實(shí)際上都是該類型的一個(gè)實(shí)例。該類型實(shí)際上就是一個(gè)矩陣，行數(shù)為7，代表一周有7天，列數(shù)由操作人員設(shè)定，為該學(xué)期每天上課的總課時(shí)數(shù)，設(shè)定為Shared類型。當(dāng)該課時(shí)可用時(shí)，置為O；不可用時(shí)，置為1；在虛擬排課階段，如果該課時(shí)被占用，則置為2。其中還包含三個(gè)全局變量：上午總課時(shí)、下午總課時(shí)、晚上總課時(shí)。

3.數(shù)據(jù)庫(kù)設(shè)計(jì)

3.1 范式模型

排課系統(tǒng)需要應(yīng)用課程、教室、教師、班級(jí)等信息，為用戶輸出求解結(jié)論即排好的課表。數(shù)據(jù)庫(kù)即為上述信息的載體。數(shù)據(jù)庫(kù)的設(shè)計(jì)是以規(guī)范化理論為基礎(chǔ)進(jìn)行的，要想設(shè)計(jì)一個(gè)好的關(guān)系，必須使關(guān)系滿足一定約束條件，此約束已經(jīng)形成了規(guī)范，分成幾個(gè)等級(jí)，一級(jí)比一級(jí)要求得嚴(yán)格。這使得在今后的應(yīng)用開發(fā)中便于進(jìn)行選擇、投影、連接等運(yùn)算；在方便用戶方面，也避免了冗余及數(shù)據(jù)庫(kù)管理維護(hù)方面可能發(fā)生的一些異?，F(xiàn)象。

·第一范式（1NF）：如果關(guān)系R的所有屬性都是不可再分的數(shù)據(jù)項(xiàng)，則稱R屬于第一范式，記作R∈1NF。

·第二范式（2NF）：如果關(guān)系R∈1NF，且它的每一非主屬性都完全依賴于主鍵，則稱R屬于第二范式，記作R∈2NF。

·第三范式（3NF）：如果關(guān)系R∈2NF，且它的每一非主屬性都不傳遞依賴于關(guān)鍵字，則稱R屬于第三范式。

圖4-1 排課系統(tǒng)的E－R模型

圖5-1 系統(tǒng)登錄窗口

3.2 概念模型

在使用關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng)設(shè)計(jì)開發(fā)時(shí)，首先進(jìn)行概念結(jié)構(gòu)的設(shè)計(jì)，概念結(jié)構(gòu)可以充分反映現(xiàn)實(shí)世界中實(shí)體之間的聯(lián)系。排課系統(tǒng)的E－R模型如圖4-1所示。

其中各實(shí)體類型的屬性如下：

教師（教師編號(hào)，姓名，教研室編號(hào)，所授課程編號(hào)，教師類別）

課程（課程編號(hào)，課程名稱，總學(xué)時(shí)，課程類別，需用教室類別）

班級(jí)（班級(jí)編號(hào)，學(xué)生人數(shù)，所在院系，專用教室）

教室（教室編號(hào)，教學(xué)樓號(hào)，座位數(shù)，教室類別）

4.用戶界面設(shè)計(jì)

4.1 建立程序主界面——菜單

排課系統(tǒng)的各個(gè)功能是通過選擇主窗口中的菜單命令來完成的，每個(gè)功能模塊有一個(gè)或多個(gè)菜單命令與其相對(duì)應(yīng)，并以對(duì)話框方式展現(xiàn)其功能。

本系統(tǒng)在主窗口上放置了7個(gè)菜單，其分別用來完成不同的模塊功能，下面是幾個(gè)主要菜單所完成的功能：

1）系統(tǒng)登錄

該菜單包括的菜單命令有“登錄”、“修改口令”、“退出”。登錄命令能夠讓用戶以合法的身份登錄系統(tǒng)，完成不同權(quán)限的操作。退出命令能夠讓用戶退出當(dāng)前的用戶狀態(tài)，從而避免數(shù)據(jù)被他人竊取。修改口令命令能夠讓用戶在合法登錄狀態(tài)下，確保提供自己的原口令后才能修改自己當(dāng)前的密碼。

2）基本信息維護(hù)

該菜單中包括“授課任務(wù)”、“教室信息”、“教師信息”、“班級(jí)信息”、“課程信息”等命令，以完成基本信息的維護(hù)。授課任務(wù)菜單命令打開授課任務(wù)信息表管理模塊，對(duì)排課系統(tǒng)算法所用的數(shù)據(jù)進(jìn)行管理，包括課程號(hào)，教師號(hào)，班級(jí)號(hào)，房間號(hào)，每周課時(shí)等。

3）排課管理

該菜單包括“排課”、“瀏覽課表”兩項(xiàng)命令。排課菜單命令運(yùn)行排課算法，對(duì)后臺(tái)數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行分析，排課，最后以相應(yīng)的格式輸出一個(gè)可行的課程表。瀏覽課表菜單命令對(duì)當(dāng)前已經(jīng)完成好的授課表進(jìn)行瀏覽，但在瀏覽狀態(tài)下不能修改編輯課程表。

4.2 登錄窗口的設(shè)計(jì)

由于此應(yīng)用程序采用的是基于單文檔的開發(fā)，因此用戶可通過主窗口的菜單來調(diào)用各個(gè)相應(yīng)的功能窗體。其中用戶單擊系統(tǒng)登錄菜單中的登錄命令，可以打開用戶登錄對(duì)話框，如圖5-1所示。

輸入正確的用戶名和密碼后，菜單中所有功能都變?yōu)橛行?，用戶可以進(jìn)行相應(yīng)的操作。

結(jié)束語

面向?qū)ο蟮能浖_發(fā)方法是現(xiàn)代軟件工程的一個(gè)新興也是很有發(fā)展前途的方法，本文采用了面向?qū)ο蠹夹g(shù)對(duì)排課系統(tǒng)進(jìn)行分析、設(shè)計(jì)，并應(yīng)用建模語言對(duì)需求做出全面分析，最終得到面向?qū)ο蟮南到y(tǒng)模型，成功的解決了需求提出的問題。

[1]陸峰,李新.自動(dòng)排課系統(tǒng)算法的設(shè)計(jì)與實(shí)現(xiàn)[J].微機(jī)發(fā)展,2005,15(11):61-63.

[2]許潔.基于信息管理的高校排課系統(tǒng)[J].江蘇科技大學(xué)學(xué)報(bào)(社會(huì)科學(xué)版),2006,6(2).

[3]袁鵬飛,孫軍安.SQL Sever 2000數(shù)據(jù)庫(kù)系統(tǒng)管理[M].北京:人民郵電出版社,2001.

[4]傅清祥,王曉東.算法與數(shù)據(jù)結(jié)構(gòu)(第2版)[M].北京:電子工業(yè)出版社,2001.