課程表的空間模型及排課算法分析

1、課程表的空間模型及排課算法分析             摘  要 本文在課程表問題分析的基礎(chǔ)上，建立了課程表的空間數(shù)學模型，并據(jù)此模型推出排課算法，建立了排課系統(tǒng)的E-R圖，描述了采用軟件實現(xiàn)排課的計算過程。   關(guān)鍵字 排課算法 數(shù)學模型 E-R圖1  引言   隨著計算機的普及，如何利用軟件系統(tǒng)來進行課程編排，是各個高校面臨的問題。目前已經(jīng)有一些比較成熟的排課軟件，其大部分作為教務管理系統(tǒng)的一個子系統(tǒng)存在，其排課

2、算法和數(shù)據(jù)采集效率及排課效率都各不相同，各有特點。高校課程表排課設(shè)計因素多和結(jié)構(gòu)復雜被歸結(jié)為NPC(Nondeterministic Poly-nominal Complexity)問題。本文在文獻提出的課程表的矢量空間的概念基礎(chǔ)上，進一步完善設(shè)計及算法，并實現(xiàn)一個更具體可行的排課過程。2  排課問題描述   課程表的問題，是解決教師、課程、班級、教室、時間的組合問題，這個問題的數(shù)學描述是給定一組學生S(S1，S2，Si)，一組課程C (C1，C2，Cj)，一組教師T (T1，T2，Tk)，一組教室R (R1，R2，Rm)，一個時間序列N(N1，N2，Nn)，問題

3、的求解目的是找出這些序列的每個元素之間的一一對應關(guān)系，其中這些元素的組合要滿足一定的對應關(guān)系。諸如：S-C 之間的對應關(guān)系；T-C 之間的對應關(guān)系；R-C 之間的對應關(guān)系；T-N 之間的對應關(guān)系；S-N 之間的對應關(guān)系；這些對應關(guān)系是主要考慮的限制條件，還有一些次要的限制條件。這是一個復雜的NPC問題，它的求解是一個完整類的求解問題。   在文獻中使用代數(shù)的矢量空間的概念，將S，C，T，N，R 中每個組中的每一個元素的組合用5 維空間的點來表示，合并S和C為一個維度，合并N和R為一個緯度，可得3維空間點陣。本文引入教學任務概念，如圖1所示，本文進一步將空間點陣細化，明確具體

4、開課點在空間上的交點來源及含義。在T，C，S對應的平面上的點定義為教學任務1（C1，S1，W1，T1），C，S坐標上對應的點是班級排課序列，空間點P1，P2即為求的開課的時間和地點。3  排課問題求解方法   根據(jù)圖1描述空間點情況，排課問題的解就是空間中對應的交點P1，P2等。求解過程   (1)確定CS軸上的點：此過程就是給班級排課，某班（S）上某門課程（C），在什么類型的教室上課（O），每周幾課時（V），開課時間（開課周數(shù)，如單周開課、雙周開課、510周開課等）（Y）。   (2)確定NR軸上的點：此過程為列出所有可用

5、教室。此軸上應該列出每節(jié)（N）所有可用的教室資源（R），此外，每個教室對應有教室類型（O）。   (3)確定T軸上的點：此軸上列出所有的教師資源（T）。   (4)確定TCS平面上的點：此過程就是安排教學任務，也就是教師任課選擇。   (5)尋找TCSNR空間上的點：此過程就是排課，根據(jù)教學任務列出的教室類型，查找符合條件的NR上的點，從而完成排課。   在排課求解過程中，潛在幾個約束必須要滿足：   (1) 一個班級在某一節(jié)課時只能在一個地點上課；如得到P1前，必須檢查S1在N1時刻是否已經(jīng)存

6、在一個交點。   (2) 一個教師在某一節(jié)課時只能在一個地點上課；如得到P1前，必須檢查T1在N1時刻是否已經(jīng)存在一個交點。   (3) 一個地點在某一節(jié)課時只能有一個教學任務；如得到P1前，必須檢查N1R1是否已經(jīng)存在交點，合班教學除外。   (4) 一個地點的座位數(shù)是否大于上課學生總數(shù)；如得到P1前，必須檢查R1座位數(shù)是否大于S1。4  數(shù)據(jù)庫建模            務對于合班上課的處理可以虛擬為一條教學任務，這樣可在

7、排課過程中保持教學任務與教室、時間的一一對應關(guān)系。5  排課過程   排課遵循排課問題求解方法所描述過程，首先是教學任務數(shù)據(jù)的采集，采用Web模式，各教學部門首先對于班級排課，然后對于教師排課，然后選擇上課場地類型，并且選擇對應的周學時，從而生成教學任務。采用此方式，降低教務部門的壓力，各系的教學任務由個系自己提交完成，然后教務處審核，通過后即可進行排課任務。   排課程序采用VC程序?qū)崿F(xiàn)，排課過程采用自動排課和手動調(diào)課結(jié)合的方式，自動排課具體方法就是將教學任務安排到時間與地點構(gòu)成的點上，并同時檢查是否同時滿足約束4個約束條件，如果滿足，則教學

8、任務安排上課完畢，并對于教學任務做已安排標記；否則，繼續(xù)下一個時間與地點構(gòu)成的點并檢查約束。手動排課對于自動排課不完或者不合理的地方進行手動調(diào)整，使課程表更加合理。排課過程需要按照一定的順序進行，即對于教學任務中要求的資源相對短缺的先進行計算排課，對于一般要求或者資源相對充裕的后排課，這就要求排課前必須先對于全部資源和教學任務進行計算，由程序來統(tǒng)計出上課需求資源和實際資源，從而進行優(yōu)先級別排序，依順序進行排課。   排課過程中需要考慮的特殊問題的處理：   (1) 上大課（合班上課）的處理，合班上課會違反第(3)個約束，因此對于合班上課首先將其教學任務合

9、并。   (2) 公共選修課的處理：全校范圍內(nèi)選修某門課程，根據(jù)學生選修情況分班，該分班結(jié)果為虛擬班級，然后對虛擬班級排課，此外，控制選修課程在固定的時間范圍開設(shè)，以免違反第(2)個約束。   (3) 雙肩挑教師上課時間的處理：對于雙肩挑教師，設(shè)定某一時間段統(tǒng)一不排課。   (4) 雙職工教師上課時間的處理：處于人性化考慮，屬于此類教師，3、4節(jié)不能同時排課。6  結(jié)束語   本文描述了課程表的空間點陣模型及排課算法，另外給出了課程表的E-R圖，可以據(jù)此順利實現(xiàn)一個排課系統(tǒng)，具有較高的實用價值。本文所描述的算法已經(jīng)對于1500條實際教學任務的學校進行了2個學期的排課，結(jié)果比較理想，因此具有一定的實用性，此外對于課程表排好后，采用Web方式發(fā)布，隨時隨地可以查詢和打印，方便快捷。參考文獻1潘以鋒.高校智能排課系統(tǒng)的算法J.上海師范大學學報(自然科學版)，200