基于高?？荚嚬芾砑?xì)化的排考系統(tǒng)研究與設(shè)計*

張培培，呂震宇，閆海波

（1.華北理工大學(xué) 管理學(xué)院，河北 唐山 063000；2.華北理工大學(xué) 教務(wù)處，河北 唐山 063000）

一、引言

以往高校考試自動排考問題的數(shù)學(xué)描述[1-4]在實際考試安排管理中有考慮不周的地方，主要表現(xiàn)在：①資源浪費和分配不均。高校教室資源一般存在多種容量，如大教室容量為3個班，小教室容量為1個班，如某門課程任務(wù)數(shù)是10，分配了4個容量為3的教室，造成2個容量的浪費，而上千門課程造成的浪費是不容小覷的；再如某門課程有多個學(xué)院學(xué)習(xí)，前幾個學(xué)院拿走了所有容量為3的大教室，最后一個學(xué)院只剩下容量為1的小教室，由于每個教室需派遣的監(jiān)考老師人數(shù)相同，優(yōu)先選擇大教室，但大教室數(shù)量有限，這樣就造成各學(xué)院資源分配不均的現(xiàn)象。需將資源按照教室容量進(jìn)行分配，避免出現(xiàn)資源浪費和分配不均的現(xiàn)象。②公共課集中排。公共課是所有專業(yè)或部分跨學(xué)院專業(yè)的學(xué)生都必須學(xué)習(xí)的課程，若上午考《大學(xué)英語》、下午考《高等數(shù)學(xué)》，盡管監(jiān)考老師利用率高，但學(xué)生和考試管理人員任務(wù)較重，所以公共課的安排要盡量分散。專業(yè)課是針對本專業(yè)開設(shè)的課程，考生來自同一個學(xué)院，其目標(biāo)為學(xué)院所派教師人數(shù)最少，可以集中排，而公共課不要集中排，所以兩種課程在考試安排過程中需區(qū)分對待。③如考慮交通，一天四個時段是有優(yōu)先級的，如上午第二時段好于上午第一時段，目標(biāo)值相等的情況下需選時段較好的。針對上述問題，本文利用貪心算法，提出了新的高校自動排考系統(tǒng)，結(jié)果證明該設(shè)計很好地滿足了以上管理要求。

二、考試時間表問題的數(shù)學(xué)描述

1.定義

②資源 R={r1，r2，…，rNR}可表示為{w1q1a1，…，w1q1aNroom，…，w5q4a1，… ，w5q4aNroom}，其中 ，W={w1，w2，w3，w4，w5}為天數(shù)，共 5 天，Q={q1，q2，q3，q4}為時段，一天 4 個時段，時段具有優(yōu)先級，順序為 q1，q2，q3，q4，如 q1代表上午第二時段。A={a1，…，aNroom}為教室，Nroom為教室數(shù)量，rj.room_capacity為資源j教室容量，設(shè)大、中、小教室容量分別為3、2、1個班。資源按照周一到周五，每天四個時段，每個時段按Nroom個教室排，其中教室按容量先大后小的順序排，資源數(shù)量 NR=5×4×Nroom。

③任務(wù) T={t1，t2，…，tNT}為某課程某學(xué)院的某個班。任務(wù)量大的課程排在前面，課程里學(xué)院任務(wù)量大的排在前面。如圖1所示，虛線框起來的“1”對應(yīng)資源為周一上午第二大節(jié)a001教室，任務(wù)為《大學(xué)英語》管理學(xué)院信管1班，“1”說明該任務(wù)被安排在該教室。

圖1 考試安排結(jié)果示例

2.約束

①教室容量約束。資源j的任務(wù)數(shù)不能超過資源j的容量。如公式（1）所示。

②任務(wù)約束。每一個任務(wù)必須被分配，且只能被分配一次。如公式（2）所示。

③課程約束。課程任務(wù)需安排在同一時間，即課程的任一任務(wù)在任一時間所對應(yīng)的aij和要相同，時間w，q對應(yīng)資源 j序號起止為 （w×q-1）Nroom+1 和 w×q×Nroom+1，設(shè)某課程任務(wù)序號為{m，…，n}，在某一時間所對應(yīng)aij之和相同如公式（3）所示。

任一時間需讓 w=1，2，3，4，5，q=1，2，3，4。

④教室數(shù)量約束。若將教室數(shù)量約束簡單定義為課程在時間w，q有足夠教室可分配，即該時間的空教室容量大于等于課程任務(wù)數(shù)Nm，如公式（4）所示，則會產(chǎn)生資源浪費和各學(xué)院資源分配不均的現(xiàn)象，如圖2所示。為了解決這個問題，需分別計算大中小資源需求，約束也為該時間不同容量的空教室數(shù)量大于等于課程對該容量教室的需求量。如公式（5）所示。

