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

1、2 目前流行的幾種排課算法的介紹21. 自動(dòng)排課算法1 .問題的描述我們討論的自動(dòng)排課問題的簡化描述如下:1 , C2 , ., Cn ,課程總數(shù)為n , 而各門課程每周安排次數(shù)(每次為連續(xù)的2 學(xué)時(shí)) 為 N1 , N2 , ., Nn 教學(xué)日最多安排4 次課程教學(xué),即1 2 節(jié)、3 4 節(jié)、5 6 節(jié)和7 8 節(jié)(以下分別稱第1 、2 、種假設(shè)下,顯然每周的教學(xué)總時(shí)間段數(shù)為5 ×4 = 20 ,并存在以下約束關(guān)系:n 20 , (1)? N = 6n， i =1， Ni 20. (2)適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和算法, 以確定 C1 , C2 , ., Cn 中每個(gè)課程的教學(xué)應(yīng)占據(jù)的時(shí)間段,

2、并且保證任何一個(gè)時(shí)據(jù).2 .主要數(shù)據(jù)結(jié)構(gòu)配2 個(gè)字節(jié)的“時(shí)間段分配字”(無符號(hào)整數(shù)) : T1 , T2 , ., Tn . 其中任何一個(gè)時(shí)間段分配字(假設(shè)為Ti 格式定義為:unsigned int . Ti 的最高位是該課程目前是否是有效的標(biāo)志,0 表示有效,1 表示無效(如停課等)占連續(xù)的3 個(gè)位(bit) ,表示某教學(xué)日(星期一 星期五) 安排該課程的時(shí)間段的值,0 表示當(dāng)日未安排,1 時(shí)間段(超過4 的值無效) .時(shí)間段分配字的值應(yīng)小于32 768 (十六進(jìn)制8000) , 而大于等于32 768 的時(shí)間段分配字對(duì)應(yīng)于那些當(dāng)前無配位已設(shè)置好也如此) , 因此很容易實(shí)現(xiàn)停課/ 開課處理

3、.3 .排課算法在上述假設(shè)下,自動(dòng)排課算法的目標(biāo)就是確定 C1 , C2 , ., Cn 所對(duì)應(yīng)的 T1 , T2 , ., Tn .共有(即有A（20，（N-20）)20 !/ (20 - N) !種排法( N 的含義見(2) 式) . 如果有4 門課,每門課一周上就會(huì)有20 !/ (20 - 8) ! = 5 079 110 400 ,即50 多億種. 如果毫無原則地在其中選擇一種方案,將會(huì)耗費(fèi)巨確定的排課原則. 我們采用輪轉(zhuǎn)分配法作為排課原則:從星期一第1 時(shí)間段開始按 C1 , C2 , ., Cn 中所列 ,再按該順序繼續(xù)向后面的時(shí)間段進(jìn)行安排,直到所有課程的開課次數(shù)符合 N1 ,

4、N2 , ., Nn 中給定的值用 C1 , C2 , ., 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)行以下操作:如果Nc-index &g

5、t; 0 ,則做以下操作:把segment 的值寫入Tc-index 的第(week - 1) 3 3week 3 3 - 1 位中 Nc-index 的值減如果Nc-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則:開課次數(shù)過多否則:課程安排成功 算法結(jié)束時(shí)間復(fù)雜度為O ( N) ( N 為每周總開課次數(shù), 見(2) 式

6、) , 而存儲(chǔ)時(shí)間段分配字所用空間為2 n 個(gè)字節(jié)( n4 .沖突檢測(cè)算法后,需要人工調(diào)整某些課程的安排時(shí)間,如把第i 門課程在人工干預(yù)下改成星期數(shù)為week 、時(shí)間段為segment據(jù)結(jié)構(gòu)需做如下運(yùn)算:T i = T i &( (7 << (week - 1) * 3) ) + (segment << (week - 1)*3) ,其中&、 和n 分別為按位與、按位取反和按位左移運(yùn)算符(下同) .問題是如何判斷是否已有其它課程安排在同一個(gè)時(shí)間段上. 設(shè)人工調(diào)整的時(shí)間段分配描述為:判斷時(shí)間段分配字T 1 與 T2 , T 3 , ., T n 中的某個(gè)分

7、配字是否存在相同課程分配, T 3 , .,T n 中是否存在與T 1 沖突的時(shí)間段分配字. 為簡化起見,在以下算法描述中假設(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 做以下操作:如果T1 & mask 等于Tc-index & mask ,而且二者不等于0則: T 1 與Tc-index 相沖突,轉(zhuǎn)mask 左移3 位(或乘8) 算法結(jié)束本算法時(shí)間復(fù)

8、雜度為O ( n) ( n 為課程門數(shù))5.算法分析，進(jìn)行搜索匹配，取最先匹配的值；具有占有空間少，運(yùn)算速度快的特點(diǎn)。但其未對(duì)數(shù)據(jù)進(jìn)行擇優(yōu)選取，所也不能滿足一些特殊要求（比如有些老師喜歡上午上課，有些老師偏向于集中式上課；有些課程安排到上程不能安排到上午等）。22 基于優(yōu)先級(jí)的排課算法是一個(gè)在時(shí)間、教師、學(xué)生和教室四維空間, 以教學(xué)計(jì)劃和各種特殊要求為約束條件的組合規(guī)劃問題。其實(shí)的沖突。在設(shè)計(jì)算法時(shí), 為了降低課程調(diào)度的算法復(fù)雜性, 我們主要采用了化整為零的思想及優(yōu)先級(jí)算法:1排課的預(yù)處理1等價(jià)類的劃分任務(wù)劃分在同一等價(jià)類中, 在每個(gè)等價(jià)類之間只存在地點(diǎn)上的沖突, 而沒有時(shí)間上的沖突。 然后按

9、照的大小等價(jià)類的劃分可以先按年級(jí)分, 然后再按系別分, 如下 所示:聽課對(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 .個(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教室分類用教室, 我們采用了教室分類的辦法, 以便盡可能在課程編排過程中避免上課人數(shù)少的課程盲目強(qiáng)占容量大的分為若干個(gè)等價(jià)類, 如下所示,然后,