- 相關(guān)推薦
自動排課算法的分析論文
摘 要：隨著我國教育事1業(yè)的不斷發(fā)展，課程編排問題在很大的程度上影響著學(xué)校教學(xué)質(zhì)量的提高。近些年來，政府對教育事業(yè)的投入也是逐年加大，可見對教育事業(yè)的重視。為了保證教學(xué)的質(zhì)量，學(xué)校應(yīng)該制定出嚴(yán)密合理和規(guī)范的課程安排，課程的編制過程是十分復(fù)雜和繁重的。下面我們就分析一下排課研究的意義，如今排課問題的現(xiàn)狀，以及現(xiàn)有的幾種排課算法，詳細(xì)地分析一下排課算法，
關(guān)鍵詞：自動排課；排課算法；自動排課算法
1.排課算法研究的意義
不管是小初高還是大學(xué)，靠老師教課來學(xué)習(xí)還是占主要的部分，這是培養(yǎng)學(xué)生的主要途徑。在學(xué)期開始的時候，學(xué)校都會給每人發(fā)一張課程表，學(xué)生還有老師都是按照課程表來進(jìn)行計劃。一張課程表打印出來十分簡單，但是想把課程安排的緊湊合格，管理人員是需要下很大苦工的。新學(xué)期開始前學(xué)校的管理人員都要整理教學(xué)計劃，根據(jù)教學(xué)計劃下教學(xué)任務(wù)書，然后結(jié)合教學(xué)計劃和任務(wù)開始編排課程。這個編排過程是繁重而關(guān)鍵的，因為在這些教學(xué)調(diào)度過程中，不僅有大量繁瑣的數(shù)據(jù)整理工作，還有嚴(yán)謹(jǐn)思維的腦力勞動，需要填寫并打印大量的表格。
21世紀(jì)以來，信息技術(shù)突飛猛進(jìn)，計算機排課慢慢取代了手工排課，這一技術(shù)的發(fā)明大大減輕了管理人員的工作量，而且采用計算機排課有利于學(xué)校對老師教學(xué)貢獻(xiàn)的評估，有利于優(yōu)化學(xué)生的學(xué)習(xí)過程，也有利于學(xué)校領(lǐng)導(dǎo)決策更合理化，最為重要的是有利于學(xué)校教學(xué)質(zhì)量的提高。
2.排課的現(xiàn)狀分析
在國外很早就有人研究課程編排問題，在 1962年，Gotlieb提出了一個課表問題的數(shù)學(xué)模型，他利用匈牙利算法解決了三維線性運輸問題。然后，人們對課表問題的算法、解的存在性等方面做了許多深入探討。近40年來，在計算機新技術(shù)的基礎(chǔ)上，人們又進(jìn)行了不斷地嘗試，并取得一些成效。如1965年，Mihoc和Balas將課表公式化為了一個優(yōu)化問題；Krawczk提出了一種線性編程的方法；Junginger將課表問題簡化為一個三維運輸問題。最近幾年，我們在課程編排方面已經(jīng)取得了一些成績，但是對于多數(shù)學(xué)校而言，這種課表編排還不具備實用價值，只能在極為簡單的情況下才能實現(xiàn)。
然而，人們并沒有放棄研究課表問題，在九十年代，國外在課表問題研究方面的主要代表人物有加拿大Montreal大學(xué)的Jean Aubin和Jacques Ferland、印度的Vastapur大學(xué)管理學(xué)院的ArabindaTripathy等。我國對課表問題的研究是開始于80年代初期，具有代表性的是南京工學(xué)院的UTSS（A University Timetable Scheduling System）系統(tǒng)，清華大學(xué)的TISER（Timetable SchedulER）系統(tǒng)，大連理工大學(xué)的智能教學(xué)組織管理與課程調(diào)度等。
不管是國外研究還是國內(nèi)的研究，從實際使用情況來看，國內(nèi)外研制開發(fā)的軟件系統(tǒng)都不是很實用，比如，我國研制的系統(tǒng)，這些系統(tǒng)大多是模擬手工排課過程的。這種系統(tǒng)課表編排經(jīng)實踐證明是不適合進(jìn)行大量推廣的，因為它過于依賴各個學(xué)校的教學(xué)體制，限制性較大。另外，排課系統(tǒng)本來就是很復(fù)雜的，排課很難做到面面俱到，而且，每個學(xué)校都有其特殊性，如果是想要改動某個地方，有可能使全部的課程發(fā)生大調(diào)整，這就是說全校的課程都會發(fā)生變動，在實際應(yīng)用中我們會發(fā)現(xiàn)這是很難實現(xiàn)的。
經(jīng)過長時間的研究，目前解決課表方法的問題有：模擬手工排課法，圖論方法，拉格朗日法，二次分配型法等多種方法。在排課算法上，目前，人們已經(jīng)研制出了幾種，比較流行的是自動排課算法和基于時間片優(yōu)先級的排課算法。下面我們主要介紹詳細(xì)一下自動排課算法。
3.自動排課算法
3.1問題的簡化描述
設(shè)要安排的課程為{ C1 , C2 , ., Cn} ,課程的總數(shù)設(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é)，在以下我們將4次教學(xué)課程分別稱第1 、2 、3 、4 時間段 .這樣，在這種假設(shè)下,每周的教學(xué)總時間的段數(shù)就是5 ×4 = 20 ，如以下這種表達(dá)方式:
n ≤20 , (1)
N = 6n， i =1， Ni ≤20. (2)
我們要思考的就是如何設(shè)計出恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和算法, 從而確定{ C1 , C2 , ., Cn } 中每個課程的教學(xué)應(yīng)該占據(jù)的時間段,還得保證美個時間段只能由一門課程占據(jù).
3.2主要數(shù)據(jù)結(jié)構(gòu)
對于每一門課程,分配2 個字節(jié)的"時間段分配字" :{ T1 , T2 , ., Tn} . 每個時間段分配字(假設(shè)為Ti )的格式為:
Ti 的數(shù)據(jù)類型C 語言格式定義為:unsigned int . 以Ti的最高位來表示該課程是否有效，如果是0的話表示有效，1的話則表示無效。其他的被稱為課程分配位，每個分配位占連續(xù)的3 個位，這里的位就是bit，用來表示星期一到星期五所安排課程的時間段的值，0是表示當(dāng)日沒有排課，1～4是表示課程所安排的相應(yīng)的時間段，如果值大于4的話就表示無效。
這樣的話，小于32 768 (十六進(jìn)制8000)就是有效的時間段分配字的值，大于等于32 768 的時間段分配字則是對應(yīng)無效的課程。
3.3排課算法
在上述假設(shè)下,我們可以看出，自動排課算法的目標(biāo)就是確定{ C1 , C2 , ., Cn} 所對應(yīng)的{ T1 , T2 , ., Tn} .
假設(shè)成立的話,我們發(fā)現(xiàn)一共可有20 !/ (20 - N) !種排法 . 假設(shè)一共有4 門課,每門課一個星期上2 次,則N = 8 ,就是說這8 次課安排的方法就可能會有20 !/ (20 - 8) ! = 5 079 110 400 ,即50 多億種.在這種多可能性的情況下，排課必須有一個確定的排課標(biāo)準(zhǔn)，這樣才能節(jié)省時間，提高效率。一般情況下我們會采用輪轉(zhuǎn)分配法來進(jìn)行:首先從星期一開始就按{ C1 , C2 , ., Cn} 中的相應(yīng)順序來安排課程，每門課程安排1 次,之后再按這樣的順序繼續(xù)排后面的課程,直到所有課程的開課次數(shù)都與{ N1 , N2 , ., Nn} 中給定的值相符合. 在算法描述中用{ C[1 ] , C[2 ] , ., C[ n ]} 表示{ C1 , C2 , ., Cn} ，{ N1 , N2 , ., Nn}以及{ T1 , T2 , ., Tn}。
3.4算法的優(yōu)缺點分析
優(yōu)點：這個算法是以課程為中心的，然后進(jìn)行搜索匹配，取得最先匹配的值；它具有占有空間少，運算速度快這兩個特點。
缺點：該算法無法對數(shù)據(jù)進(jìn)行擇優(yōu)選取，所以不無法合理分配學(xué)校的教學(xué)資源，并不能滿足一些特殊要求，比如說有些老師喜歡上午上課，有些老師偏向于組織集體上課；有些課程安排到上午會更合適些，有些課程不能安排到上午等。
參考文獻(xiàn)：
[1]蔡啟明,吳新民;基于中小學(xué)校園網(wǎng)的自動排課系統(tǒng)的分析和設(shè)計[J];電化教育研究;2003年03期
[2]祝勇仁;鄧勁蓮;胡獻(xiàn)華;張煒;;排課問題的一種遺傳算法適應(yīng)度求解方法[A];第四屆中國軟件工程大會論文集[C];2007年
【自動排課算法的分析論文】相關(guān)文章：
案例分析論文11-07
本科論文目錄自動生成11-15
論文的可行性分析02-21
淺論軟件需求分析的論文11-10
論文的問卷分析報告范文11-05
案例分析論文15篇11-09
案例分析論文(15篇)11-10
論文參考文獻(xiàn)自動編號11-16
論文參考文獻(xiàn)自動生成10-26