一種解決排考資源沖突的優(yōu)化方法

邵景峰，厲 謙，暢朝霞

（1.西安工程大學(xué) 管理學(xué)院，陜西 西安710048；2.西安工程大學(xué) 藝術(shù)工程學(xué)院，陜西 西安710048；3.西安工程大學(xué) 圖書館，陜西 西安710048）

面對我國高校因擴招而帶來的教育資源配置不足與培養(yǎng)方式多樣化之間，以及教學(xué)資源短缺與考試方式多元化之間日益嚴重的矛盾，如何在各高校開展教育國際化和協(xié)同創(chuàng)新體系下，為適應(yīng)新時代的要求，實現(xiàn)學(xué)生考試管理方式的智能化就顯得十分必要［1］.借助Web of Science數(shù)據(jù)庫，以“arrangement examination”為主題詞進行文獻檢索，發(fā)現(xiàn)國外學(xué)者對排考問題的研究相對較早，是始于1964年.當(dāng)然，在此期間也對排考資源沖突問題進行了深入探討，如Brocklesby J［2］構(gòu)建的排考系統(tǒng)模型，Hamazaki Hironori等人［3］提出的基于改進遺傳算法的排考方法，以及Carter M W在1986年研究的基于時間段優(yōu)化的排考算法等，目的是使各類排考資源（如教室、監(jiān)考教師、座次等）在考試時間段的選擇上達到最優(yōu)匹配.在考試編排方法不斷改進的過程中，也有學(xué)者對排考資源沖突問題進行了算法優(yōu)化，如Acharyya Arnav等人［4］提出的搜索算法以及Abramson D等人［5］研究的考場編排算法等.在我國，對排考資源沖突問題的研究可追蹤到1998年，如徐尚進［6］研究的普通高校課務(wù)管理排考系統(tǒng)的算法設(shè)計，朱書尚和曹世勇等人［7］研究的關(guān)于排考問題的數(shù)學(xué)模型及其算法等.在此期間，一些國內(nèi)學(xué)者針對不同應(yīng)用環(huán)境下的排考問題給出不同的解決方案，如田嶺［8］提出的大學(xué)自動排考算法；蔡木生［9］研究的高校自動排考算法；劉艷等人［10］研究的學(xué)院專業(yè)課自動排考算法的設(shè)計與實現(xiàn)等，都從數(shù)學(xué)的角度證明了其算法的可行性.當(dāng)然，也有人從圖論模型的角度給出了一些優(yōu)化方法，如王卿等人 提出的高等學(xué)校排考染色－匹配算法；董健興等人［12］提出的基于圖論的高校排考算法等，期待解決排考資源沖突問題和排考過程優(yōu)化問題.

通過文獻回顧，發(fā)現(xiàn)國內(nèi)外學(xué)者對排考資源沖突問題的研究主要針對排考算法的設(shè)計和優(yōu)化，并沒有對排考過程中所涉及到的諸如時間段問題、考場資源問題、座位資源等問題進行較深入研究，也沒有從整體上加以考慮.本文首先從排考實際存在的問題作為切入點，深入分析排考資源間的邏輯關(guān)系；然后，從考場的編排、監(jiān)考的編排，以及座次的編排過程入手，對各類排考資源在最優(yōu)考試時間選擇上的沖突問題進行逐步算法描述和流程設(shè)計，并實現(xiàn)整體優(yōu)化；其次，通過智能排考系統(tǒng)的構(gòu)建，來驗證算法的可行性和合理性，以期解決排考資源在時間段選擇上的沖突問題.

1 排考問題分析

排考過程所設(shè)涉及的對象主要有：學(xué)生（參加考試的對象）、課程（被選擇的對象）、選課記錄（排考的對象）、教室（場所對象）、教師（監(jiān)考對象）、考試時間（包括：每場考試的時間和考試分布的時間段，即考期）等，這些對象在數(shù)據(jù)結(jié)構(gòu)上具有數(shù)據(jù)重用性，而且，每個對象之間在時間上還具有一定的相關(guān)性，使得一個對象的變換往往涉及到多個對象數(shù)據(jù)內(nèi)容的變換，往往牽一發(fā)而動全身，要真正實現(xiàn)排考過程的最優(yōu)化，則需要在多約束條件下，通過多種優(yōu)化規(guī)則，使現(xiàn)有的對象在編排過程中最大程度地達到最優(yōu)化.當(dāng)然，要使現(xiàn)有的對象得到優(yōu)化，其首要解決的問題是進行選課體系的優(yōu)化，盡可能避免課程沖突問題［13］.尤其是在高校內(nèi)部相近專業(yè)的排考過程中，更要解決好如下問題：（1）課程名稱相同，但課時、學(xué)分不同的情況；（2）不同專業(yè)學(xué)生，選修同一門課程的情況；（3）不同校區(qū)、選修同一門課程的情況；（4）在教室教師資源有限、安排同一門課程考試的情況.

