本文關(guān)鍵詞：排課算法，由筆耕文化傳播整理發(fā)布。

自動(dòng)排課算法分析

1   緒 論

1．1課題背景與研究意義

1．2課題的應(yīng)用領(lǐng)域

1．3 課題的現(xiàn)狀

1．4解決NP問(wèn)題的幾種算法及其比較

2   目前流行的幾種排課算法的介紹

2．1. 自動(dòng)排課算法

2．2 基于優(yōu)先級(jí)的排課算法

3   基于時(shí)間片優(yōu)先級(jí)排課算法描述與分析

3．1排課中的基本原則

3．2排課的基本要求

3．3基于時(shí)間片優(yōu)先級(jí)排課算法描述

3．4算法分析

參 考 資 料

1   緒 論

 1課題背景與研究意義

排課問(wèn)題早在70年代就證明是一個(gè)NP完全問(wèn)題，即算法的計(jì)算時(shí)間是呈指數(shù)增長(zhǎng)的，這一論斷確立了排課問(wèn)題的理論深度。對(duì)于NP問(wèn)題完全問(wèn)題目前在數(shù)學(xué)上是沒(méi)有一個(gè)通用的算法能夠很好地解決。然而很多NP完全問(wèn)題目具有很重要的實(shí)際意義，例如。大家熟悉地路由算法就是很典型的一個(gè)NP完全問(wèn)題，路由要在從多的節(jié)點(diǎn)中找出最短路徑完成信息的傳遞。既然都是NP完全問(wèn)題，那么很多路由算法就可以運(yùn)用到解決排課問(wèn)題上，如Dijkstra算法、節(jié)點(diǎn)子樹(shù)剪枝構(gòu)造網(wǎng)絡(luò)最短路徑法等等。

   目前大家對(duì)NP 完全問(wèn)題研究的主要思想是如何降低其計(jì)算復(fù)雜度。即利用一個(gè)近似算法來(lái)代替，力爭(zhēng)使得解決問(wèn)題的時(shí)間從指數(shù)增長(zhǎng)化簡(jiǎn)到多項(xiàng)式增長(zhǎng)。結(jié)合到課表問(wèn)題就是建立一個(gè)合適的現(xiàn)實(shí)簡(jiǎn)約模型，利用該簡(jiǎn)約模型能夠大大降低算法的復(fù)雜度，便于程序?qū)崿F(xiàn)，這是解決排課問(wèn)題一個(gè)很多的思路。

在高等院校中，培養(yǎng)學(xué)生的主要途徑是教學(xué)。在教學(xué)活動(dòng)中，有一系列管理工作，其中，教學(xué)計(jì)劃的實(shí)施是一個(gè)重要的教學(xué)環(huán)節(jié)。每學(xué)期管理人員都要整理教學(xué)計(jì)劃，根據(jù)教學(xué)計(jì)劃下達(dá)教學(xué)任務(wù)書(shū)，然后根據(jù)教學(xué)任務(wù)書(shū)編排課程表。在這些教學(xué)調(diào)度工作中，既有大量繁瑣的數(shù)據(jù)整理工作，更有嚴(yán)謹(jǐn)思維的腦力勞動(dòng)，還要填寫(xiě)大量的表格。因此工作非常繁重。

加之，隨著教學(xué)改革的進(jìn)行及“211”工程的實(shí)施，新的教育體制對(duì)課表的編排提出了更高的要求。手工排課時(shí)，信息的上通下達(dá)是極其麻煩的，而采用計(jì)算機(jī)排課，教學(xué)中的信息可以一目了然，對(duì)于優(yōu)化學(xué)生的學(xué)習(xí)進(jìn)程，評(píng)估每位教師對(duì)教學(xué)的貢獻(xiàn)，領(lǐng)導(dǎo)合理決策等都具有重要的意義，必將會(huì)大大推進(jìn)教學(xué)的良性循環(huán)。

 2課題的應(yīng)用領(lǐng)域

本課題的研究對(duì)開(kāi)發(fā)高校排課系統(tǒng)有指導(dǎo)作用。

排課問(wèn)題的核心為多維資源的沖突與搶占，對(duì)其研究對(duì)類似的問(wèn)題（特別是與時(shí)間表有關(guān)的問(wèn)題：如考試排考場(chǎng)問(wèn)題、電影院排座問(wèn)題、航空航線問(wèn)題）也是個(gè)參考。

   3 課題的現(xiàn)狀

