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

王妍 呂震宇

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

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

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

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

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

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

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

二、國內(nèi)外關(guān)于排考安排的相關(guān)研究

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

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

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

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

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

參考文獻：

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

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