2 排考問題描述

要解決好排考問題，首先應(yīng)理順與排考工作相關(guān)的數(shù)據(jù)流和業(yè)務(wù)流.其中，數(shù)據(jù)流來源于學(xué)生對象、課程對象、選課對象.現(xiàn)令集合S＝ ｛s1，s2，…，sm｝、C＝ ｛c1，c2，…，cn｝、SC ＝ ｛sc1，sc2，…，sck｝分別表示學(xué)生、課程、選課對象集合，其中：m、n、k分別表示學(xué)生數(shù)、課程數(shù)、選課記錄數(shù).由于sci（i＝1，2，…）的取值范圍源于si和ci，使得S中的一條記錄可對應(yīng)C中的多條記錄，而C中的一條記錄也可對應(yīng)S中的多條記錄.顯然，S與C之間是一種多對多關(guān)系，學(xué)生、選課、課程三者間的關(guān)系圖如圖1所示.

在保證基礎(chǔ)數(shù)據(jù)正確的前提下，對于同一門課程的考試編排，通常規(guī)定必須安排在同一時間段進行考試，尤其是面對高校多校區(qū)的情況時，更應(yīng)注重同一門課程安排在同一時間段進行.當(dāng)然，在智能排考過程中，要保證這種管理規(guī)定得以順利進行，前提條件就是確保每門考試課程在考試資源的分配上無沖突，而檢驗有無沖突的基本判斷方法是在同一時間段內(nèi)，一個考生只能在一個考場參與一門課程的考試.

為了更加直觀地檢驗排考過程是否存在沖突問題，在圖1的基礎(chǔ)上，特選取五門課程作為一學(xué)期學(xué)生的選修課，結(jié)果見表1.由此構(gòu)建的學(xué)生、課程、選課三者間關(guān)系所對應(yīng)的帶權(quán)的無向圖，如圖2所示，其中，圖的頂點表示五門課程，而邊表示同時選修了相關(guān)課程的學(xué)生人數(shù).

表1 五門課程的學(xué)生選課結(jié)果表

圖1 學(xué)生、選課、課程三者間的關(guān)系圖

通過圖2，借助無向圖的頂點個數(shù)和邊所對應(yīng)的權(quán)，可以構(gòu)建一個鄰接矩陣M，使M ＝（mij）n＊n，其中，i，j≤n且mij＝mji，即矩陣M存在對稱關(guān)系，并且主對角線元素全為0.這樣，矩陣M的元素存在如下關(guān)系：

圖2 帶權(quán)的選課信息無向圖

通過鄰接矩陣M的構(gòu)建，可見在同一時間段，為節(jié)約教室資源，對同一考場而言，考試課程間的關(guān)系僅有兩種表示方式，即相容（不存在一個學(xué)生同時選修兩門課程的情況）；相斥（存在至少有一個學(xué)生同時選修兩門課程的情況）［14］.為此，用0表示相容，則兩門課程同時安排在同一考場的條件完全滿足；而用1表示相斥，則兩門課程同時安排在同一考場會引起課程沖突.

這樣，為了盡可能避免同場次考試課程間的沖突問題，還需對鄰接矩陣M＝（mij）n＊n進一步簡化，可得到矩陣M對應(yīng)的一個課程關(guān)系矩陣C＝（cij）n＊n，其中，cij＝cji，即矩陣C也存在對稱關(guān)系，其主對角線全為0，則

由課程關(guān)系矩陣C，則可得到如下兩類數(shù)據(jù)：

（2）與第i門課程相容的課程數(shù)N，其由滿足cij＝0（0≤j＜n且j≠i）條件的所有課程組成.

由關(guān)系矩陣C得出的兩類數(shù)據(jù)可見，在整個智能排考過程中，為使整個排考結(jié)果得以合理優(yōu)化，其首要條件是必須保證“考試課程之間在資源分配上無沖突”.當(dāng)然，在這個前提下，要實現(xiàn)教育資源利用率的最大化，整個排考過程還應(yīng)遵循如下原則：

（1）要使課程關(guān)系矩陣C存在近似解或可行解，必須使考試資源（教師、教室、學(xué)生、課程）在空閑時間的分配上達到最優(yōu)；

