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