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