（2）當(dāng)存在大型考試、集中考試或連考情形時，參加考試的學(xué)生人均場次數(shù)的間隔應(yīng)盡可能大，讓學(xué)生有盡可能多的時間進行復(fù)習(xí)，并使考試資源（教師、教室、學(xué)生、課程）在空閑時間上得到合理分配和利用.

3 相關(guān)算法的構(gòu)建

3.1 考場安排算法

考場安排是考試管理環(huán)節(jié)中的一項重要工作，其科學(xué)合理的考場編排方法既可以提高教務(wù)工作者的工作效率，又可以在一定程度上促進高等教育信息化的發(fā)展.為此，在編排考場時，首先需解決的問題是如何將選修同一門課程的學(xué)生或同一個教學(xué)班的學(xué)生在同一考場中選課順序進行隨機編排，并讓排考系統(tǒng)隨機分配座位，以體現(xiàn)考試過程的公平性和公正性，從根本上杜絕考試舞弊現(xiàn)象的發(fā)生.

考場編排算法設(shè)計的基本思想是：首先在教室信息表ClassRoom中選擇“空閑”教室信息資源，并將“空閑”教室資源信息按教室類型（多媒體教室、畫室、普通教室等）、座位數(shù)n（n≤40，40＜n≤80，80＜n）大小進行排序并分類；然后，將其排序分類結(jié)果依次存入預(yù)先設(shè)計好的教室臨時時間隊列數(shù)據(jù)表Temproom1，Temproom2，Temproom3中；其次，選取待排考的課程信息ci，每門課程對應(yīng)的選課人數(shù)kij（第i門課程的學(xué)生人數(shù)有j位），以及教室座位數(shù)n.若該選課任務(wù)所對應(yīng)的課程還沒有安排考場，則該教學(xué)班的課程將滿足排考條件，并將選課任務(wù)按照屬性“考試時間段”進行降序排列，依次存入課程臨時隊列數(shù)據(jù)表Tempcourse中.對每門課程而言，在排考過程中，需進行選課人數(shù)及考生數(shù)kij與座位數(shù)n之間的除操作，整個過程以占用教室資源數(shù)最少，且kij能整除n為最佳.

在考場編排過程中，還應(yīng)根據(jù)考試數(shù)量的多少安排相應(yīng)的監(jiān)考教師，此時，應(yīng)從表Tempcourse中選取首條記錄，并根據(jù)Tempcourse中的開課學(xué)院信息，開始檢索教師信息表，從中選取“是否排考”字段值為空的教師職工號，構(gòu)造考試任務(wù)鏈表 Examin－Duty－Link（Number－Time，Number－Course，ClassRoom－Array，Number－Student，ClassRoom－Type，Number－ClassRoom）；以及考場鏈表 ClassRoom－Link（Number－ClassRoom，ClassRoom－Type，ClassRoom－Prior，Number－Seat），以初始化鏈表并將考場鏈表 Class－Room－Link按ClassRoom－Prior優(yōu)先級的先后順序進行排序.同時，若考試任務(wù)對考場有特殊需求，則按考場類型（ClassRoom－Type）進行排序，采用最佳擬合方案為每個考試任務(wù)安排考場，并存入教師臨時空閑時間隊列數(shù)據(jù)表Tempteacher中進行匹配排考.在此過程中，若匹配失敗，則數(shù)據(jù)庫指針下調(diào)一位，繼續(xù)查詢“是否排考”字段值為空的教師，直到滿足條件為止；否則，刪除Tempcourse表中已經(jīng)匹配的考試課程，并將最終考場結(jié)果存入Course鏈表的教室編號節(jié)點字段.周而復(fù)始，直到Tempcourse表中的全部課程被匹配為止.

依據(jù)上述考場編排算法，將其應(yīng)用到智能排考系統(tǒng)之中，形成“考場安排”功能模塊，如圖3所示.其中，主要包括單個學(xué)生的考試科目、考試時間、考試批次、考場（教室編號）以及考試備注等信息.

圖3 考場安排結(jié)果

圖4 監(jiān)考安排結(jié)果

3.2 監(jiān)考編排算法

