關于高路途成本下監(jiān)考安排算法優(yōu)化的若干思考

王妍 呂震宇

摘 要：排考問題是對考生、考場、時間、考試科目和監(jiān)考人員等因素進行配置的決策性問題?？荚嚲幣胖苯記Q定著教師能否更為有效地完成監(jiān)考工作，且編排過程中需盡可能降低監(jiān)考路途成本，這就要求考試編排在滿足眾多約束條件的同時要盡可能確保均衡。文章對優(yōu)化高路途成本下監(jiān)考安排算法的意義、國內外相關研究及本問題的研究前景進行了分析。

關鍵詞：高路途成本；監(jiān)考安排；算法；優(yōu)化

中圖分類號：TP301.6文獻標識碼：A收稿日期：2017-12-22

一、優(yōu)化高路途成本下監(jiān)考安排算法的意義

（1）減輕繁重工作，提高監(jiān)考編排效率。人工考試安排的工作量非常繁重，容易產生各種問題且不容易排查和修改，存在工作效率低、容易出錯等問題。通過計算機智能計算法完成考試編排可以大幅減輕人工工作壓力。

（2）優(yōu)化監(jiān)考安排，讓監(jiān)考教師在一次往返過程中完成更多監(jiān)考任務，降低學校班車派送成本及教師路途成本。

（3）有效利用資源，提升教學管理水平。綜合協(xié)調學生、教師、課程和教室資源配置，提高盡可能多的人員的滿意度，進而提升整體教學管理水平。

二、國內外關于排考安排的相關研究

由于排考問題的普遍性和復雜性，國外研究者已投入研究力量尋找解決方案。Carter 等（1996） 最早提出了監(jiān)考編排問題，并設計了一個EXAMINE 系統(tǒng)，采用序列建構方法尋找最優(yōu)解。Casey 和 Thompson（2003）將約束分為硬約束與軟約束，采用兩階段方法尋找解決方案，即第一階段對教師資源進行排序，按硬約束分配教師資源，第二階段采用退火算法安排教師資源，以滿足軟約束。根據這一算法，Casey 和Thompson 設計了一個系統(tǒng)，即 GRASP。Banerjee S等（2004）提出了一種改進的模擬退火算法，在代價函數和解空間方面都有所改進，但模擬退火算法解的初始化比較耗時，對大任務集來說，收斂速度依舊緩慢。Ulker 等（2007）使用遺傳算法對該問題進行了分析，但結果并不比以前的方法好。Caramia 等（2008）采用三階段法來解決監(jiān)考安排問題，即先使用貪婪算法依照優(yōu)先級分配教師資源，然后使用懲罰遞減因子（Penalty decreaser）減少軟約束成本，最后使用懲罰交易因子（Penalty trader）對監(jiān)考安排進行必要的修正。

國內的學者也對此類問題進行了相關研究。張華、王秀坤和孫燾（2003）利用蟻群算法，結合圖論中的著色和運籌學背包問題，對考試安排這一問題進行了求解[1]。王亞敏、冀俊忠（2009）利用基于時間序列的粒子編碼方式和更新算子，建立了考試安排的粒子群求解模型，并結合簡化鄰域算法給出了改進策略。仿真實驗結果表明，其算法及策略有效。上述研究盡管應用了信息技術或智能搜索算法實現自動排考，但僅考慮了約束條件的滿足，而沒有考慮目標的優(yōu)化。徐欣等（2010）構建的“期末考試監(jiān)考安排的數學模型”具有優(yōu)化目標，即監(jiān)考次數最多的教師與監(jiān)考次數最少的教師的監(jiān)考總次數相差最小[2]。但實際中監(jiān)考次數往往是教學秘書在平均化的基礎上根據各教師的實際情況進行調整，如某教師在學期初參加了補考的監(jiān)考，則其在期末考試時可以少參加監(jiān)考，因此，徐欣模型的優(yōu)化目標與實際情況有所出入。

總之，目前國內外相應的考試安排軟約束的優(yōu)化較為缺乏，尤其是節(jié)省路途成本這一因素，這是本研究力求解決之處。

三、優(yōu)化高路途成本下監(jiān)考安排算法的前景展望

從應用領域看，是對考試安排的智能優(yōu)化，各高校都面臨考試安排的工作量大、數據關系復雜的問題，該項目具有很好的應用價值；從問題本質看，考試安排是時間表問題，時間表問題屬于多目標優(yōu)化問題，多目標優(yōu)化對于高校合理利用教學資源等方面有很好的應用價值。對算法的優(yōu)化可廣泛應用于多目標優(yōu)化問題的解決中，研究不僅滿足高?？荚嚭侠砘才诺男枰?，并對其進行優(yōu)化，從而達到節(jié)省路途成本的目的，是新時代高校解決分校區(qū)、校區(qū)偏遠等問題的有利解決方案，同時引入排考結果評價體系，真正將排考結果應用于高?？荚嚬ぷ髦校ㄟ^多方打分反饋結果，從而調整編排方式方法，使結果達到最優(yōu)化，該研究具有廣泛的應用前景。

參考文獻：

[1]張 華，王秀坤，孫 燾.蟻群算法在考試安排中的應用[J].計算機工程與設計，2003（12）：62-64.

[2]徐 欣，翟金剛，劉曉華.期末考試監(jiān)考安排的數學模型[J].數學的實踐與認識，2010（23）.