年代末，國(guó)外就有人開(kāi)始研究課表編排問(wèn)題。1962年，Gotlieb曾提出了一個(gè)課表問(wèn)題的數(shù)學(xué)模型，并利用匈牙利算法解決了三維線性運(yùn)輸問(wèn)題。次后，人們對(duì)課表問(wèn)題的算法、解的存在性等問(wèn)題做了很多深入探討。但是大多數(shù)文獻(xiàn)所用的數(shù)學(xué)模型都是Gotlieb的數(shù)學(xué)模型的簡(jiǎn)化或補(bǔ)充，而至今還沒(méi)有一個(gè)可行的算法來(lái)解決課表問(wèn)題。

     近40年來(lái)，人們對(duì)課表問(wèn)題的計(jì)算機(jī)解法做了許多嘗試。其中，課表編排的整數(shù)規(guī)劃模型將問(wèn)題歸結(jié)為求一組0-1變量的解，但是其計(jì)算量非常大。解決0-1線性優(yōu)化問(wèn)題的分支一定界技術(shù)卻只適用也規(guī)模較小的課表編排，Mihoc和Balas（1965）將課表公式化為一個(gè)優(yōu)化問(wèn)題，Krawczk則提出一種線性編程的方法。Junginger將課表問(wèn)題簡(jiǎn)化為三維運(yùn)輸問(wèn)題，而Tripathy則把課表問(wèn)題視作整數(shù)線性編程問(wèn)題并提出了大學(xué)課表的數(shù)學(xué)模型。

     此外，有些文獻(xiàn)試圖從圖論的角度來(lái)求解排課表的問(wèn)題，但是圖的染色問(wèn)題也是NP完全問(wèn)題，只有在極為簡(jiǎn)單的情況下才可以將課表編排轉(zhuǎn)化為二部圖匹配問(wèn)題，這樣的數(shù)學(xué)模型與實(shí)際相差太遠(yuǎn)，所以對(duì)于大多數(shù)學(xué)校的課表編排問(wèn)題來(lái)說(shuō)沒(méi)有實(shí)用價(jià)值。

     進(jìn)入九十年代以后，國(guó)外對(duì)課表問(wèn)題的研究仍然十分活躍。比較有代表的有印度的Vastapur大學(xué)管理學(xué)院的ArabindaTripathy、加拿大Montreal大學(xué)的Jean Aubin和Jacques Ferland等。目前，解決課表方法的問(wèn)題有：模擬手工排課法，圖論方法，拉格朗日法，二次分配型法等多種方法。由于課表約束復(fù)雜，用數(shù)學(xué)方法進(jìn)行描述時(shí)往往導(dǎo)致問(wèn)題規(guī)模劇烈增大，這已經(jīng)成為應(yīng)用數(shù)學(xué)編程解決課表問(wèn)題的巨大障礙。國(guó)外的研究表明，解決大規(guī)模課表編排問(wèn)題單純靠數(shù)學(xué)方法是行不通的，而利用運(yùn)籌學(xué)中分層規(guī)劃的思想將問(wèn)題分解，將是一個(gè)有希望得到成功的辦法。

     在國(guó)內(nèi)，對(duì)課表問(wèn)題的研究開(kāi)始于80年代初期、具有代表性的有：南京工學(xué)院的UTSS（A University Timetable Scheduling System）系統(tǒng)，清華大學(xué)的TISER（Timetable SchedulER）系統(tǒng)，大連理工大學(xué)的智能教學(xué)組織管理與課程調(diào)度等，這些系統(tǒng)大多數(shù)都是模擬手工排課過(guò)程，以“班”為單位，運(yùn)用啟發(fā)式函數(shù)來(lái)進(jìn)行編排的。但是這些系統(tǒng)課表編排系統(tǒng)往往比較依賴于各個(gè)學(xué)校的教學(xué)體制，不宜進(jìn)行大量推廣。

從實(shí)際使用的情況來(lái)看，國(guó)內(nèi)外研制開(kāi)發(fā)的這些軟件系統(tǒng)在實(shí)用性上仍不盡如人意。一方面原因是作為一個(gè)很復(fù)雜的系統(tǒng)，排課要想面面俱到是一件很困難的事；另一方面每個(gè)學(xué)校由于其各自的特殊性，自動(dòng)排課軟件很難普遍實(shí)用，特別是在調(diào)度的過(guò)程中一個(gè)很小的變動(dòng)，要引起全部課程的大調(diào)整，這意味著全校課程大變動(dòng)，在實(shí)際的應(yīng)用中這是很難實(shí)現(xiàn)的事。

  4解決NP問(wèn)題的幾種算法及其比較

    解決NP完全問(wèn)題只能依靠近似算法，所以下面介紹幾種常用算法的設(shè)計(jì)思想，包括動(dòng)態(tài)規(guī)劃、貪心算法、回溯法等。