根據(jù)3.1的考場編排算法，在監(jiān)考教師編排算法的設(shè)計過程中，首先從課程表Course中選取任課教師作為主監(jiān)考；然后從教室表ClassRoom中獲取教室座位數(shù)n（n≤40，40＜n≤80，n＞80），并根據(jù)座位數(shù)n來設(shè)置主監(jiān)考與副監(jiān)考的比例（1∶1，1∶2，1∶3）；其次，從監(jiān)考教師鏈表SuperExaminTeacher（Superexamin－ID，Superexamin－Name，Right－Superexamin，Time－Superexamin，Number－Superexamin）選 擇該時間段其屬性值（Time－Superexamin）為“空閑”的教師作為副監(jiān)考，并使監(jiān)考教師的監(jiān)考場次數(shù)（Number－Superexamin）加1；最后，根據(jù)上述基礎(chǔ)數(shù)據(jù)的設(shè)置，進行數(shù)據(jù)鏈表的初始化，將監(jiān)考教師鏈表按監(jiān)考場次（Right－Superexamin）順序進行倒序排序，以構(gòu)造考試任務(wù)鏈表 Examin－Duty－Link（Number－Time，Number－Course，ClassRoom－Array，Number－Student，ClassRoom－Type，Number－ClassRoom）.

按照監(jiān)考編排算法的描述過程，借助智能排考系統(tǒng)獲取課程信息、學(xué)生選課信息、教師信息，以及教室信息等基礎(chǔ)數(shù)據(jù)，進行算法過程的可行性和合理性驗證，其模塊的界面如圖4所示.

3.3 考場座次編排算法

3.3.1 算法設(shè)計 設(shè)某課程的考試涉及到m個教學(xué)班的n個考生，并將每個教學(xué)班的考生分別用集合A1，A2，…，Am表示，這樣Ai可用集合Ai＝ ｛ai1，ai2，…，aik｝來表示，且k∈ ［0，n］.同時存在關(guān)系n＝A1，A2，…，Am.基于此，考場座次編排算法的設(shè)計思路為：基于混洗算法的基本思想［16］，先設(shè)n＝A1，將其看成一個其前后可插入新元素的環(huán)；然后，依次將各集合Ai（i＝2，…，n）中的元素順序插入到環(huán)n中的相鄰元素之間，插完為止，最終形成更大的環(huán)n；其次，依據(jù)考場編排算法，確定各考場的規(guī)定人數(shù)s，將全部考生n均勻分散到n／s個考場中去.

3.3.2 算法結(jié)果分析 現(xiàn)獲取學(xué)生選課任務(wù)信息進行考場座次編排結(jié)果的功能測試，并依據(jù)3.1的考場編排算法描述過程，將各個教學(xué)班的選課學(xué)生均勻地分配到各個考場，且考場座位編排結(jié)果如圖5所示.可見該算法完全可以滿足多校區(qū)多門課程在同一時間段考試的編排工作，并且考場座位編排結(jié)果顯示，選修同一門課程的學(xué)生其前后位置并不是同一教學(xué)班或?qū)W號相連的考生，這充分體現(xiàn)了考試過程的公平性和公正性，從根本上杜絕了考試舞弊現(xiàn)象的發(fā)生.

3.3.3 算法復(fù)雜度分析 為了分析種算法的復(fù)雜度，現(xiàn)定義如下變量：n為所有課程的選課總?cè)藬?shù)，m為根據(jù)校區(qū)、行政班、選課課程進行分組的組數(shù)，k為參加考試的每組人數(shù)，i為每個k所需要的考場數(shù)，s為每個k所對應(yīng)的考生人數(shù)，f為某個教學(xué)班的選課人數(shù).這樣，利用線性隨機方法［17］，通過3.1考場編排算法為每個考生所產(chǎn)生的隨機數(shù)進行排序，然后結(jié)合每個考場的考場號、座位號，進行數(shù)據(jù)組合形成考生的準(zhǔn)考證號或考試號，而這個過程正好是一個線性變換的過程，其時間復(fù)雜度為O（n）.同時，假設(shè)排序的時間復(fù)雜度為O（nlgn），則再根據(jù)二重循環(huán)，系統(tǒng)生成考場號、座位號的過程的時間復(fù)雜度為O（m＊i＊s），故線性隨機方法的復(fù)雜度為O（n）＋O（nlgn）＋O（m＊i＊s）.

圖5 考場座位編排結(jié)果

根據(jù)算法的設(shè)計思路，具體的偽代碼如下：

在對考生編排考場號和座位號之前，算法過程還要對選修每門課程的所有考生進行重新排序，以得到一個新的隊列，使得每次插入一個新的考生，隊列中的對象都要執(zhí)行加1操作，所以，總的算法復(fù)雜度為O（n）＋O（nlgn）＋O（m＊（O（k2）＋O（klgk）＋O（j＊s））.

4 結(jié)束語

