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