王俊生 戴云龍

【摘要】該文在分析了影響排課效果的非技術(shù)性因素基礎(chǔ)上,提出了一個(gè)自動(dòng)排課的課程優(yōu)先級(jí)計(jì)算模型,并通過層次分析法確定了各影響因素的權(quán)重和取值。通過實(shí)驗(yàn)證明,該文模型可以提高自動(dòng)排課系統(tǒng)的排課效果。

【關(guān)鍵詞】自動(dòng)排課;課程優(yōu)先;AHP;教學(xué)管理

【中圖分類號(hào)】G420 【文獻(xiàn)標(biāo)識(shí)碼】B 【論文編號(hào)】1009—8097(2009)11—0032—04

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

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

一 非技術(shù)性因素對(duì)排課的影響

排課系統(tǒng)是一個(gè)由教學(xué)計(jì)劃維護(hù)、教學(xué)進(jìn)程編排、下達(dá)教學(xué)任務(wù)、教學(xué)任務(wù)審核、開課任務(wù)維護(hù)、預(yù)排課表、排定課表、手工課表調(diào)整等流程組成,是由教務(wù)處和二級(jí)學(xué)院共同完成的一項(xiàng)復(fù)雜的系統(tǒng)工作,只有分析了各個(gè)環(huán)節(jié)中非技術(shù)性因素的影響,才能排定出合理的課表。

1教學(xué)計(jì)劃。教學(xué)計(jì)劃規(guī)定了各個(gè)專業(yè)的課程及其各學(xué)期課程的分布情況,是安排教學(xué)進(jìn)程、落實(shí)教學(xué)任務(wù)的基礎(chǔ)性文件,具有一定的穩(wěn)定性和權(quán)威性,它對(duì)排課效果的影響是明顯的。教學(xué)計(jì)劃中課程分為必修課、限選課和任選課,一般來說必修課應(yīng)該被優(yōu)先安排,獲得較好的上課時(shí)間,其次是限選課和任選課。課程具有學(xué)分和學(xué)時(shí)性質(zhì),一般一個(gè)學(xué)分為16-18學(xué)時(shí),從排課效果來說大學(xué)分和大學(xué)時(shí)的課程應(yīng)該被優(yōu)先安排。

2教師資源。教師資源對(duì)排課效果的影響主要體現(xiàn)在兩個(gè)方面:教師工作量的不平衡和教師的個(gè)性化要求。當(dāng)前高校教師數(shù)量存在較為不平衡現(xiàn)象,有的專業(yè)特別是基礎(chǔ)課教師工作量非常大,而有的專業(yè)教師卻工作量嚴(yán)重不足,從而對(duì)排課系統(tǒng)產(chǎn)生了較大的影響。特別是大工作量的教師的課表就較難安排,于是從排課效果的角度來說就應(yīng)該優(yōu)先安排。教師個(gè)性化需求的滿足是高?！耙匀藶楸尽钡囊粋€(gè)具體體現(xiàn),在滿足班級(jí)課表合理的情況下,應(yīng)該考慮教師的個(gè)性化需求。

3合班問題。合班問題是困擾高校排課人員的一個(gè)難點(diǎn)問題,對(duì)排課的影響主要體現(xiàn)在兩個(gè)方面:合班的方式和合班的數(shù)量。合班的方式是不同課程的合班組合方式,實(shí)踐證明一般一個(gè)班級(jí)如果有3門及3門以上課程合班不同時(shí),課表將非常難安排,安排出的課表可能會(huì)較不合理。合班的數(shù)量是指一門課程合在一起上課班級(jí)的數(shù)量,合班數(shù)量越多課表越難安排,從排課效果的角度來說合班數(shù)量多的課程應(yīng)該優(yōu)先安排。

4教室資源。教室資源是限制排課效果的因素之一。這里的教室包括高校的體育場(chǎng)地、實(shí)驗(yàn)室、設(shè)計(jì)教室、多媒體及非多媒體教室等用于教學(xué)的場(chǎng)所。一般高校中體育場(chǎng)體、實(shí)驗(yàn)室及多媒體教室比較短缺,對(duì)其需求課程應(yīng)該優(yōu)先安排 。