排考是各高校教務(wù)管理部門的一項十分重要又相當(dāng)復(fù)雜的工作，其直接目的是為學(xué)校各教學(xué)部門開設(shè)的課程安排合理的考試時間、地點、監(jiān)考教師，從而使高校的教學(xué)工作得順利進行.為此，首先對如何實現(xiàn)智能排考，以及排考過程中存在什么樣的問題進行了分析；其次，在網(wǎng)絡(luò)環(huán)境下，借助高校教務(wù)管理系統(tǒng)，研制了一種智能排考系統(tǒng)，驗證了排考算法的合理性和有效性.最后，通過系統(tǒng)功能測試，結(jié)果表明，所構(gòu)建的最優(yōu)匹配算法具有較好的靈活性和簡潔性，較好地解決了傳統(tǒng)手工排考過程中的隨意性和重復(fù)性，并且避免了排考過程中的人為干預(yù).同時，智能排考系統(tǒng)的實現(xiàn)，一方面優(yōu)化了高校教務(wù)排考工作的業(yè)務(wù)流程，提高了教學(xué)資源的利用率；另一方面，實現(xiàn)了排考過程的自動化，降低了繁重的人工手工統(tǒng)計工作，很大程度上提高了教務(wù)工作效率，促進了高校教育信息化的發(fā)展.

［1］YUANG Ping.Institutional arrangements and construction safety in China：An empirical examination［J］.Construction Management and Economics，2009，27（5）：439－450.

［2］BROCKLESBY J.Using the viable systems model to examine multi－agency arrangements for combatting transnational organised crime［J］.Journal of the Operational Research Society，2012，63（3）：418－430.

［3］HAMAZAKI Y，HIRONORI J，F(xiàn)UJITA W，et al.Examination of the proper arrangement of damper by using the improved GA ［J］.Transactions of the Japan Society of Mechanical Engineers，Part C，2002，68（9）：2577－2584.

［4］ACHARYYA Arnav，Losalka Arpan，GUPTA Pravir Singh，et al.Development of an automated examination seating arrangement generation system using music inspired harmony search algorithm［J］.Advances in Intelligent and Soft Computing，2011，130（1）：301－309.

［5］Abramson D.Constructing school timetables using simulated annealing：Sequential and parallel algorithms［J］.Management Science，1991，37（1）：98－113.

［6］徐尚進.普通高校課務(wù)管理排考系統(tǒng)的算法設(shè)計［J］.廣西科學(xué)院學(xué)報，1998，14（1）：40－43.

［7］朱書尚，曹世勇，鄒瀟湘.排考問題的數(shù)學(xué)模型及其算法［J］.系統(tǒng)工程，1999，17（2）：62－65.

［8］田嶺.大學(xué)自動排考算法設(shè)計與實現(xiàn)［J］.計算機工程與設(shè)計，2007，28（5）：2443－2445.

［9］蔡木生.高校自動排考算法的設(shè)計與實現(xiàn)［J］.計算機工程與應(yīng)用，2010，48（24）：73－76.

［10］劉艷，程國忠，譚代倫.學(xué)院專業(yè)課自動排考算法的設(shè)計與實現(xiàn)［J］.綿陽師范學(xué)院學(xué)報，2012，30（2）：95－99.

［11］王卿，張亞文，張偉.高等學(xué)校排考染色匹配算法［J］.上海理工大學(xué)學(xué)報，2005，27（2）：157－161.

［12］董健興，欒勇，閆君政.基于圖論的高校排考算法［J］.計算機系統(tǒng)應(yīng)用，2011，20（5）：177－179.

［13］董傳良，仝月榮，洪奕茜.高校選課制下自動排考系統(tǒng)的設(shè)計和實現(xiàn)［J］.實驗技術(shù)與管理，2011，49（6）：13－15.

［14］齊萍.基于蟻群算法的高校排課系統(tǒng)優(yōu)化策略［J］.湖北工業(yè)大學(xué)學(xué)報，2010，16（02）：35－90.

［15］劉瑩.高校教學(xué)管理信息系統(tǒng)的設(shè)計與實現(xiàn)［D］.濟南：山東大學(xué)，2009：15－18.

［16］HAN K H，KIM J H.On the analysis of the quantum－inspired evolutionary algorithm with a single individual［J］.Evolutionary Computation，2006，13（4）：517－546.

［17］歐陽勇，李濤.高校自動排考系統(tǒng)設(shè)計與實現(xiàn)［J］.湖北工業(yè)大學(xué)學(xué)報，2009，27（4）：69－72.