湖北經(jīng)濟(jì)學(xué)院本科畢業(yè)生畢業(yè)論文(畢業(yè)設(shè)計(jì)) 開題報(bào)告書

1、湖北經(jīng)濟(jì)學(xué)院本科畢業(yè)生畢業(yè)論文（畢業(yè)設(shè)計(jì)）開 題 報(bào) 告 書題目 自動(dòng)排課系統(tǒng)的研究與實(shí)現(xiàn) 指導(dǎo)教師姓名及職稱 講師 學(xué)生姓名 李紅衛(wèi) 所屬院系 計(jì)算機(jī)技學(xué)與技術(shù)學(xué)院 專業(yè)名稱 軟件工程 班級(jí)名稱 軟件Q0341 開題時(shí)間 年 月 日 湖北經(jīng)濟(jì)學(xué)院本科畢業(yè)生畢業(yè)論文（畢業(yè)設(shè)計(jì)）開題報(bào)告書姓 名李紅衛(wèi)專業(yè)和班級(jí)軟件Q0341開題時(shí)間題 目自動(dòng)排課系統(tǒng)的研究與實(shí)現(xiàn)一、題目來(lái)源及研究的理論與實(shí)際意義課程的安排是學(xué)校教學(xué)系統(tǒng)中的一個(gè)重要環(huán)節(jié),是維護(hù)學(xué)校教學(xué)秩序正常進(jìn)行的重要保證。隨著在校學(xué)生的增多,課程類別的多樣化,學(xué)生選課的自由度增加,使得課程的安排工作日益復(fù)雜和繁瑣,所以學(xué)校課程安排的合理與否直接

2、體現(xiàn)了教務(wù)部門的工作效率和學(xué)校的教學(xué)質(zhì)量。目前使用計(jì)算機(jī)進(jìn)行自動(dòng)排課,可以使教務(wù)管理人員迅速掌握全校教學(xué)情況,提高教務(wù)管理工作的效率,加快其現(xiàn)代化進(jìn)程,可以看出加強(qiáng)學(xué)校的課程安排工作對(duì)學(xué)校教務(wù)管理工作具有非常重要的意義。傳統(tǒng)的人工進(jìn)行排課，最令人擔(dān)心的問(wèn)題就是出現(xiàn)教室資源沖突或教師資源沖突的情況，而且工作繁瑣，工作量巨大,尤其是在給大學(xué)校園進(jìn)行排課時(shí)出現(xiàn)的問(wèn)題更多。計(jì)算機(jī)軟件技術(shù)應(yīng)用于學(xué)校的課程安排是發(fā)展的必然。充分發(fā)揮計(jì)算機(jī)的優(yōu)勢(shì)，將大量復(fù)雜的判斷與運(yùn)算交給計(jì)算機(jī)來(lái)做，是真正意義上的人腦的“減負(fù)”。 教師設(shè)置好學(xué)?；厩闆r及排課要求，讓計(jì)算機(jī)排出課程表，適度調(diào)課后的課表就能滿意地應(yīng)用于新的學(xué)

3、期。雖然當(dāng)前已經(jīng)出現(xiàn)了許多采用不同算法設(shè)計(jì)的自動(dòng)排課系統(tǒng)，但它們普遍存在著不足：或因適用范圍太廣而導(dǎo)致操作復(fù)雜，需手工輸入排課信息太多；或因適用范圍窄而導(dǎo)致排完課后仍需人工調(diào)整，既耗時(shí)且排課質(zhì)量差。市場(chǎng)流行的排課系統(tǒng)很多，比如：相似排課CIS，plsn智能排課系統(tǒng)，正信華課程安排管理系統(tǒng)，排課博士，排課高手,水晶排課等等。這些排課軟件在解決排課問(wèn)題時(shí)大多數(shù)采用的算法都是回溯算法，排課的效果也都很好。利用回溯算法解決問(wèn)題的思路是先選擇某一可能的線索進(jìn)行試探，每一步試探都有多種方式，將每一方式都一一試探，如有問(wèn)題就返回糾正，反復(fù)進(jìn)行這種試探再返回糾正，直到得出全部符合條件的答案或是問(wèn)題無(wú)解為止。這