5課程的時(shí)間分布。主要指課程在課表中的橫向分布和縱向分布。橫向分布指的課程周學(xué)時(shí),縱向分布指課程的上課周次。相對(duì)于課程上課周次,周學(xué)時(shí)對(duì)排課的影響更大。一般周學(xué)時(shí)分為:2、3、5、6及以上學(xué)時(shí),學(xué)時(shí)越大課程應(yīng)該該被優(yōu)先安排,特別是當(dāng)一門課程學(xué)時(shí)大于6時(shí),應(yīng)該獲得較高的優(yōu)先級(jí)。

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

二 自動(dòng)排課課程優(yōu)先級(jí)計(jì)算模型

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

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

1 確定各影響因素的權(quán)重

(1)層次結(jié)構(gòu)模型設(shè)計(jì)

依據(jù)影響課程優(yōu)先級(jí)因素分析,構(gòu)建如圖1所示的層次結(jié)構(gòu)模型。

(2)判斷矩陣構(gòu)建

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

易知A為互反矩陣, aii = 1,aij =1/ aji ,i,j = 1,2, …,n 。第一行第二列值表示影響因素V1(課程性質(zhì))與V2(周學(xué)時(shí))對(duì)評(píng)價(jià)目標(biāo)排課效果影響大小進(jìn)行比較,其結(jié)果3表示專家認(rèn)為“課程性質(zhì)比周學(xué)時(shí)略為重要”,相反第二行第一列的值就應(yīng)該取1/3。第一行第四列的7表示“課程性質(zhì)比學(xué)分?jǐn)?shù)確實(shí)重要”, 同樣第四行第一列就的值就應(yīng)該為1/7。

(3)排序向量的計(jì)算與一致性檢驗(yàn)

對(duì)判斷矩陣A進(jìn)行特征值λ和特征向量Wi計(jì)算,將特征向量規(guī)范化,結(jié)果見表2,P1-P10表示10個(gè)專家,W1,W2,…,W7表示各因素評(píng)價(jià)指標(biāo)權(quán)重, 表示最大特征值。表2表明:各個(gè)專家對(duì)非技術(shù)性因素對(duì)課程優(yōu)先級(jí)影響的觀點(diǎn)并不完全一致,P1專家認(rèn)為教室類型(W3=0.358)對(duì)排課的影響最大,而學(xué)分?jǐn)?shù)(W6=0.025)影響最小;P3專家認(rèn)為課程性質(zhì)(W1=0.295)對(duì)排課的影響最大,而排課模式(W7=0.021)影響最小。

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

(4)排序向量綜合

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

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

影響課程優(yōu)先級(jí)順序的另外一個(gè)因素就是各影響因素的具體取值Ci。我們?nèi)匀贿x取上面的10個(gè)專家,利用AHP法確定影響因素的具體取值,整體計(jì)算過程同上。計(jì)算結(jié)果為:C課程屬性(必修課,限選課,任選課)=(0.48,0.38,0.14); C周學(xué)時(shí)(2-3,4-5,6及以上)=(0.25,0.35,0.4);C教室類型(體育場(chǎng)地,實(shí)驗(yàn)室,多媒體,非多媒體)=(0.4,0.4,0.18,0.02);C學(xué)分?jǐn)?shù)(2下,2-3,4,5及以上)=(0.06,0.24,0.32,0.38);C合班數(shù)(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 實(shí)驗(yàn)及分析

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

三 結(jié)論

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

參考文獻(xiàn)

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

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

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

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

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

[6] 郭向勇,傅國強(qiáng),周玉芬.基于層次分析法的網(wǎng)絡(luò)課程學(xué)習(xí)評(píng)價(jià)模型[J].電化教育研究,2008,(3):72-76.

[7] 刑紅宇. 基于AHP法和Delphi 法的網(wǎng)絡(luò)課程評(píng)價(jià)指標(biāo)體系設(shè)計(jì)研究[J].中國電化教育,2006,(9):78-81.

[8] 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)[M],北京:清華大學(xué)出版社,1997.