基于層次分析法的自動排課課程優先級模型

王俊生 戴云龍

【摘要】該文在分析了影響排課效果的非技術性因素基礎上,提出了一個自動排課的課程優先級計算模型,并通過層次分析法確定了各影響因素的權重和取值。通過實驗證明,該文模型可以提高自動排課系統的排課效果。

【關鍵詞】自動排課;課程優先;AHP;教學管理

【中圖分類號】G420 【文獻標識碼】B 【論文編號】1009—8097(2009)11—0032—04

排課是高校教學運行管理中的一個重要環節,課表安排是否合理直接關系到學校教學工作的有序性和穩定性。自動排課系統就是在教師、教室和時間這3大資源數量有限,約束不同的條件下,由計算機根據一定的算法,合理安排班級的課程,使得學生和教師獲得較為合理的上課時間和空間,是一個多目標的調度問題,在運籌學中被稱為時間表問題(Timetable Problem,簡稱TTP)。隨著高校學分制教學管理的不斷深入及招生規模的不斷擴大,排課過程中的矛盾也凸顯出來,如何合理高效地完成課表的安排成為學校教學管理人員關注的一個重點問題。

對自動排課系統產生影響的因素有兩類,一類為技術因素,主要指排課模型、排課算法對排課效果的制約;另一類為非技術性因素,主要指排課過程中,教學計劃、課程學分學時、教師、教室等非技術性因素對排課效果的制約。近幾年,我國有很多學者對自動排課進行了探討,熱點集中在對排課算法的研究及排課整體模式的構建,即技術因素上,例如將人工智能算法如遺傳算法[1-2]、禁忌搜索算法[3]運用到排課系統中,取得了不錯的效果。而對課程本身性質對排課的影響討論較少。合班是否合理是影響排課效果的因素之一,郭俊柏[4]等建立合班的數學模型,且通過非線性規劃的方法求解,得出了課程和班級較少情況下的較為合理的合班狀態,但對高校排課中合班的復雜的實際情況是否實用還待驗證。陸如秋[5]分析排課過程中的基本要素主要有教學計劃、教師、教室、學生及時間,比較全面,但卻沒有對如何將這些基本要素運用到自動排課中提出合理的建議。本文正是基于此,分析非技術性因素對排課系統的影響,且提出了將非技術性因素應用到實際自動排課系統中的方案,實踐證明可以獲得較為理想的排課結果。

一 非技術性因素對排課的影響

排課系統是一個由教學計劃維護、教學進程編排、下達教學任務、教學任務審核、開課任務維護、預排課表、排定課表、手工課表調整等流程組成,是由教務處和二級學院共同完成的一項復雜的系統工作,只有分析了各個環節中非技術性因素的影響,才能排定出合理的課表。

1教學計劃。教學計劃規定了各個專業的課程及其各學期課程的分布情況,是安排教學進程、落實教學任務的基礎性文件,具有一定的穩定性和權威性,它對排課效果的影響是明顯的。教學計劃中課程分為必修課、限選課和任選課,一般來說必修課應該被優先安排,獲得較好的上課時間,其次是限選課和任選課。課程具有學分和學時性質,一般一個學分為16-18學時,從排課效果來說大學分和大學時的課程應該被優先安排。

2教師資源。教師資源對排課效果的影響主要體現在兩個方面:教師工作量的不平衡和教師的個性化要求。當前高校教師數量存在較為不平衡現象,有的專業特別是基礎課教師工作量非常大,而有的專業教師卻工作量嚴重不足,從而對排課系統產生了較大的影響。特別是大工作量的教師的課表就較難安排,于是從排課效果的角度來說就應該優先安排。教師個性化需求的滿足是高校“以人為本”的一個具體體現,在滿足班級課表合理的情況下,應該考慮教師的個性化需求。

3合班問題。合班問題是困擾高校排課人員的一個難點問題,對排課的影響主要體現在兩個方面:合班的方式和合班的數量。合班的方式是不同課程的合班組合方式,實踐證明一般一個班級如果有3門及3門以上課程合班不同時,課表將非常難安排,安排出的課表可能會較不合理。合班的數量是指一門課程合在一起上課班級的數量,合班數量越多課表越難安排,從排課效果的角度來說合班數量多的課程應該優先安排。

4教室資源。教室資源是限制排課效果的因素之一。這里的教室包括高校的體育場地、實驗室、設計教室、多媒體及非多媒體教室等用于教學的場所。一般高校中體育場體、實驗室及多媒體教室比較短缺,對其需求課程應該優先安排 。

5課程的時間分布。主要指課程在課表中的橫向分布和縱向分布。橫向分布指的課程周學時,縱向分布指課程的上課周次。相對于課程上課周次,周學時對排課的影響更大。一般周學時分為:2、3、5、6及以上學時,學時越大課程應該該被優先安排,特別是當一門課程學時大于6時,應該獲得較高的優先級。