動(dòng)態(tài)規(guī)劃法是將求解的問(wèn)題一層一層地分解成一級(jí)一級(jí)、規(guī)模逐步縮小的子問(wèn)題，直到可以直接求出其解的子問(wèn)題為止。分解成的所有子問(wèn)題按層次關(guān)系構(gòu)成一顆子問(wèn)題樹(shù)。樹(shù)根是原問(wèn)題。原問(wèn)題的解依賴于子問(wèn)題樹(shù)中所有子問(wèn)題的解。動(dòng)態(tài)規(guī)劃算法通常用于求一個(gè)問(wèn)題在某種意義下的最優(yōu)解。設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法，通常可按以下幾個(gè)步驟進(jìn)行：

    1. 分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。

    2. 遞歸的定義最優(yōu)解。

    3. 以自底向上的方式計(jì)算出最優(yōu)解。

    4. 根據(jù)計(jì)算最優(yōu)解時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。

步驟1~3是動(dòng)態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)解的情形，步驟4可以省去。若需要求出問(wèn)題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟4。此時(shí)，在步驟3中計(jì)算最優(yōu)解時(shí)，通常需記錄更多的信息，以便在步驟4中，根據(jù)所記錄的信息，快速地構(gòu)造出一個(gè)最優(yōu)解。

（二）貪心算法

當(dāng)一個(gè)問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，我們會(huì)想到用動(dòng)態(tài)規(guī)劃法去解它，但有時(shí)會(huì)有更簡(jiǎn)單、更有效的算法，即貪心算法。顧名思義，貪心算法總是做出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不是整體最優(yōu)上加以考慮，他所作出的選擇只是在某種意義上的局部最優(yōu)的選擇。雖然貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣的許多問(wèn)題它能產(chǎn)生整體最優(yōu)解，如圖的算法中單源最短路徑問(wèn)題，最小支撐樹(shù)問(wèn)題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，但其最終結(jié)果卻是最優(yōu)解的很好的近似解。

在貪心算法中較為有名的算法是Dijkstra算法。它作為路由算法用來(lái)尋求兩個(gè)節(jié)點(diǎn)間的最短路徑。Dijkstra算法的思想是：假若G有n個(gè)頂點(diǎn)，于是我們總共需要求出n-1條最短路徑，求解的方法是：初試，寫(xiě)出V0(始頂點(diǎn))到各頂點(diǎn)(終頂點(diǎn))的路徑長(zhǎng)度，或有路徑，則令路徑的長(zhǎng)度為邊上的權(quán)值；或無(wú)路經(jīng)，則令為∞。再按長(zhǎng)度的遞增順序生成每條最短路徑。事實(shí)上生成最短路徑的過(guò)程就是不斷地在始頂點(diǎn)V何終頂點(diǎn)W間加入中間點(diǎn)的過(guò)程，因?yàn)樵诿可闪艘粭l最短路徑后，，就有一個(gè)該路徑的終頂點(diǎn)U，那么那些還未生成最短路徑的路徑就會(huì)由于經(jīng)過(guò)U而比原來(lái)的路徑短，于是就讓它經(jīng)過(guò)U。

（三）回溯法

回溯法有“通用的解題法”之稱。用它可以求出問(wèn)題的所有解或任一解。概括地說(shuō)，回溯法是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的搜索法。它在包含問(wèn)題所有解的一顆狀態(tài)空間樹(shù)上，按照深度優(yōu)先的策略，從根出發(fā)進(jìn)行搜索。搜索每到達(dá)狀態(tài)空間樹(shù)的一個(gè)節(jié)點(diǎn)，總是先判斷以該節(jié)點(diǎn)為根的子樹(shù)是否肯定不包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)該子樹(shù)的系統(tǒng)搜索，一層一層地向它的祖先節(jié)點(diǎn)繼續(xù)搜索，直到遇到一個(gè)還有未被搜索過(guò)的兒子的節(jié)點(diǎn)，才轉(zhuǎn)向該節(jié)點(diǎn)的一個(gè)未曾搜索過(guò)的兒子節(jié)點(diǎn)繼續(xù)搜索；否則，進(jìn)入子樹(shù)，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索�；厮莘ㄔ谟脕�(lái)求問(wèn)題的所有解時(shí)，要回溯到根，且根的所有兒子都已被搜索過(guò)才結(jié)束；而在用來(lái)求問(wèn)題的任一解時(shí)，只要搜索到問(wèn)題的一個(gè)解就可結(jié)束。

