基于優先級考試自動編排的算法研究

摘要：利用計算機進行考試自動編排，涉及到的約束條件紛繁復雜，本文論及了一種基于優先級的考試編排算法，根據約束條件將教師，教室，課程各定義一個特征函數，來計算他們各自的優先級別，結合分治法、貪婪法等多種算法思想來排出無沖突的，人性化的考試編排表。

關鍵詞：優先級；考試編排；算法

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)08-1pppp-0c

1 引言

考試編排是高校考務管理中核心任務之一，因為其約束條件多，存在大量不確定因素，是比較復雜的一項工作。考試編排實際上是在教室集、監考教師集、課程集、時間集以及約束條件集等這些集合中尋求一種最優的解。為了提高考務管理工作的效率，快速排出合理無沖突的考試編排表，本文提出了一種基于優先級并結合分治、貪婪等多種算法思想的考試編排算法。

2 考試編排的約束條件與要求

(1)考試的時間段有限定（例如所有課程在2周內考完），并且在限定時間段時要以考試課程門數最多的班級能夠考完全部課程為前提；

(2)各班級的考試門數可能不同，因此考試日期間隔應盡可能的均勻，以利于學生的復習、考試間歇進行，發揮出正常水平。

(3)各班級最后一門考試要安排在最后一天或者倒數第二天，不然會存在過早放假的情況；

(4)安排考試要盡可能以自然班為單位，即同一自然班的學生盡可能安排在同一考試教室；所以在給班級安排考場時要選擇教室能容納的最大考試人數與自然班總人數差值的絕對值最小的教室，以達到教室資源合理的被利用；同一課程的班級，考試教室在地理位置上盡量在一個地方（比如說一棟樓的一層緊挨的幾個教室）。

(5)有特殊要求的課程要安排在特殊教室，如計算機機試課要安排在機房等；

(6)課程分為合班課（多個班級一起上課）和單班課，合班課牽扯的班級、人數都比較多，試卷量大，應優先安排（如公共課等），以便能更好的安排教師、教室資源；

(7)每個教室安排主考教師一名，監考教師一名。任課教師盡量不安排監考，因為他要巡考以解決考試過程中出現的專業問題；各監考老師的監考次數盡量均等，年紀比較大的教師上午安排了監考，下午盡量不要安排監考，同一時間段內所需監考教師的總人數不得大于可安排監考的教師總人數；

(8)同一時間學生不能參加2場考試；同一時間同一教室不能安排2場考試；同一時間同一監考教師不能安排2場監考；同一時間段內安排的考場總數不能大于能用于考試的教室總數；在同一時間段內，安排考試課程總數不能大于最大考試課程總數；

3 優先級的確定

(1)課程優先級的確定

課程優先級別的確定是指對符合某些條件的課程在考試時間集上優先進行安排。根據約束條件與要求，對考試班級數以及人數多的課程優先安排，對公共課優先安排。要對課程進行優先級別的確定，首先要分析課程的特征，課程的一般特征我們可以歸納為：①考試課程類型：公共必修、公共選修、專業必修、專業選修等；②考試課程班級數：開有該門課程的班級數量；③考試人數：參加該門考試的總人數；因此，我們給課程定義一個特征函數：F(x)=Ft(x)*C1+Fc(X)*C2+Fp(x)*C3。其中：C1、C2、C3為調整參數；Ft(x)表示該課程的類型；Fc(X)表示該課程的班級數，班級數越多的課程優先安排；Fp(x)表示參加該門考試的總人數，參考人數越多的課程優先安排。在我們實際的考試編排中，有可能會出現，主要考慮的是課程的考試人數與考試班級，因此我們規定C1

(2)考試教室優先級的確定

考試教室的優先級別由它的地理位置、教室最佳考試人數來決定。因此我們定義一個特征函數：G(x)=Ga(x)*D1+Gp(x)*D2。其中：D1、D2為調整參數；Ga(x)表示該教室所在的地理位置，按預先確定的規則給每個地理位置的教室規定一個權值，權值越大，則優先選擇該教室；Gp(x)表示該教室能容納的考試人數的最佳匹配權值，所謂最佳就是該教室能容納的最大考試人數與自然班的參考人數之差值的絕對值最小，Gp(x)=1/（最大考試人數-參考人數），若最大考試人數等于參考人數則Gp(x)=1；G(x)越大就說明該教室越適合作為該課程的考場。本特征值在給每一門課程安排教室時計算一次，然后將所有教室按G(x)值的非升序進行排序。

(3)監考教師優先級的確定

在所有可以監考的教師中我們對教師根據條件進行優先級的計算，以確定哪些教師適合監考。要保證每個老師的監考次數基本上保持平衡，同樣我們給教師定義一個特征函數：H(x)=(1-Hy(x)/HA(x)).其中：Hy(x)為該教師已監考的次數；HA(x)為需要監考的總次數。另外特殊情況有：當該教師為任課教師時，一般安排巡考，H(x)=0；當該教師年紀大于50歲時，出于人性化考慮盡量少安排監考，H(x)=(1-Hy(x)/HA(x))*0.3。H(x)越大說明該教師越適合監考該課程。本特征值在為每門課程安排主監考、副監考時分別計算一次，然后將所有可安排監考的老師按H(x)值的非升序進行排序。