6排課時間模式。排課時間模式是一種排課時間的組合形式,分為:一般模式、單元模式、特殊模式及公選課模式等。一般模式安排周學時為2、3、5、6等學時的課程;單元模式則安排一個上午或一個下午的半天課;特殊模式根據自己的實際定義的排課時間模式;公選課模式是定義了只能安排在公選課上課時間的排課模式。一般來說,單元模式和特殊模式被優先安排,容易產生理想的排課效果。

二 自動排課課程優先級計算模型

自動排課系統中課程的安排順序是影響排課效果的關鍵因素。一個班級排課順序影響著本班課表編排的合理性;整個學校的排課順序影響著整個學校所有班級課表合理性。為此,本文引入影響排課效果的非技術性因素,為每一個預排課程設置優先級,建立了一種課程優先級計算模型,用于決定課程被安排的順序,優先級高的課程被優先安排。本文選取7個具有代表性的非技術性因素用于課程優先級計算模型,包括課程性質、周學時、教室類型、學分數、分班數、教師工作量及排課時間模式,用Wi表示, ,且用Ci表示第i個影響因素的具體取值,從公式(1)可以看出,影響PCF取值大小的有各影響因素權值的大小及具體取值。如何確定各影響因素的權重及取值對課程優先級的計算非常重要。

層次分析法(Analytical Hierarchy Process 簡記AHP)是由美國運籌學家T.L.Satty于20世紀70年代末提出的。它是一種結合了定量與定性分析的系統分析方法,尤其在多因素系統評價的指標權重確定中應用非常廣泛[6-7]。為此,本文引入AHP法,以揚州大學為例介紹課程優先級各影響因素的權重和具體取值計算過程。

1 確定各影響因素的權重

(1)層次結構模型設計

依據影響課程優先級因素分析,構建如圖1所示的層次結構模型。

(2)判斷矩陣構建

判斷矩陣構建是層次分析法最為關鍵的環節。分為兩步:選取專家和構建判斷矩陣。選取專家的過程中,專家的學科結構和職業結構對判斷矩陣的構建具有決定性的作用。為了保證判斷矩陣構建的合理,選取計算機、教育及具有排課經驗的專家共10人來構建判斷矩陣。構建判斷矩陣實際是請專家對圖1中所示的所有的因素都進行倆倆比較的過程,如果分層中有n個因素,一般需要n(n-1)/2次比較,圖1第二層有7個因素,故需21次比較。為了表示比較的結果,層次分析法提出了相對重要性的比例標度,兩個元素相對重要性的比較可變化得到一個衡量的數。為了說明問題,現設有n個因素對目標有影響,用aij表示影響因素Bi與Bj對目標的相對重要性比例標度,則表1給出了aij值定義。

易知A為互反矩陣, aii = 1,aij =1/ aji ,i,j = 1,2, …,n 。第一行第二列值表示影響因素V1(課程性質)與V2(周學時)對評價目標排課效果影響大小進行比較,其結果3表示專家認為“課程性質比周學時略為重要”,相反第二行第一列的值就應該取1/3。第一行第四列的7表示“課程性質比學分數確實重要”, 同樣第四行第一列就的值就應該為1/7。

(3)排序向量的計算與一致性檢驗

對判斷矩陣A進行特征值λ和特征向量Wi計算,將特征向量規范化,結果見表2,P1-P10表示10個專家,W1,W2,…,W7表示各因素評價指標權重, 表示最大特征值。表2表明:各個專家對非技術性因素對課程優先級影響的觀點并不完全一致,P1專家認為教室類型(W3=0.358)對排課的影響最大,而學分數(W6=0.025)影響最小;P3專家認為課程性質(W1=0.295)對排課的影響最大,而排課模式(W7=0.021)影響最小。

為了保證判斷矩陣的一致性,對每個判斷矩陣進行一致性檢驗。由矩陣理論知: 越接近影響因子數量n,得到的解(特征向量)越接近于正確的排序,所作的判斷也越準確。故層次分析法引入隨機一致性比率CR=CI/RI,作為評價一致性的標準,其中CI=( -n)/(n-1),RI見表3。RI在10%附近及以下時,一般認為判斷矩陣是具有滿意的一致,在判斷矩陣較為復雜(大于7階)的情況下,可以放到20%。否則必須調整。表2表明:P7的CR最大為9.8%,P5的CR最小為4.2%,所有判斷矩陣具有滿意的一致性。

(4)排序向量綜合