2   目前流行的幾種排課算法的介紹

2．1. 自動(dòng)排課算法

1 .問(wèn)題的描述

我們討論的自動(dòng)排課問(wèn)題的簡(jiǎn)化描述如下:

設(shè)要安排的課程為{ C1 , C2 , ., Cn} ,課程總數(shù)為n , 而各門(mén)課程每周安排次數(shù)(每次為連續(xù)的2 學(xué)時(shí)) 為{ N1 , N2 , ., Nn} ;每周教學(xué)日共5 天,即星期一～ 星期五;每個(gè)教學(xué)日最多安排4 次課程教學(xué),即1 ～ 2 節(jié)、3 ～ 4 節(jié)、5 ～ 6 節(jié)和7 ～ 8 節(jié)(以下分別稱第1 、2 、3 、4 時(shí)間段) . 在這種假設(shè)下,顯然每周的教學(xué)總時(shí)間段數(shù)為5 ×4 = 20 ,并存在以下約束關(guān)系:

　　　　n ≤20 , (1)

　　　　N = 6n， i =1， Ni ≤20. (2)

自動(dòng)排課問(wèn)題是:設(shè)計(jì)適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和算法, 以確定{ C1 , C2 , ., Cn } 中每個(gè)課程的教學(xué)應(yīng)占據(jù)的時(shí)間段,并且保證任何一個(gè)時(shí)間段僅由一門(mén)課程占據(jù).

2 .主要數(shù)據(jù)結(jié)構(gòu)

對(duì)于每一門(mén)課程,分配2 個(gè)字節(jié)的“時(shí)間段分配字”(無(wú)符號(hào)整數(shù)) :{ T1 , T2 , ., Tn} . 其中任何一個(gè)時(shí)間段分配字(假設(shè)為T(mén)i ) 都具有如下格式:

Ti 的數(shù)據(jù)類型C 語(yǔ)言格式定義為:unsigned int . Ti 的最高位是該課程目前是否是有效的標(biāo)志,0 表示有效,1 表示無(wú)效(如停課等) ;其它各位稱為課程分配位, 每個(gè)課程分配位占連續(xù)的3 個(gè)位(bit) ,表示某教學(xué)日(星期一～ 星期五) 安排該課程的時(shí)間段的值,0 表示當(dāng)日未安排,1 ～ 4 表示所安排的相應(yīng)的時(shí)間段(超過(guò)4 的值無(wú)效) .

在這種設(shè)計(jì)下, 有效的時(shí)間段分配字的值應(yīng)小于32 768 (十六進(jìn)制8000) , 而大于等于32 768 的時(shí)間段分配字對(duì)應(yīng)于那些當(dāng)前無(wú)效的課程(既使課程分配位已設(shè)置好也如此) , 因此很容易實(shí)現(xiàn)停課/ 開(kāi)課處理.

3 .排課算法

在上述假設(shè)下,自動(dòng)排課算法的目標(biāo)就是確定{ C1 , C2 , ., Cn} 所對(duì)應(yīng)的{ T1 , T2 , ., Tn} .

從安排的可能性上看,共有20 !/ (20 - N) !種排法( N 的含義見(jiàn)(2) 式) . 如果有4 門(mén)課,每門(mén)課一周上2 次,則N = 8 ,這8 次課可能的安排方法就會(huì)有20 !/ (20 - 8) ! = 5 079 110 400 ,即50 多億種. 如果毫無(wú)原則地在其中選擇一種方案,將會(huì)耗費(fèi)巨大量的時(shí)間. 所以排課的前提是必須有一個(gè)確定的排課原則. 我們采用輪轉(zhuǎn)分配法作為排課原則:從星期一第1 時(shí)間段開(kāi)始按{ C1 , C2 , ., Cn} 中所列順序安排完各門(mén)課程之后(每門(mén)課安排1 次) ,再按該順序繼續(xù)向后面的時(shí)間段進(jìn)行安排,直到所有課程的開(kāi)課次數(shù)符合{ N1 , N2 , ., Nn} 中給定的值為止. 在算法描述中將用{ C[1 ] , C[2 ] , ., C[ n ]} 表示{ C1 , C2 , ., Cn} , 對(duì){ N1 , N2 , ., Nn}

