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

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

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

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

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

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

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

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

8、規(guī)劃法。比較流行的算法有: 基于優(yōu)先級的排課算法和遺傳算法。近年來, 遺傳算法用于排課成為熱門, 許多國內(nèi)外的學者進入了這個領(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. 安徽教育學院學報,2006,(6). 3陳強 通用高校排課算法研究J. 科技廣場,2006,(7). 4田嶺 大學自動排課算法設(shè)計與實現(xiàn)J. 教育信息化,2006,(13). 5張慧蘭,羅家國,張?zhí)?基于校院兩級任務的計算機排課算法研究J. 南方冶金學院學報,2006,(1). 6