關于高路途成本下監考安排算法優化的若干思考

王妍 呂震宇

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

關鍵詞：高路途成本；監考安排；算法；優化

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

一、優化高路途成本下監考安排算法的意義

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

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

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

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

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

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

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

三、優化高路途成本下監考安排算法的前景展望

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

參考文獻：

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

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