課程表的空間模型及排課演算法分析的教育論文
課程表的空間模型及排課演算法分析的教育論文
摘 要 本文在課程表問題分析的基礎上，建立了課程表的空間數學模型，並據此模型推出排課演算法，建立了排課系統的E-R圖，描述了採用軟體實現排課的計算過程。
關鍵字 排課演算法 數學模型 E-R圖
1 引言
隨著計算機的普及，如何利用軟體系統來進行課程編排，是各個高校面臨的問題。目前已經有一些比較成熟的排課軟體，其大部分作為教務管理系統的一個子系統存在，其排課演算法和資料採集效率及排課效率都各不相同，各有特點。高校課程表排課設計因素多和結構複雜被歸結為NPC(Nondeterministic Poly-nominal Complexity)問題。本文在文獻[2]提出的課程表的向量空間的概念基礎上，進一步完善設計及演算法，並實現一個更具體可行的排課過程。
2 排課問題描述
課程表的問題，是解決教師、課程、班級、教室、時間的組合問題，這個問題的數學描述是給定一組學生S(S1，S2，……Si)，一組課程C (C1，C2，……Cj)，一組教師T (T1，T2，……Tk)，一組教室R (R1，R2，……Rm)，一個時間序列N(N1，N2，……Nn)，問題的求解目的是找出這些序列的每個元素之間的一一對應關係，其中這些元素的組合要滿足一定的對應關係。諸如：①S-C 之間的對應關係；②T-C 之間的對應關係；③R-C 之間的對應關係；④T-N 之間的對應關係；⑤S-N 之間的對應關係；這些對應關係是主要考慮的限制條件，還有一些次要的限制條件。這是一個複雜的NPC問題，它的求解是一個完整類的求解問題。 在文獻[2]中使用代數的向量空間的概念，將S，C，T，N，R 中每個組中的每一個元素的組合用5 維空間的點來表示，合併S和C為一個維度，合併N和R為一個緯度，可得3維空間點陣。本文引入教學任務概念，如圖1所示，本文進一步將空間點陣細化，明確具體開課點在空間上的交點來源及含義。在T，C，S對應的平面上的點定義為教學任務1（C1，S1，W1，T1），C，S座標上對應的點是班級排課序列，空間點P1，P2即為求的開課的時間和地點。
3 排課問題求解方法
根據圖1描述空間點情況，排課問題的解就是空間中對應的交點P1，P2等。求解過程如下：
(1)確定CS軸上的點：此過程就是給班級排課，某班（S）上某門課程（C），在什麼型別的.教室上課（O），每週幾課時（V），開課時間（開課週數，如單週開課、雙週開課、5~10周開課等）（Y）。
(2)確定NR軸上的點：此過程為列出所有可用教室。此軸上應該列出每節（N）所有可用的教室資源（R），此外，每個教室對應有教室型別（O）。
(3)確定T軸上的點：此軸上列出所有的教師資源（T）。
(4)確定TCS平面上的點：此過程就是安排教學任務，也就是教師任課選擇。
(5)尋找TCSNR空間上的點：此過程就是排課，根據教學任務列出的教室型別，查詢符合條件的NR上的點，從而完成排課。
在排課求解過程中，潛在幾個約束必須要滿足：
(1) 一個班級在某一節課時只能在一個地點上課；如得到P1前，必須檢查S1在N1時刻是否已經存在一個交點。
(2) 一個教師在某一節課時只能在一個地點上課；如得到P1前，必須檢查T1在N1時刻是否已經存在一個交點。
(3) 一個地點在某一節課時只能有一個教學任務；如得到P1前，必須檢查N1R1是否已經存在交點，合班教學除外。
(4) 一個地點的座位數是否大於上課學生總數；如得到P1前，必須檢查R1座位數是否大於S1。
4 資料庫建模
根據對排課問題的求解方法，定義資料庫E-R圖，如圖2所示。在此E-R模型中，教學任務的定義十分重要，在此將教學任務的主要屬性都列出，教學任務主要屬性有班級、課程、教師、開課周、周課時、上課所需教室型別等。在設計中，開課周用20個字元來表示是否安排教學計劃（前提為學期教學周定義為20周，若學期教學周為18周，則用18個字元），若某周安排上課，則對應字元為1，否則為0，如：某課程在一學期每週都安排上課，則字串為“11111 11111 11111 11111”，某課程在一學期只有單週安排上課，則字串為“10101010101010101010”，某課程在一學期只有雙週安排上課，則字串為“01010101010101010101”，某課程在一學期第5到10周安排上課，則字串為“00001111110000000000”，依此類推。此外，教學任務對於合班上課的處理可以虛擬為一條教學任務，這樣可在排課過程中保持教學任務與教室、時間的一一對應關係。
5 排課過程
排課遵循排課問題求解方法所描述過程，首先是教學任務資料的採集，採用Web模式，各教學部門首先對於班級排課，然後對於教師排課，然後選擇上課場地型別，並且選擇對應的周學時，從而生成教學任務。採用此方式，降低教務部門的壓力，各系的教學任務由個系自己提交完成，然後教務處稽核，通過後即可進行排課任務。 排課程式採用VC程式實現，排課過程採用自動排課和手動調課結合的方式，自動排課具體方法就是將教學任務安排到時間與地點構成的點上，並同時檢查是否同時滿足約束4個約束條件，如果滿足，則教學任務安排上課完畢，並對於教學任務做已安排標記；否則，繼續下一個時間與地點構成的點並檢查約束。手動排課對於自動排課不完或者不合理的地方進行手動調整，使課程表更加合理。排課過程需要按照一定的順序進行，即對於教學任務中要求的資源相對短缺的先進行計算排課，對於一般要求或者資源相對充裕的後排課，這就要求排課前必須先對於全部資源和教學任務進行計算，由程式來統計出上課需求資源和實際資源，從而進行優先級別排序，依順序進行排課。 排課過程中需要考慮的特殊問題的處理：
(1) 上大課（合班上課）的處理，合班上課會違反第(3)個約束，因此對於合班上課首先將其教學任務合併。
(2) 公共選修課的處理：全校範圍內選修某門課程，根據學生選修情況分班，該分班結果為虛擬班級，然後對虛擬班級排課，此外，控制選修課程在固定的時間範圍開設，以免違反第(2)個約束。
(3) 雙肩挑教師上課時間的處理：對於雙肩挑教師，設定某一時間段統一不排課。
(4) 雙職工教師上課時間的處理：處於人性化考慮，屬於此類教師，3、4節不能同時排課。
6 結束語
本文描述了課程表的空間點陣模型及排課演算法，另外給出了課程表的E-R圖，可以據此順利實現一個排課系統，具有較高的實用價值。本文所描述的演算法已經對於1500條實際教學任務的學校進行了2個學期的排課，結果比較理想，因此具有一定的實用性，此外對於課程表排好後，採用Web方式釋出，隨時隨地可以查詢和列印，方便快捷。
參考文獻
[1]潘以鋒.高校智慧排課系統的演算法[J].上海師範大學學報(自然科學版)，2006，(10)
[2]花鵬飛.課程表問題的數學分析[J].中國科技論文線上
[3]李增智等.課程表問題的一種混合型模擬退火演算法[J].西安交通大學學報，Vo.l37，No 4（2003）
[4]郭方銘等.採用增強學習演算法的排課模型[J].計算機工程與設計，Vol.24，No11（2003）
[5]陶滔等.多維衝突在排課演算法中的應用[J].華東地質學院學報，Vol.24，No 3 (2001)