每個專家的評價權重結果計算完畢,需計算綜合評價權重。計算方法有兩種:加權算數平均法及加權幾何平均法(公式略)。將之規范化就可以得到綜合評價權重向量。計算結果見表2,加權算數平均計算結果W算=(0.169,0.094,0.306,0.043,0.199,0.108,0.088),加權幾何平均計算結果W幾=(0.161,0.098,0.336,0.038,0.203,0.091,0.073),兩種算法計算結果比較相近,但不完全一樣。加權算數平均計算結果顯示對排課影響從大到小依次為:教室類型、分班數、課程性質、教師工作量、周學時、排課時間模式及學分數。加權幾何平均法計算結果則認為周學時(0.098)較教師工作量(0.091)重要,其它與加權算數平均計算的排序結果相同。教室類型被認為是制約排課結果最為重要的因素,體現出學校的實際情況:實驗室、體育場、設計教室及部分校區的多媒體教室的缺乏制約了排課。合班被認為是次重要的因素,顯示出我校在教學任務落實的過程中,每個課程合班數量較大,且不科學,特別是通修課程更為嚴重,也從側面體現出我校現在通修課師資不夠的現象。本文選擇了加權幾何平均法計算的結果進行下面的分析。

2 確定各影響因素的取值Ci

影響課程優先級順序的另外一個因素就是各影響因素的具體取值Ci。我們仍然選取上面的10個專家,利用AHP法確定影響因素的具體取值,整體計算過程同上。計算結果為:C課程屬性(必修課,限選課,任選課)=(0.48,0.38,0.14); C周學時(2-3,4-5,6及以上)=(0.25,0.35,0.4);C教室類型(體育場地,實驗室,多媒體,非多媒體)=(0.4,0.4,0.18,0.02);C學分數(2下,2-3,4,5及以上)=(0.06,0.24,0.32,0.38);C合班數(1,2,3,4及以上)=(0.03,0.24,0.33,0.4);C教師工作量(4及以下,5-8,9-12,13及以上)=(0.05,0.15,0.35,0.45);C排課模式(一般模式,特殊模式,單元模式,公選課模式)=(0.22,0.35,0.38,0.05)。

3 實驗及分析

以揚州大學2008-2009秋季學期,3307門課程,近700班級,1580教師參與排課為例進行實驗。用AHP法確定了影響課程優先級多因素的權重和具體取值以后,根據公式(1)計算每門課程的優先級PCF,然后利用冒泡排序算法[8]對每門課程的PCF排序,得到所有課程的優先級排序結果。按照PCF從大到小的順序由自動排課系統排課,結果有105門課程沒有安排成功,其它課程都有了較好的排課結果,比未計算PCF之前的排課結果有(358未安排成功)較大幅度的提高。同時課程安排分布較為合理,達到計算機自動排課的目標。

三 結論

影響自動排課系統的非技術性因素主要有教學計劃、教師資源、合班問題、教室資源、課程的時間分布及排課的時間模式等。文中構建了一種排課課程的優先級計算模型,并通過AHP法分析得出影響我校排課效果因素的權重和具體取值,給出AHP法的詳細計算過程。各因素對排課效果的影響,從大到小的依次為:教室類型、分班數、課程性質、周學時、教師工作量、排課時間模式及學分數。體現出教室類型特別是體育場地、實驗室及多媒體教室直接制約我校的自動排課系統的排課結果;分班情況是否合理也是影響排課效果的重要因素;而學分大小則對排課的效果影響較小。各影響因素的具體取值中:必修課、體育場地、學分在5以上、周學時在6及以上、合班數在4及以上,教師周工作量在13及以上及時間模式為單元模式的課程獲得了較高的取值,應該被優先安排。最后通過實踐證明,基于AHP的自動排課課程優先級計算模型可以有效地提高排課的效率和獲得較為理想的排課效果,為自動排課系統完善提供了新的思路。

參考文獻

[1] 王俊生.基于遺傳算法的排課系統研究[J].中國教育信息化,2008,(9):51-53.

[2] 韋玉,馮速.免疫遺傳算法在排課問題中的應用[J].北京師范大學學報,2008,(4):168-172.

[3] 丁振國,趙宏維.禁忌搜索求解排課問題的應用研究[J].微電子學與計算機,2008,(4):31-34.

[4] 郭俊柏,邢永麗.高校排課中的合班問題[J].湘潭師范學院學報,2008,(4):8-9.

[5] 陸如秋.淺談高校學分制管理中排課的制約因素及模式[J].廣西師范學院學報,2007,(10):53-55.

[6] 郭向勇,傅國強,周玉芬.基于層次分析法的網絡課程學習評價模型[J].電化教育研究,2008,(3):72-76.

[7] 刑紅宇. 基于AHP法和Delphi 法的網絡課程評價指標體系設計研究[J].中國電化教育,2006,(9):78-81.

[8] 嚴蔚敏,吳偉民.數據結構[M],北京:清華大學出版社,1997.