教務(wù)處排課系統(tǒng)建模-

1、教務(wù)處排課系統(tǒng)建模摘要:為解決教務(wù)處排課系統(tǒng)選課問題,通過對問題的分析,設(shè)計解決問題的主要數(shù)據(jù)結(jié)構(gòu),再設(shè)計出算法程序,從時間、教師、周開課次數(shù)、沖突檢測及解決等方面處理排課問題。關(guān)鍵詞:排課系統(tǒng),數(shù)據(jù)結(jié)構(gòu),算法,沖突檢測,建模。每年開學(xué)時需要選課,有時排課系統(tǒng)會出現(xiàn)各種各樣的問題,一部分是因為排課系統(tǒng)本身的算法問題。設(shè)計一個合理算法對于學(xué)生選課方便至關(guān)重要,以下是一個排課系統(tǒng)的介紹。1.排課系統(tǒng)的基本要求:1.必修課盡可能的排在上午;例如,數(shù)學(xué)、英語、專業(yè)課等安排在上午,而體育、計算機、實驗等安排在下午。2.一個教師如果上午連續(xù)上四節(jié)課,盡可能的將四節(jié)課都安排在一個教室;3.一周上多次的課程盡

2、可能間隔至少一天,比如高數(shù),如果一周上六節(jié)課,則盡可能安排周1、3、5上午上課;因此同一節(jié)的課程一周最多上六節(jié)課,且只能在周一、周三、周五。4.同一專業(yè)的課程不能有沖突。2. 問題的描述:根據(jù)排課的優(yōu)先級,應(yīng)該先將全校各個專業(yè)本學(xué)期的專業(yè)課安排好,再考慮教師的教學(xué)問題,即如果某一個教師某天上午或下午連續(xù)教四節(jié)課,確保后一節(jié)課的教室號與前一節(jié)相同。判斷同一課程一周上幾次,一次則可以在五天中無課程的時間中隨機抽取一天安排課程,兩次則可以分為周一和周三、周二和周四、周三和周五三周時間來排課,三次則只能是周一、周三、周五一種排課時間。3.基本算法的描述:設(shè)要安排的課程為 C1 , C2 , ., Cn

3、 ,課程總數(shù)為n , 而各門課程每周安排次數(shù)為 N1 , N2 , ., Nn ;每周教學(xué)日共5 天,即星期一至星期五;每個教學(xué)日最多安排4 次課程教學(xué),即1 2 節(jié)、3 4 節(jié)、5 6 節(jié)和7 8 節(jié)(以下分別稱第1 、2 、3 、4 時間段 . 在這種假設(shè)下,顯然每周的教學(xué)總時間段數(shù)為5 ×4 = 20 ,并存在以下約束關(guān)系:n 20 (1N = 6n,i =1,Ni 20 (2自動排課問題是:設(shè)計適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和算法, 以確定 C1 , C2 , , Cn 中每個課程的教學(xué)應(yīng)占據(jù)的時間段,并且保證任何一個時間段僅由一門課程占據(jù).4.主要數(shù)據(jù)結(jié)構(gòu)對于每一門課程,分配2 個字節(jié)的“

4、時間段分配字”(無符號整數(shù) : T1 , T2 , ., Tn . 其中任何一個時間段分配字(假設(shè)為Ti 都具有如下格式: Ti 的數(shù)據(jù)類型C為:unsigned int 。Ti 的最高位是該課程目前是否是有效的標(biāo)志,0 表示有效,1 表示無效(如停課等 ;其它各位稱為課程分配位, 每個課程分配位占連續(xù)的3 個位(bit ,表示某教學(xué)日(星期一星期五 安排該課程的時間段的值,0 表示當(dāng)日未安排,1 4 表示所安排的相應(yīng)的時間段(超過4 的值無效 .在這種設(shè)計下, 有效的時間段分配字的值應(yīng)小于32 768 (十六進制8000 , 而大于等于32 768 的時間段分配字對應(yīng)于那些當(dāng)前無效的課程(既

5、使課程分配位已設(shè)置好也如此 , 因此很容易實現(xiàn)停課/ 開課處理. 5.排課算法在上述假設(shè)下,自動排課算法的目標(biāo)就是確定 C1 , C2 , ., Cn 所對應(yīng)的 T1 , T2 , ., Tn .從安排的可能性上看,共有20 !/ (20 - N !種排法。如果有4 門課,每門課一周上2 次,則N = 8 ,這8 次課可能的安排方法就會有20 !/ (20 - 8 ! = 5 079 110 400 ,即50 多億種. 如果毫無原則地在其中選擇一種方案,將會耗費巨大量的時間. 所以排課的前提是必須有一個確定的排課原則。采用輪轉(zhuǎn)分配法作為排課原則:從星期一第1 時間段開始按 C1 , C2 ,

6、., Cn 中所列順序安排完各門課程之后(每門課安排 1 次 ,再按該順序繼續(xù)向后面的時間段進行安排,直到所有課程的開課次數(shù)符合 N1 , N2 , ., Nn 中給定的值為止. 在算法描述中將用 C1 , C2 , ., C n 表示 C1 , C2 , ., Cn , 對 N1 , N2 , ., Nn和 T1 , T2 , ., Tn 也采用同樣的表示法.算法1 排課算法輸入 C1 , C2 , ., Cn 、 N1 , N2 , ., Nn .輸出 T1 , T2 , ., Tn .初始化:星期值week = 1時間段值segment = 1 T 1 , T 2 , ., T n 中各

7、時間段分配字清零新一輪掃描課程:置繼續(xù)處理標(biāo)志flag = 0對課程索引值c-index = 1 ,2 , ., n 進行以下操作:如果Nc-index > 0 ,則做以下操作:把segment 的值寫入Tc-index 的第(week - 1 3 3week 3 3 - 1 位中Nc-index 的值減1如果Nc-index > 0 ,則置flag = 1如果week = 5 并且segment = 4則:置flag = 1 并轉(zhuǎn)否則:如果segment = 4則:置segment = 1 且week 增1否則:segment 增1檢測是否已全部安排完畢:如果flag = 1則:

8、轉(zhuǎn)否則:轉(zhuǎn)檢測是否成功:如果flag = 1則:開課次數(shù)過多否則:課程安排成功算法結(jié)束6.沖突檢測算法有時在自動排課完畢后,需要人工調(diào)整某些課程的安排時間,如把第i 門課程在人工干預(yù)下改成星期數(shù)為week 、時間段為segment 的位置,則根據(jù)上述數(shù)據(jù)結(jié)構(gòu)需做如下運算:T i = T i &(7 << (week - 1 * 3 + (segment << (week - 1*3 ,其中&、和n 分別為按位與、按位取反和按位左移運算符(下同 .問題是如何判斷是否已有其它課程安排在同一個時間段上. 設(shè)人工調(diào)整的時間段分配字為T1 ,則該問題描述為:判斷時間段分配字T 1 與 T2 , T 3 , ., T n 中的某個分配字是否存在相同課程分配位上的相等的非零時間段值, 或者說 T 2 , T 3 , .,T n 中是否存在與T 1 沖突的時間段分配字. 為簡化起見,在以下算法描述中假設(shè)所有時間段分配字的最高位為0.算法2 沖突檢測算法輸入T1 和 T2 , ., Tn .輸出與T1 沖突的 T2 , ., Tn 中的時間段分配字.對c-index = 2 ,3 , ., n 做以下操作:初始化屏蔽字mask = 7對星期值week = 1 ,2 ,3 ,4 ,5 做以下操作:如果T1 &