4 考試編排算法的實現

(1)總體設計

編排考試涉及到的因素有教室集、監考教師集、課程集、時間集，條件復雜。本算法的核心思想就是采用分治法與貪婪法的思想。采用分治法思想，以考試課程為中心，將各集合分而治之。先給課程安排考試時間，然后再安排考試教室，最后再安排監考教師。如下圖：

另外，貪婪法就是一種在每一步選擇中都采取在當前狀態下最好（優）的選擇，從而導致結果是最好（優）的算法。采用貪婪法的思想，在分別安排時間、教室、教師的過程中將課程、教室、教師分別進行優先級的計算，每次遍歷時都選擇最優的做為結果。

(2)時間安排

基于高校目前的考試時間安排情況，將考試時間段分為多個時間片，每個時間片安排一門考試，假設考試時間為2周，每一天分為2個時間片，即上午下午各考一門，若無周末限制，則可安排考試的時間片總共有14個。

約定：假設時間片總共有2n個，為確保考試時間安排的均衡，我們把時間片記為：t1，t3….t2n-1或t2，t4….t2n兩組。任一時間片已經安排的考試科目數為N已，任一時間片允許安排的最大考試科目數為N總。具體步驟如下所述：（流程圖見左圖）

①對課程按約束條件利用課程特征函數進行優先級計算并按非升序排序；在排好序的表里順序取一門考試課程。

②取出一組時間片，循環遍歷每一個時間片，檢查N已

③取出該課程對應的所有考試班級，循環遍歷每個班級在此時間是

否有考試安排，若所有班級都無考試安排，則表示這些班級可以在此時間片一同考試，用變量Tk保存該時間片t2n-1 或t2n；若存在有考試安排的班級，則跳到下一時間片。這是為了滿足考試同一門課程的班級必須在同一時間考試的原則。

④遍歷所有班級，檢查是否有過早考完所有課程而放假的班級。若無，則將該課程的考試時間設置為Tk；若有，則將該課程的考試時間置為倒數第一或第二天的時間片。

(3)教室安排

給課程安排考試教室主要考慮如何有效利用所有能用來做考場的教室資源。就是教室的可容納考試人數要與班級參考人數的差值的絕對值最小。對于一課多班的情況，各班級考場最好在地理位置上盡量接近。

①將已安排好考試時間的考試課程表以時間片的非降序進行排序。

②取出同一時間片內所有課程及課程數（記為Nkc）.

③取一門課程，取該課程對應的考試班級，對每一個班級安排教室，計算所有教室的優先級并非升序排列，則越排前面的就是越適合該課程安排考場的教室；再次計算教室容考人數與班級實考人數的差值，判斷是否有可以合班一起考試的情況；

For(i=1;i<=Nkc;i++)

{

取出該課程對應的班級及班級數（記為Nbj）

For(j=1;j<=Nbj ;j++)

{

對教室表里所有在此時間片未安排考試的教室按教室特征函數進行優先級計算并按非升序排列。取出教室數Njs。

For(h=1;h<=Njs ; h++)

{

計算該教室Pcz =|教室容考人數-班級實考人數|

If(所有未安排考場的班級中存在實考人數

{這2個班合用一個教室進行考試; Break;}

Else

{該班獨占該教室; Break;}

}

}

}

(4)監考教師安排

對監考教師的安排我們分為2個步驟進行：第一步，安排主監考教師；第二步，安排副監考教師；主監考教師盡量安排開設該課程所在系的老師，副監考教師則無系別要求。

①將已安排好考試時間和考試教室的考試課程表以時間片的非降序進行排序。

②取出同一時間片的所有考試課程的考試教室，并遍歷這些教室給每個考試教室安排監考教師。

③第一步：取考試課程的所在系別，將教師表中屬于該系并在此時間片未安排監考的老師取出，根據特征函數進行優先級計算并排序。假如該課程有n個考試教室，則取教師表中優先級高的前n個教師，每個教室安排一個主監考老師；若此時該系的可監考老師數小于n，則對剩下的考試教室按同樣的方法安排非本系的老師做為主監考。

第二步：將教師表里面在此時間片未安排監考的老師取出（不管系別），根據特征函數進行優先級計算并排序。假如該課程有n個考試教室進行考試，則取出教師表中優先級高的前n個教師，每個班安排一個副監考。

5 總結

考試編排在解決沖突問題的同時還要體現其自動化與智能化，本文介紹了一種基于優先級的考試編排算法，分別給教室，教師，課程一個特征函數，根據特征函數來計算它們的優先級別，融合分治，貪婪等算法思想，基本上實現了考試編排的自動化與智能化，并在監考教師的安排上體現“以人為本”的思想。

參考文獻：

[1]孟慶全.排課程序優先級的確定與最簡單算法的實現[J].安徽工程科技學院學報，2005，6:56-57.

[2]馬慧彬.智能型考試安排系統的監考及教室安排算法[J].佳木斯大學學報（自然科學版），2004.3:74-75．

[3]胡世清，葛幸平.高校自動排考軟件的優化設計[J].教育信息化，2001，3:34-35．

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”