4、種解決問(wèn)題的方法就是回溯法?；厮菟惴▽?duì)空間的消耗較少，當(dāng)其與分枝定界法一起使用時(shí)，對(duì)于所求解在解答樹中層次較深的問(wèn)題有較好的效果。但應(yīng)避免在后繼節(jié)點(diǎn)可能與前繼節(jié)點(diǎn)相同的問(wèn)題中使用，以免產(chǎn)生循環(huán)。二、國(guó)內(nèi)外相關(guān)研究成果及研究動(dòng)態(tài)綜述排課問(wèn)題早在70年代就證明是一個(gè)NP完全問(wèn)題，即算法的計(jì)算時(shí)間是呈指數(shù)增長(zhǎng)的，這一論斷確立了排課問(wèn)題的理論深度。對(duì)于NP完全問(wèn)題目前在數(shù)學(xué)上沒(méi)有一個(gè)通用的算法能夠很好地解決，然而很多NP完全問(wèn)題具有很重要的實(shí)際意義。目前大家對(duì)NP完全問(wèn)題研究的主要思想是如何降低其計(jì)算復(fù)雜度，即利用一個(gè)近似算法來(lái)代替，力爭(zhēng)使得解決問(wèn)題的時(shí)間從指數(shù)增長(zhǎng)化簡(jiǎn)到多項(xiàng)式增長(zhǎng)。結(jié)合到課表問(wèn)題就是

5、建立一個(gè)合適的現(xiàn)實(shí)簡(jiǎn)約模型，利用該簡(jiǎn)約模型能夠大大降低算法的復(fù)雜度，便于程序?qū)崿F(xiàn)，這是解決排課問(wèn)題一個(gè)主要的思路。進(jìn)入九十年代以后，國(guó)外對(duì)課表問(wèn)題的研究仍然十分活躍。比較有代表的有印度 V a s t a p u r 大學(xué)管理學(xué)院的ArabindaTripathy、加拿大Montreal大學(xué)的JeanAubin和JacquesFerland等。目前，解決課表方法的問(wèn)題有:模擬手工排課法、圖論方法、拉格朗日法、二次分配型法等多種方法。由于課表約束復(fù)雜，用數(shù)學(xué)方法進(jìn)行描述時(shí)往往導(dǎo)致問(wèn)題規(guī)模劇烈增大，這已經(jīng)成為應(yīng)用數(shù)學(xué)編程解決課表問(wèn)題的巨大障礙。國(guó)外的研究表明，解決大規(guī)模課表編排問(wèn)題單純靠數(shù)學(xué)方法是

6、行不通的，而利用運(yùn)籌學(xué)中分層規(guī)劃的思想將問(wèn)題分解，將是一個(gè)有希望獲得成功的辦法。在國(guó)內(nèi)，對(duì)課表問(wèn)題的研究開始于80年代初期，具有代表性的有:南京工學(xué)院的UTS（SAUniversityTimetableSchedulingSystem）系統(tǒng)，清華大學(xué)的TISER（TimetableSchedulER）系統(tǒng)，大連理工大學(xué)的智能教學(xué)組織管理與課程調(diào)度等，這些系統(tǒng)大多數(shù)都是模擬手工排課過(guò)程，以“班”為單位，運(yùn)用啟發(fā)式函數(shù)來(lái)進(jìn)行編排的。但是這些課表編排系統(tǒng)往往比較依賴于各個(gè)學(xué)校的教學(xué)體制，不宜進(jìn)行大量推廣。從實(shí)際使用的情況來(lái)看，國(guó)內(nèi)外研制開發(fā)的這些軟件系統(tǒng)在實(shí)用性上仍不盡如人意。一方面是作為一個(gè)很復(fù)雜

