民辦高校排課系統算法的研究與設計

西安歐亞學院基礎部 仲崇麗

引言

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

綜合分析當前的排課系統軟件，大多采用傳統方法進行程序設計，把程序作為系統核心。系統中所使用的排課數據主要考慮了一般性排課原則，對于不同學校的特點考慮不足，并且數據與程序結合過于緊密，程序的修改維護有很大難度，不便于系統擴充和升級，因此限制了系統的通用性，對特殊情形只能依賴于人工調整。

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

1.自動排課的原則描述

1.1 基本原則

在課程的編排過程中應遵循一定的規則，只有按照基本規則來編排，才能夠減少沖突的發生并滿足各種要求，這些基本原則主要有：

（1）同一班級的學生在同一時間段（必修課時段），只能安排一門課程。

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

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

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

（5）某一課程參加學習的總人數，不能大于所安排教室的座位數。

1.2 模糊原則

結合實際情況，為了使編排的課表更加優化、合理，排課時還應該考慮以下模糊原則：

（1）優先安排全校公共基礎課程；

（2）優先安排低年級的課程；

（3）優先安排兼職教師的課程；

（4）對于一周內有兩次或三次課的多學時課程，在時間安排上盡量隔天；

（5）同一個教學任務的不同節次盡量安排在同一個教室；

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

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

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

2.基于面向對象思想的數據結構分析

在該算法中我們設立五個操作實體：課程、班級、教師、教室和時間。每個實體都對應一種數據結構，即五種新的類型為：Class Class_Course；Class Class_Class；Class Class_Teacher；Class Class_Room；Class Class_Time。

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

（2）班級類型包含3個屬性：班級ID號、班級名稱、可用時間。可用時間主要是用來在排課過程中檢驗該班級在上課時間上的沖突，因為，同一個班級上的課程不能排在同一時間段。

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

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

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

3.數據庫設計

3.1 范式模型

排課系統需要應用課程、教室、教師、班級等信息，為用戶輸出求解結論即排好的課表。數據庫即為上述信息的載體。數據庫的設計是以規范化理論為基礎進行的，要想設計一個好的關系，必須使關系滿足一定約束條件，此約束已經形成了規范，分成幾個等級，一級比一級要求得嚴格。這使得在今后的應用開發中便于進行選擇、投影、連接等運算；在方便用戶方面，也避免了冗余及數據庫管理維護方面可能發生的一些異常現象。

·第一范式（1NF）：如果關系R的所有屬性都是不可再分的數據項，則稱R屬于第一范式，記作R∈1NF。

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

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

圖4-1 排課系統的E－R模型

圖5-1 系統登錄窗口

3.2 概念模型

在使用關系型數據庫管理系統設計開發時，首先進行概念結構的設計，概念結構可以充分反映現實世界中實體之間的聯系。排課系統的E－R模型如圖4-1所示。

其中各實體類型的屬性如下：

教師（教師編號，姓名，教研室編號，所授課程編號，教師類別）

課程（課程編號，課程名稱，總學時，課程類別，需用教室類別）

班級（班級編號，學生人數，所在院系，專用教室）

教室（教室編號，教學樓號，座位數，教室類別）

4.用戶界面設計

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

排課系統的各個功能是通過選擇主窗口中的菜單命令來完成的，每個功能模塊有一個或多個菜單命令與其相對應，并以對話框方式展現其功能。

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

1）系統登錄

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

2）基本信息維護

該菜單中包括“授課任務”、“教室信息”、“教師信息”、“班級信息”、“課程信息”等命令，以完成基本信息的維護。授課任務菜單命令打開授課任務信息表管理模塊，對排課系統算法所用的數據進行管理，包括課程號，教師號，班級號，房間號，每周課時等。

3）排課管理

該菜單包括“排課”、“瀏覽課表”兩項命令。排課菜單命令運行排課算法，對后臺數據庫中的數據進行分析，排課，最后以相應的格式輸出一個可行的課程表。瀏覽課表菜單命令對當前已經完成好的授課表進行瀏覽，但在瀏覽狀態下不能修改編輯課程表。

4.2 登錄窗口的設計

由于此應用程序采用的是基于單文檔的開發，因此用戶可通過主窗口的菜單來調用各個相應的功能窗體。其中用戶單擊系統登錄菜單中的登錄命令，可以打開用戶登錄對話框，如圖5-1所示。

輸入正確的用戶名和密碼后，菜單中所有功能都變為有效，用戶可以進行相應的操作。

結束語

面向對象的軟件開發方法是現代軟件工程的一個新興也是很有發展前途的方法，本文采用了面向對象技術對排課系統進行分析、設計，并應用建模語言對需求做出全面分析，最終得到面向對象的系統模型，成功的解決了需求提出的問題。

[1]陸峰,李新.自動排課系統算法的設計與實現[J].微機發展,2005,15(11):61-63.

[2]許潔.基于信息管理的高校排課系統[J].江蘇科技大學學報(社會科學版),2006,6(2).

[3]袁鵬飛,孫軍安.SQL Sever 2000數據庫系統管理[M].北京:人民郵電出版社,2001.

[4]傅清祥,王曉東.算法與數據結構(第2版)[M].北京:電子工業出版社,2001.