和{ T1 , T2 , ., Tn} 也采用同樣的表示法.

算法1 　排課算法

輸入　{ C1 , C2 , ., Cn} 、{ N1 , N2 , ., Nn} .

輸出　{ T1 , T2 , ., Tn} .

①　初始化:

　　星期值week = 1

　　時(shí)間段值segment = 1

　　{ T [1 ] , T [2 ] , ., T [ n ]} 中各時(shí)間段分配字清零

②　新一輪掃描課程:

　　置繼續(xù)處理標(biāo)志flag = 0

　　對(duì)課程索引值c-index = 1 ,2 , ., n 進(jìn)行以下操作:

　　如果N[c-index ] > 0 ,則做以下操作:

　　　　把segment 的值寫(xiě)入T[c-index ]的第(week - 1) 3 3～week 3 3 - 1 位中　　N[c-index ]的值減1

　　　　如果N[c-index ] > 0 ,則置flag = 1

　　　　如果week = 5 并且segment = 4

　　    則:置flag = 1 并轉(zhuǎn)③

　　否則:如果segment = 4

　　　　則:置segment = 1 且week 增1

　　　　否則:segment 增1

　　　　　　檢測(cè)是否已全部安排完畢:

　　如果flag = 1

　　則:轉(zhuǎn)②

　　否則:轉(zhuǎn)③

③　檢測(cè)是否成功:

　　如果flag = 1

　　則:開(kāi)課次數(shù)過(guò)多

　　否則:課程安排成功

④　算法結(jié)束

顯然,本算法的時(shí)間復(fù)雜度為O ( N) ( N 為每周總開(kāi)課次數(shù), 見(jiàn)(2) 式) , 而存儲(chǔ)時(shí)間段分配字所用空間為2 n 個(gè)字節(jié)( n 為課程門(mén)數(shù)) .

4 .沖突檢測(cè)算法

有時(shí)在自動(dòng)排課完畢后,需要人工調(diào)整某些課程的安排時(shí)間,如把第i 門(mén)課程在人工干預(yù)下改成星期數(shù)為week 、時(shí)間段為segment 的位置,則根據(jù)上述數(shù)據(jù)結(jié)構(gòu)需做如下運(yùn)算:

　　　　T [ i ] = T [ i ] &(～ (7 << (week - 1) * 3) ) + (segment << (week - 1)*3) ,

其中&、～ 和n 分別為按位與、按位取反和按位左移運(yùn)算符(下同) .

問(wèn)題是如何判斷是否已有其它課程安排在同一個(gè)時(shí)間段上. 設(shè)人工調(diào)整的時(shí)間段分配

字為T(mén)[1 ] ,則該問(wèn)題描述為:判斷時(shí)間段分配字T [1 ] 與{ T[2 ] , T [3 ] , ., T [ n ]} 中的某個(gè)分配字是否存在相同課程分配位上的相等的非零時(shí)間段值, 或者說(shuō){ T [2 ] , T [3 ] , .,T[ n ]} 中是否存在與T [1 ] 沖突的時(shí)間段分配字. 為簡(jiǎn)化起見(jiàn),在以下算法描述中假設(shè)所有時(shí)間段分配字的最高位為0.

算法2 　沖突檢測(cè)算法

輸入　T1 和{ T2 , ., Tn} .

輸出　與T1 沖突的{ T2 , ., Tn} 中的時(shí)間段分配字.

①　對(duì)c-index = 2 ,3 , ., n 做以下操作:

　　初始化屏蔽字mask = 7

　　對(duì)星期值week = 1 ,2 ,3 ,4 ,5 做以下操作:

　　如果T[1] & mask 等于T[c-index] & mask ,而且二者不等于0

　則: T[ 1 ]與T[c-index ]相沖突,轉(zhuǎn)①

　　mask 左移3 位(或乘8)

②　算法結(jié)束

本算法時(shí)間復(fù)雜度為O ( n) ( n 為課程門(mén)數(shù))

5.算法分析

   此算法以課程為中心，進(jìn)行搜索匹配，取最先匹配的值；具有占有空間少，運(yùn)算速度快的特點(diǎn)。但其未對(duì)數(shù)據(jù)進(jìn)行擇優(yōu)選取，所以不能對(duì)教學(xué)資源（教師、教室）合理分配，也不能滿足一些特殊要求（比如有些老師喜歡上午上課，有些老師偏向于集中式上課；有些課程安排到上午會(huì)更合適些，有些課程不能安排到上午等）。

2．2 基于優(yōu)先級(jí)的排課算法