7、的系統(tǒng)，排課要想面面俱到是一件很困難的事；另一方面每個(gè)學(xué)校由于其各自的特殊性，自動(dòng)排課軟件很難普遍使用，特別是在調(diào)度過(guò)程中一個(gè)很小的變動(dòng)，要會(huì)引起全部課程的大調(diào)整，也就意味著全校課程大變動(dòng)，在實(shí)際的應(yīng)用中這是很難實(shí)現(xiàn)的事。排課是每一所學(xué)校都會(huì)面臨的繁重作業(yè),且通常是校務(wù)計(jì)算機(jī)化中最難解決的一環(huán)。如何將排課的資源與其限制進(jìn)行妥善而令人滿意的調(diào)度安排,是排課作業(yè)的基本要求與目標(biāo)。迄今為止,對(duì)課程表的研究工作已經(jīng)進(jìn)行了長(zhǎng)達(dá)40多年之久,取得了豐碩的成果。但是,仍然存在許多困難,例如規(guī)模大、約束條件復(fù)雜以及規(guī)律不斷變化等,因此課程表問(wèn)題至今仍未完全解決。比較常用的算法有: 貪心算法, 回溯算法, 動(dòng)態(tài)

8、規(guī)劃法。比較流行的算法有: 基于優(yōu)先級(jí)的排課算法和遺傳算法。近年來(lái), 遺傳算法用于排課成為熱門, 許多國(guó)內(nèi)外的學(xué)者進(jìn)入了這個(gè)領(lǐng)域。三、主要研究?jī)?nèi)容1分析現(xiàn)有排課算法, 總結(jié)出其優(yōu)缺點(diǎn)。2在現(xiàn)在算法的基礎(chǔ)上, 設(shè)計(jì)出自己的排課算法,。3實(shí)現(xiàn)該排課算法, 并加以圖形化的實(shí)現(xiàn)。四、本研究的關(guān)鍵創(chuàng)新點(diǎn)、研究方法、研究進(jìn)度計(jì)劃和完成時(shí)間1研究的關(guān)鍵創(chuàng)新點(diǎn): 采用回溯算法和碰撞檢測(cè)的思想, 將排課問(wèn)題轉(zhuǎn)為排列問(wèn)題, 為約束建立碰撞檢測(cè)函數(shù), 便于系統(tǒng)的擴(kuò)充。2研究方法: 查閱文獻(xiàn)資料, 在了解現(xiàn)在流行的排課算法的基礎(chǔ)上設(shè)計(jì)出自己的排課算法。寫出算法的偽代碼, 并寫出排課關(guān)鍵代碼, 并測(cè)試,。 待通過(guò)后選擇圖形化開發(fā)工具, 參看別人做好的排課系統(tǒng)界面, 取長(zhǎng)補(bǔ)短, 設(shè)計(jì)出自己的界面, 然后添加實(shí)現(xiàn)代碼。3研究進(jìn)度計(jì)劃和完成時(shí)間 五、主要參考文獻(xiàn)1黃玉波 基于空間的合理排課算法分析J. 科技廣場(chǎng),2007,(1). 2殷榮慶 高校排課算法的分析與設(shè)計(jì)J. 安徽教育學(xué)院學(xué)報(bào),2006,(6). 3陳強(qiáng) 通用高校排課算法研究J. 科技廣場(chǎng),2006,(7). 4田嶺 大學(xué)自動(dòng)排課算法設(shè)計(jì)與實(shí)現(xiàn)J. 教育信息化,2006,(13). 5張慧蘭,羅家國(guó),張?zhí)?基于校院兩級(jí)任務(wù)的計(jì)算機(jī)排課算法研究J. 南方冶金學(xué)院學(xué)報(bào),2006,(1). 6