基于Web的高校考試自動安排算法研究與系統(tǒng)設(shè)計.pdf

1、考試安排一直是高校教務(wù)管理系統(tǒng)中一項繁重的任務(wù)。隨著現(xiàn)代教育事業(yè)的不斷發(fā)展，實現(xiàn)計算機智能化管理是學(xué)校管理工作的一項重要內(nèi)容?？荚嚂r間的安排屬于著名的時間表問題TTP(Timetabling Problem)。TTP問題已經(jīng)被廣泛應(yīng)用于學(xué)校課程和考試的時間安排(Examination Timetabling Problem，簡稱ETP問題)、各類大型會議、體育比賽、航班(火車、飛機、輪船等)時刻表的制定等。1975年S.Eveo等人論證

2、了時間表問題屬于NP完全問題，是一個難題。 對于考試時間、考場和監(jiān)考教師這三部分的安排，要想同時做出一個驗證方案可行性的算法，其算法復(fù)雜度就不是簡單的將其相加了。經(jīng)過分析，這三個部分中考試時間的安排最為復(fù)雜，算法最難?？紙霭才畔鄬唵涡瑧?yīng)用銀行家算法更合理的分配教室，解決了當(dāng)2個考場人數(shù)都少于規(guī)定人數(shù)一半時合并考場的問題，節(jié)約了教室資源。而根據(jù)某高校的實際情況，監(jiān)考教師的安排是征求教師個人意見，自己將名字報上來的，所以程序中不

3、做完全的自動安排，而是將監(jiān)考教師姓名匯總到數(shù)據(jù)庫中，由教務(wù)人員選擇性安排。因此，在這種情況下，首先考慮考試時間的安排算法，在滿足考試時間安排的情況下再做其他部分安排。 本文分析了考試時間安排的約束條件，基于圖著色的數(shù)學(xué)模型，采用了一個二階段式的混合算法：即先用貪心算法的思想得出一個滿足所有必須要滿足的約束條件的初始可行解；在此基礎(chǔ)上再用改進(jìn)的分組遺傳算法的思想進(jìn)一步優(yōu)化結(jié)論，協(xié)調(diào)好考試周總的考試天數(shù)與學(xué)生復(fù)習(xí)時間之間的矛盾關(guān)系，