從數(shù)學(xué)上講, 排課問(wèn)題是一個(gè)在時(shí)間、教師、學(xué)生和教室四維空間, 以教學(xué)計(jì)劃和各種特殊要求為約束條件的組合規(guī)劃問(wèn)題。其實(shí)質(zhì)就是解決各因素之間的沖突。在設(shè)計(jì)算法時(shí), 為了降低課程調(diào)度的算法復(fù)雜性, 我們主要采用了化整為零的思想及優(yōu)先級(jí)算法:

1．排課的預(yù)處理

1．等價(jià)類的劃分

將具有共同聽(tīng)課對(duì)象的任務(wù)劃分在同一等價(jià)類中, 在每個(gè)等價(jià)類之間只存在地點(diǎn)上的沖突, 而沒(méi)有時(shí)間上的沖突。 然后按照的大小, 從大到小進(jìn)行處理。 等價(jià)類的劃分可以先按年級(jí)分, 然后再按系別分, 如下 所示:

聽(tīng)課對(duì)象等價(jià)類的劃分

自控系機(jī)械系化工系管理系.

99 級(jí)N 1 子類1 子類2 子類3 子類4 .

98 級(jí)N 2 子類5 子類6 子類7 子類8 .

97 級(jí)N 3 子類9 子類10 子類11 子類12 .

96 級(jí)N 4 子類13 子類14 子類15 子類16 .

這樣, 先按年級(jí)分為四個(gè)類: 99 級(jí)(N 1) , 98 級(jí)(N 2) , 97 級(jí)(N 3) , 96 級(jí)(N 4) , 而對(duì)每一個(gè)等價(jià)類N 1、N 2、N 3、N 4 又可以按院系分為若干個(gè)子類, 然后對(duì)每個(gè)子類分別進(jìn)行排課處理, 這樣做就可以大大降低算法的復(fù)雜性

2．教室分類

為了合理使用教室, 我們采用了教室分類的辦法, 以便盡可能在課程編排過(guò)程中避免上課人數(shù)少的課程盲目強(qiáng)占容量大的教室現(xiàn)象。

首先將教室按照其類型分為若干個(gè)等價(jià)類, 如下所示,然后, 根據(jù)教室的容量再分別對(duì)每個(gè)教室等價(jià)類進(jìn)行劃分: 如分為0～ 30 人、30～ 60 人、60～90 人、90～ 120 人、120～ 180 人等若干種

　  教室等價(jià)類的劃分:

教室類型等價(jià)類R 教室類型等價(jià)類R

普通教室R1 聽(tīng)力教授R5

投影教室R2 物理實(shí)驗(yàn)室R6

多媒體教室R3 化學(xué)實(shí)驗(yàn)教室R7

制圖教室R4 計(jì)算機(jī)實(shí)驗(yàn)教學(xué)R8

3.時(shí)間預(yù)處理

1) 構(gòu)造時(shí)間模式庫(kù)

時(shí)間模式是根據(jù)教務(wù)人員的經(jīng)驗(yàn), 為各種周學(xué)時(shí)數(shù)不同的課程指定的一種時(shí)間組合方式.例如, 一門(mén)課程的周學(xué)時(shí)數(shù)為4, 那么它的時(shí)間組合方式可以有:“11”,“41”; 表示該課程一周上兩次, 分別為周一的12 節(jié)和周四的12 節(jié)L同時(shí), 為了達(dá)到較好的上課效果, 也要對(duì)這些時(shí)間模式進(jìn)行分級(jí).如下 所示

　  時(shí)間模式分級(jí)舉例

周學(xué)時(shí)優(yōu)先級(jí)周一周二周三周四周五

4 1 11 41

∶ ∶

4 2 22 43

: :

其中, 將周一至周五用數(shù)字1～ 5 表示, 上課節(jié)次: 12 節(jié)、34 節(jié)、56 節(jié)、78 節(jié)、晚12 節(jié)、晚34 節(jié)分別用數(shù)字1～ 6 表示。 例如數(shù)字“42”表示周四的34 節(jié)

這個(gè)時(shí)間單元。這樣, 對(duì)于每種周學(xué)時(shí)數(shù), 可以將所有合理的時(shí)間組合形式存入模式庫(kù)中。以便進(jìn)行時(shí)間處理時(shí)可以用時(shí)間模式庫(kù)中的各種模式進(jìn)行匹配。

2) 時(shí)間數(shù)組