圖2 資源浪費與學(xué)院分配不均示例

圖3 教室數(shù)量約束示例

如圖3所示，三個課程進(jìn)行排考，總?cè)蝿?wù)量為20，教室總?cè)萘繛?4，三門課程大、中、小教室需求如公式（8）所示。當(dāng)遇到求得結(jié)果為小數(shù)，則舍棄小數(shù)，進(jìn)行補齊，補齊思路為大、中、小教室資源循環(huán)補給，如《運籌學(xué)》需補齊 2 個班，大、中、小教室需求為 0、1、0。

3.目標(biāo)

①公共課課程緊密程度最低。課程緊密程度Cw用一天安排的任務(wù)數(shù)量來表征，天數(shù)為w的資源j的起止序號為（w-1）×4×Nroom+1 和 w×4×Nroom，如圖 4 所示，黑格為安排任務(wù)，黑格越多課程緊密程度越高，總緊密程度C為5天緊密程度的最大值，如公式（9）所示。

圖4 課程緊密程度最低目標(biāo)示例

課程緊密程度最低的目標(biāo)為min C。

②專業(yè)課學(xué)院im所派教師人數(shù)最少。學(xué)院所派總?cè)藬?shù)TN[im]為每天所派人數(shù)之和，每天所派人數(shù)TN[im][wn]為各時段人數(shù)的最大值，假定每個教室派2個監(jiān)考老師，各時段人數(shù)TN[im][wn][qr]如公式（10）所示，Tim為學(xué)院im所對應(yīng)任務(wù)集合，如圖5所示，虛線框有多個任務(wù)為1，但因為在同一個教室，所派監(jiān)考人數(shù)仍為2，所以該學(xué)院、該資源和Σi∈Timaij若大于0則取值為1，若等于0則取值為0。

圖5 學(xué)院所派教師人數(shù)最少目標(biāo)示例

學(xué)院所派教師人數(shù)最少的目標(biāo)公式如（11）所示。如圖5所示，管理學(xué)院的公共課《大學(xué)英語》已排在w1q1，若要監(jiān)考教師人數(shù)少，專業(yè)課《運籌學(xué)》需排在同一天但不同時段。

三、算法描述

排考問題是一類典型的時間表問題，是對考生、考場、時間、考試科目和監(jiān)考人員等因素進(jìn)行配置的決策性問題[5]。關(guān)鍵技術(shù)包括：進(jìn)化計算、貪心算法、整數(shù)規(guī)劃、圖著色等[6]。Ferland[7]和吳金榮[8]提出把時間表問題化成整數(shù)規(guī)劃來解決，但是計算量很大，只適用于規(guī)模非常小的課程表的編排。董健興[9]等人則提出可以用圖論中的染色問題來求解，可惜圖論的染色問題本身也是一個NP完全問題。進(jìn)化算法其獲得全局最優(yōu)的可能性較大，但對初始種群的選擇有一定依賴性，易產(chǎn)生早熟收斂的問題[10]。貪心算法將整體劃分成多個子問題，先做出子問題的最優(yōu)解，逐步來達(dá)到整體最優(yōu)，該方法簡單快速，被廣泛使用[11]。

本文采用貪心算法解決自動排考問題，貪心策略為每次挑選排在最前面的課程進(jìn)行排考。任務(wù)按照先公共課后專業(yè)課，公共課按先大課后小課排，課程里面按學(xué)院任務(wù)量從大到小排，專業(yè)課按照先大課后小課排。選出一個課程，循環(huán)時間，進(jìn)行約束判斷，將所有滿足約束條件的時間w、q以及目標(biāo)值V放入鏈表List，當(dāng)時間循環(huán)結(jié)束，遍歷List，找到目標(biāo)值最優(yōu)的情況，當(dāng)目標(biāo)值相等，選擇時段較好的，即q較小的時間，遍歷完List就確定了最優(yōu)的時間，將該時間教室資源按比例進(jìn)行分配，更新排考結(jié)果A。算法N-S圖如圖6所示。

圖6 考試安排算法N-S圖

