獨立學院排課系統的數據庫與算法分析

摘要：排課問題是一個約束的、組合優化問題。本文結合獨立學院的實際情況，對排課系統的數據庫進行分析，提出一種適合于獨立學院教學特色的排課算法。

關鍵詞：獨立學院 排課 數據庫 算法

0 引言

高校擴招以來，全國至今已有300多所獨立學院。隨著獨立學院在校生人數的增加，教學資源緊張、師資缺乏等各種矛盾日益加劇，其中排課方面的困難逐漸暴露、突出，給獨立學院日常教學及自身發展壯大帶來了很大的困擾與壓力。科學、合理的排課是保障教學秩序正常運行的基礎，也是取得良好教學效果的關鍵因素之一，更應引起與普通高等學院相比，具有復雜、特殊教學情況的獨立學院高度重視。排課問題是一個約束的、組合優化問題，1976年，S.Even等人已經證明了排課問題是NP完全問題，目前計算機還沒有解決NP完全問題的多項式算法。因此大多數教學經費緊張的獨立學院都采取半自動排課方式，首先用排課系統進行簡單的自動排課，然后用手動方式進行優化與調整。此種排課方式耗時耗力，其效果卻差強人意，排課科學合理及資源優化很難達到。本文主要對排課系統的數據庫進行分析，并且提出了一種適合于獨立學院教學特色的排課算法。

1 數據庫分析

要了解排課的過程，首先要了解排課過程中數據表的生成。由于排課系統所涉及的數據表較多，我們這里只分析一些最基礎的表之間的關系與結構，便于我們更好的理解整個排課過程。

1.1 數據表

教師表(教師編號，姓名，職稱，學歷，學位)

班級表(班級編號，名稱，人數)

課程計劃表(課程編號，課程名字，考核方式，教師編號，班級編號)

時間表(時間編號，周，星期，節)

教室表(教室編號，教室類型，容納人數)

排課計劃表(課程編號，時間編號，教室編號)

教師課表(教師編號，姓名，課程編號，課程名字，考核方式，時間編號，教室編號)

班級課表(班級編號，名稱，課程編號，課程名字，考核方式，時間編號，教室編號)

教室課表(教室編號，教室類型，容納人數，教師編號，班級編號，時間編號)

1.2 數據表之間的關系，如圖1所示

課程計劃表，是由教學計劃生成，有一個主鍵：班級編號。兩個外鍵：教師編號、班級編號。所謂的“排課”就是給課程計劃表中的每一門課程，選一個時間，選一個教室來實施教學行為，也就是生成排課計劃表。由排課計劃表可以延伸出三張課表：教師課表、教室課表、學生課表，這三張課表才是最終實施教學計劃的最終依據。班級是指學生組成的一個集體，可以是臨時班、分班、合班、選修課班。

2 排課算法

2.1 排課過程

廣義的排課過程包括：在自動排課之前的準備工作、自動排課過程中按約束條件進行排課以及自動排課過程結束后還有手動的優化與調整工作。

狹義的排課過程是按一定的約束條件給一門課程安排一個時間和一個地點，也就是如圖1所示用課程計劃表、時間表、教室表來生成排課計劃表。這個過程是一個組合優化的過程，目前有許多排課算法，各有其優缺點。由于獨立學院學生較多、教學資源少、師資少，更使這個過程變得困難重重。最基本的約束條件有如下五點：①同一時間同一教室只能安排一門課程。②同一時間同一班級只能學習一門課程。③同一時間同一教師只能教授一門課程。④教室的類型滿足課程需要。⑤教室容量滿足班級人數需要。

除了以上五個必要約束條件，還有五個彈性約束條件：①體育課的合班上課問題。②音樂、美術等分班上課問題。③由于外聘教師較多，外聘教師對上課時間方面的要求也多，因此排課通常是先滿足外聘教師上課時間上的需求。④按課程優先級來安排上課時間，如專業課的優先級可以設為較高，應盡量安排在上午，體育課可以安排在下午。⑤需要多媒體教學、語音室、實驗室的課程應優先。⑥同一班級的同一門課程的上課時間應有一定間隔，班級課表每周要分布均勻。⑦滿足專職教師、兼職教師的特殊需求。

一個先進的算法解決彈性約束條件是在課程計劃錄入時選擇約束條件，在自動排課階段算法按照這些約束條件來執行。不依靠后續的人工優化和調整。

2.2 自動排課中的數據結構與算法

我們選擇循環隊列這種數據結構表示時間與空間，利用進程中的滑動窗口來選擇時間片段和空間片段，滑動窗口大小是根據連續上課節數來定，滑動窗口的步長是下一門課的節數。我們都知道飛機降落過后，我們會從輸送帶上面取下行李，而排課是一個反過程，是搬運員往傳送帶上面放行李，但是沒有人在取行李，放的時候只是要考慮更多的約束條件而已，搬運員會把所有的行李往上面放直到放完為止。具體抽象出來的概念如下圖2所示。此數據結構與算法的優點就是簡單形象，比普通的組合式算法效率更高。

3 結束語

本文結合獨立學院的實際情況，對排課系統的數據庫進行了分析，提出了一種適合于獨立學院教學特色的排課算法。

參考文獻：

[1]Gotlieb.The Construction of Class Teacher Time Tables[J].Proceeding IFIP Congress，Amsterdam，1963：73-74.

作者簡介：俸世洲，男，1981年出生，四川廣漢，研究實習員，碩士，主要研究方向:人工神經網絡，數據挖掘。