為了表示班級(jí)、教師、教室的可排課時(shí)間, 分別為他們建立一維數(shù)組L例如, 某位教師的初始可排課時(shí)間數(shù)組為(123456　123456　123456　123456 123456)。 其中共有五組數(shù)據(jù), 分別表示一周中的五天; 而一組數(shù)據(jù)共有6 個(gè)字符“1、2、3、4、5、6”分別表示一天中的六個(gè)時(shí)間單元。 當(dāng)為某位教師分配時(shí)間后, 相應(yīng)的那位字符就置為0L 例如, 某位教師的可排課時(shí)間數(shù)組為( 020456 　103456 　003456 　120456　023456) , 則表示這位教師在周一的12 節(jié)和56 節(jié), 周二的34 節(jié), 周三的12 節(jié)和34 節(jié), 周四的56 節(jié), 周五的12 節(jié)已經(jīng)安排了課程, 如果要再安排課程的話, 就應(yīng)該安排在非0 的時(shí)間單元L對(duì)于班級(jí)和教室也可以進(jìn)行同樣的處理, 分別標(biāo)出可排課時(shí)間。

2．　每一子類的排課處理

在對(duì)每個(gè)子類的排課處理中, 我們結(jié)合了分治法、貪婪法、回溯法三者的思想L首先, 根據(jù)分治法的思想把整個(gè)排課過(guò)程分成時(shí)間分配和教室分配兩個(gè)階段。然后, 依據(jù)貪婪法的算法思想, 在時(shí)間分配時(shí),總是在尚未分配的時(shí)間單元中選擇上課效果最好的

單元。而在時(shí)間分配發(fā)生死鎖時(shí), 會(huì)向上回溯搜索到發(fā)生沖突的最近一個(gè)記錄, 然后對(duì)它進(jìn)行重排以解決沖突。 具體處理過(guò)程如下:

1．設(shè)定優(yōu)先級(jí)

對(duì)子類中的課程計(jì)算優(yōu)先級(jí)L設(shè)優(yōu)先級(jí)函數(shù)為:

D (g ) = J (g )*C1 + T (g ) * C2 + P (g ) * C3      ( 1 )

其中, J (g ) 表示課程級(jí)別, 選修課的課程級(jí)別設(shè)置為1, 必修課的課程級(jí)別設(shè)置為2; T (g ) 表示該課程的周學(xué)時(shí)數(shù); P (g ) 表示該課程的參與人數(shù); C1、C2、

C3 是可以調(diào)整的參數(shù)。 由式(1) 可以看出課程級(jí)別越高、周學(xué)時(shí)越多、參加人數(shù)越多的課程, 其D (g )值越大, 其優(yōu)先級(jí)也越高; 反之, D (g ) 值越小, 其優(yōu)先級(jí)越低。這樣, 就可以根據(jù)計(jì)算的優(yōu)先級(jí)的高低對(duì)課程進(jìn)行排序, 優(yōu)先級(jí)高的優(yōu)先調(diào)度。

2．查詢可用時(shí)間單元

第1 步, 初始化某門(mén)課程的最大可安排時(shí)間數(shù)組, 為( 123456 　123456 　123456 　123456 　123456)。第2 步, 找出參加該課程學(xué)習(xí)的所有班級(jí)。第3 步, 查詢每個(gè)班級(jí)的時(shí)間數(shù)組, 得到班級(jí)的已排課時(shí)間, 并將其與課程的最大時(shí)間數(shù)組相“與”, 從而得到該課程不能安排的時(shí)間單元。第4 步, 依次處理教師時(shí)間數(shù)組和相關(guān)教室時(shí)間數(shù)組, 這樣, 該課程最終的可安排時(shí)間數(shù)組就是班級(jí)、教師、教室可排課時(shí)

間的交集。

3．查找適當(dāng)?shù)臅r(shí)間模式

找到可排課時(shí)間后, 就應(yīng)根據(jù)課程的周學(xué)時(shí)數(shù)在時(shí)間模式庫(kù)中匹配適當(dāng)?shù)臅r(shí)間模式。完成以上工作后, 就確定了課程的上課時(shí)間和地點(diǎn)。如果在處理中發(fā)生死鎖, 則可根據(jù)回溯法的思想向上回溯搜索到發(fā)生沖突的最近一個(gè)記錄, 然后對(duì)它進(jìn)行重排以解決死鎖, 如果仍不能解決死鎖問(wèn)題, 則可以將該課程信息輸出到?jīng)_突列表中。

3． 人工干預(yù)的處理