在前面的教室數(shù)量約束中，可以得到所有課程大、中、小教室分配數(shù)量，如圖7所示，而公共課教室還需根據(jù)學(xué)院任務(wù)比來計算學(xué)院大中小教室數(shù)量，學(xué)院任務(wù)比Ratioi/m為課程m學(xué)院i任務(wù)量與課程m總?cè)蝿?wù)量的比值，課程m 學(xué)院i分配大（B）中（M）?。⊿）教室數(shù)量如公式（12）所示。假設(shè)《大學(xué)英語》有三個學(xué)院需要分配，計算《大學(xué)英語》三個學(xué)院的大中小教室數(shù)量如公式（13）所示，當(dāng)遇到結(jié)果為小數(shù)時，則與課程分配一樣，舍棄小數(shù)進(jìn)行資源補齊，如圖3所示。

圖7 公共課大中小教室分配示例

四、仿真結(jié)果

實驗數(shù)據(jù)來自華北理工大學(xué)春季學(xué)期考試安排18周數(shù)據(jù)。

1.公共課監(jiān)考人數(shù)、課程緊密程度與公共課任務(wù)資源比的關(guān)系

設(shè)公共課任務(wù)資源比RatioT/R=公共課任務(wù)數(shù)/總資源容量，隨RatioT/R增大，監(jiān)考人數(shù)會增多，課程緊密程度也會增大，如圖8所示，當(dāng)RatioT/R在40%之內(nèi)，教師數(shù)量急劇上升，課程緊密程度增長緩慢，這是因為公共課安排在先，任務(wù)安排較分散，當(dāng)RatioT/R超過40%，教師數(shù)量增速放緩，課程緊密程度急劇增加，這是因為需在同一天不同時段安排課程。真實考試安排數(shù)據(jù)RatioT/R低于40%，以保證公共課較低的課程緊密度。

圖8 公共課監(jiān)考教師數(shù)量、課程緊密程度與任務(wù)資源比的關(guān)系

2.專業(yè)課任務(wù)比與專業(yè)課監(jiān)考人數(shù)比的關(guān)系

專業(yè)課任務(wù)比RatioT_Pro/T=學(xué)院專業(yè)課數(shù)量/學(xué)院總?cè)蝿?wù)數(shù)量；專業(yè)課監(jiān)考人數(shù)比RatioP_Pro/P=（學(xué)院所派總?cè)藬?shù)-學(xué)院公共課所派人數(shù)）/學(xué)院所派總?cè)藬?shù)。如圖9所示，在RatioT_Pro/T≤30%時，專業(yè)課額外所需派出的老師數(shù)量幾乎為零，這是由于將專業(yè)課盡量排在與公共課同天不同時段，監(jiān)考教師利用率較高，隨后老師數(shù)量劇烈上升，所以不能再將專業(yè)課排在與公共課同天。真實數(shù)據(jù)為90%以上學(xué)院的RatioT_Pro/T低于30%，保證了監(jiān)考教師較少。

圖9 學(xué)院專業(yè)課任務(wù)比與學(xué)院專業(yè)課所派教師比的關(guān)系

3.資源利用率、資源分配均勻度與任務(wù)資源比的關(guān)系

學(xué)院im教室容量為l的分配差異Liml為理想分配結(jié)果與真實分配結(jié)果的平方差，如公式（14）所示，理想分配為學(xué)院總?cè)蝿?wù)數(shù)量與總?cè)蝿?wù)數(shù)量的比值，實際分配為學(xué)院占用教室容量為l的教室數(shù)量除以容量為l的教室總量與任務(wù)資源比的乘積，如公式（15）所示。學(xué)院im資源分配差異Lim為三個容量差異的最大值，總體資源分配差異L為各學(xué)院資源分配差異均值，NI為學(xué)院數(shù)量，分配均勻度E為差異L的倒數(shù)，如公式（16）所示。資源利用率RatioT/RInUse為總?cè)蝿?wù)量與使用教室容量的比值，如公式（17）所示。如圖10所示，無論任務(wù)資源比RatioT/R怎樣變化，均勻度和資源利用率均近似為100%，保證了較好的資源利用率和分配均勻度。

五、結(jié)束語

本文指出了公共課與專業(yè)課的目標(biāo)不同，需區(qū)分對待，算法對于兩種課程是通用的，實驗結(jié)果表明，當(dāng)公共課比例不高的情況下，緊密程度較低，同時實驗結(jié)果也表明，當(dāng)大部分學(xué)院專業(yè)課任務(wù)比較低時，可保證監(jiān)考教師較少的目標(biāo)，實現(xiàn)了任務(wù)分配的優(yōu)化。最后，算法結(jié)構(gòu)中指明，當(dāng)目標(biāo)值相等的時候，選擇較好的時間段，從而實現(xiàn)了時間選擇的優(yōu)化。

圖10 公共課資源分配均勻度與任務(wù)、資源的關(guān)系