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

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

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

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

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

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

6、., Cn 中所列順序安排完各門課程之后(每門課安排 1 次 ,再按該順序繼續(xù)向后面的時間段進行安排,直到所有課程的開課次數符合 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ù)處理標志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 并轉否則:如果segment = 4則:置segment = 1 且week 增1否則:segment 增1檢測是否已全部安排完畢:如果flag = 1則:

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