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

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

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

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

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

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

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

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

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