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

1 .問題的描述

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

設(shè)要安排的課程為{ C1 , C2 , ., Cn} ,課程總數(shù)為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)排課問題是:設(shè)計(jì)適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和算法, 以確定{ C1 , C2 , ., Cn } 中每個(gè)課程的教學(xué)應(yīng)占據(jù)的時(shí)間段,并且保證任何一個(gè)時(shí)間段僅由一門課程占據(jù).

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

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

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)停課/ 開課處理.

3 .排課算法

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

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

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

　　否則:課程安排成功

④　算法結(jié)束

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

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

有時(shí)在自動(dòng)排課完畢后,需要人工調(diào)整某些課程的安排時(shí)間,如把第i 門課程在人工干預(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)算符(下同) .

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

字為T[1 ] ,則該問題描述為:判斷時(shí)間段分配字T [1 ] 與{ T[2 ] , T [3 ] , ., T [ n ]} 中的某個(gè)分配字是否存在相同課程分配位上的相等的非零時(shí)間段值, 或者說(shuō){ T [2 ] , T [3 ] , .,T[ n ]} 中是否存在與T [1 ] 沖突的時(shí)間段分配字. 為簡(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 為課程門數(shù))

5.算法分析

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

總結(jié)

以上是生活随笔為你收集整理的排课软件的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。