計(jì)算機(jī)自動(dòng)排課也需要進(jìn)行人工干預(yù), 以便可以使得各個(gè)高校能夠根據(jù)自己的具體要求對(duì)排課算法中的一些參數(shù)進(jìn)行設(shè)置和調(diào)整, 并對(duì)計(jì)算機(jī)排出的課表進(jìn)行調(diào)整L本算法所設(shè)計(jì)的人工干預(yù)過(guò)程有:

等價(jià)類劃分中參數(shù)的設(shè)置, 教室類型的設(shè)置, 時(shí)間模式庫(kù)的設(shè)置, 優(yōu)先級(jí)函數(shù)中參數(shù)的設(shè)置。用戶可以根據(jù)自己的具體要求對(duì)這些參數(shù)和庫(kù)進(jìn)行設(shè)置。另外,對(duì)于計(jì)算機(jī)排出的課程表, 用戶也可以通過(guò)人機(jī)交互進(jìn)行適當(dāng)調(diào)整, 從而得到用戶滿意的課程表。

4．性能分析

   此算法對(duì)班級(jí)及教室劃分等價(jià)類，對(duì)學(xué)校資源進(jìn)行了合理的利用。但對(duì)一些特殊要求還是無(wú)法具體體現(xiàn)出來(lái)。

3   基于時(shí)間片優(yōu)先級(jí)排課算法描述與分析

    排課問(wèn)題實(shí)質(zhì)上是時(shí)間、教師、班級(jí)、教室、課程這五維關(guān)系的沖突問(wèn)題，要合理的解決這個(gè)問(wèn)題首先要了解排課中的一些基本原則以及排課的一些基本要求。

3．1排課中的基本原則

在課程的編排中應(yīng)遵循一定的規(guī)則, 只有按照基本規(guī)則來(lái)進(jìn)行課程的編排才能夠減少?zèng)_突的發(fā)生, 這些基本規(guī)則主要有以下幾條:

1) 同一班級(jí)的學(xué)生在同一時(shí)間(某些特定的選修課時(shí)間除外) 不能安排兩門(mén)課程

2) 同一教師在同一時(shí)間不能安排兩門(mén)課程

3) 同一教室在同一時(shí)間不能安排兩門(mén)課程

4) 同一時(shí)間安排的課程總數(shù)不能大于所能提供的教室總數(shù)

5) 某一課程參加學(xué)習(xí)的總?cè)藬?shù)不應(yīng)大于所安排教室的座位數(shù)

6) 所提供教室的屬性與課程所需教室的屬性一致

在時(shí)間、教師、班級(jí)、教室、課程這五維關(guān)系中, 時(shí)間、教師、班級(jí)三者之間存在著緊密關(guān)系。相對(duì)而言, 教室與它們關(guān)系就不那么密切。

3．2排課的基本要求

課程的安排不是任意的, 為了達(dá)到最好的教學(xué)效果應(yīng)遵循一定的要求。這些要求主要有:

1) 要盡量為所排課程安排上該類課效果最好的時(shí)間

2) 課程在一周上多次時(shí), 要有一定的間隔性

3) 公共課等涉及面廣、學(xué)時(shí)多的課程應(yīng)優(yōu)先處理

4) 對(duì)同一教師, 同一上課對(duì)象應(yīng)盡量選擇相對(duì)固定的幾個(gè)教室

5) 對(duì)同一個(gè)班級(jí)的課程應(yīng)選擇相對(duì)固定的教室

6) 連著的課的教室選擇不應(yīng)相隔太遠(yuǎn)

7）同一天有幾門(mén)課時(shí)盡量把課分散

8) 優(yōu)先滿足一些特殊要求（比如有些教室喜歡上上午的課，可以優(yōu)先滿足）

3．3基于時(shí)間片優(yōu)先級(jí)排課算法描述

在描述算法之前我們把一些概念先講清楚。在這里我們把從行政角度分的班叫自然班，把在同一個(gè)教室上課的班叫做排課班。在大學(xué)里有些公共課是幾個(gè)排課班通過(guò)多媒體來(lái)一起上的，我們把這個(gè)排課班的總和叫做公共班。班級(jí)、教室、教師、課程都維護(hù)著自己的一張課表。對(duì)課表的每個(gè)表元（如星期一的第一節(jié)課）在這里稱做時(shí)間片。

基于時(shí)間片優(yōu)先級(jí)排課算法以排課班為單位，圍繞著各對(duì)像(自然班、教室、教室)的時(shí)間表選擇合適的時(shí)間片。

  本文關(guān)鍵詞：排課算法，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：42885