基于分治法的高校考試安排算法

駱紹燁

（莆田學(xué)院電子信息工程系，福建莆田 351100）

0 引 言

現(xiàn)代教育理論認(rèn)為，考試是教育評價的一種重要手段，其作用主要表現(xiàn)在以下兩個方面：其一是評估教師的課堂教學(xué)效果，促使教師總結(jié)教學(xué)經(jīng)驗，改進教學(xué)方法；其二是評價檢測學(xué)生的學(xué)習(xí)效果，了解學(xué)生對所學(xué)知識和技能的掌握情況和應(yīng)用能力，促使學(xué)生學(xué)習(xí)以及幫助改進學(xué)習(xí)方法［1］。

傳統(tǒng)的考試安排方式主要是依靠教學(xué)管理人員的人工安排，雖然他們在考試安排中逐漸積累了一些經(jīng)驗和方法［2］，但是，隨著專業(yè)的不斷增加和細(xì)化，組織考試的工作量越來越大［3］，而且組織考試的時間大多是在學(xué)期中或?qū)W期末，此時教學(xué)管理的工作又相對集中，時間有限，任務(wù)又重，人工管理的方式暴露出了不少的弊端。

計算機自動排考是一個時間表問題，把考試安排問題化為計算領(lǐng)域有約束的時空組合優(yōu)化問題進行求解［4］。由于約束條件復(fù)雜，問題規(guī)模龐大，對于排考這類問題迄今為止還沒有找到在多項式步驟內(nèi)解決的有效算法，只能在一定范圍內(nèi)尋求最優(yōu)解。

1 排考問題描述

從排考過程中涉及到的可能引起潛在資源競爭沖突的角度，排考問題涉及到的因素主要有：時間、課程、場地、班級和教師。其中班級又分為行政班級和考試班級。行政班級指招生時注冊的班級，每個行政班級有編號、名稱、院系、專業(yè)和學(xué)生人數(shù)。每個行政班同一時間只能考一門課程?？荚嚢喔拍畹漠a(chǎn)生主要是基于有些課程由于人數(shù)過多或者其它原因需要拆班考試。

1.1 約束條件

排考的約束條件可分為兩大類：硬約束和軟約束。

1．1．1 硬約束

硬約束表示必須遵守的約束條件。

硬約束主要包括以下幾個方面：

1）同一班級在同一時間不能考兩門不同的課程。

2）同一教師在同一時間不能安排兩個考場。

3）同一考卷的班級應(yīng)在同一時間安排考試。

4）考場的容積必須大于在該處考試的學(xué)生的人數(shù)。這里所說的容積不是考場的總座位數(shù)，而應(yīng)指按照考試要求所能排下的最大學(xué)生數(shù)。

5）安排監(jiān)考的教師必須在崗。

1．1．2 軟約束

軟約束表示在排考過程中盡可能滿足的約束條件，但不滿足也無妨，軟約束條件的滿足與否往往與排考實際情況有關(guān)。

軟約束主要包括以下幾個方面：

1）該課程的授課教師應(yīng)參加監(jiān)考，且盡可能安排在該教師所授課班級監(jiān)考。這樣可以方便解決考試中出現(xiàn)的諸如試卷不清等問題。

2）課程安排有一定間隔，讓學(xué)生有足夠備考時間。一天內(nèi)一個班級盡可能只安排一門考試。

3）教師安排監(jiān)考次數(shù)適當(dāng)。

4）滿足監(jiān)考教師監(jiān)考意愿偏好。

5）在指定時間段內(nèi)安排考試。

1.2 排考目標(biāo)

由約束條件可以看出，對于排考問題實際上是一個組合規(guī)劃問題，但要求出問題的最優(yōu)解卻是不可能的，雖然約束條件能幫助我們進行求解，但是隨著問題范圍的擴大，組合方案呈爆炸式增長，特別是高校的排考問題，其排考難度更大［5］。因而，我們必須放棄尋求最優(yōu)解，事實上，迄今為止，對排考和排課問題的研究也證明了最優(yōu)解是極難求出的，只能“退而求其次”，尋找問題的近似最優(yōu)解。只要這個解能夠在滿足硬約束條件的前提下，盡可能地滿足軟約束，滿足各方面的需求，使得解決方案合理可行。

2 系統(tǒng)自動排考算法設(shè)計

隨著資源數(shù)量的增大，排考問題因考試編排選擇方案的劇增，就可能出現(xiàn)“組合爆炸”，致使排考問題變得錯綜復(fù)雜，從而直接影響到排考問題的解［6］。為了降低排考算法的復(fù)雜性，在自動排考時運用分治法的思想，將問題空間分解成多個小規(guī)?？臻g，分別求出各個小空間的解，再組成整個問題的解的方法。

分治法的思想就是將整個問題分成若干個問題后分而治之［7］。當(dāng)要求解一個輸入規(guī)模為n，且n取值又相當(dāng)大的問題時，直接求解往往是非常困難的，有的甚至根本沒法直接求出。每當(dāng)遇到這類問題時，分治法往往能發(fā)揮很大的作用。任何一個可以用計算機求解的問題所需的計算時間都與其規(guī)模有關(guān)。問題的規(guī)模越小，越容易直接求解，解題所需的計算時間也越少［6］。

運用分治法解決排考問題，把問題空間逐層分解成多個小規(guī)?？臻g，可以減小問題規(guī)模。排考時，先將課程分成公共課與專業(yè)課兩種類型，因為公共課與專業(yè)課有著各自不同的特點。公共課課程數(shù)量少，但參加考試的班級較多，而專業(yè)課則恰恰相反。將兩種課程類型分開，有利于采取不同的分配方案，同時也降低了問題的規(guī)模。其次，在專業(yè)課排考時，將整個學(xué)校的考試安排調(diào)度分解成各個開課院系的考試安排，問題空間再次縮小。最后將排考過程分解成安排時間、安排場地和安排監(jiān)考老師3個相對獨立的子問題。安排時間時，只需要考慮課程與時間的搭配；安排場地時，只需考慮考試班級與考試場地的搭配；安排監(jiān)考教師時，只需保證監(jiān)考教師的監(jiān)考時間不沖突即可。由以上可以看出，在逐層的分解過程中，求解的難度也不斷降低，排考得到了更簡單和更迅速的求解。分解到位的排考算法主要通過以下步驟實現(xiàn)。

1）選取課程。為了減少排考過程中可能出現(xiàn)的沖突，采取先難后易的原則，不好安排的課程先排，即容易在排考時出現(xiàn)沖突的、排考條件要求較難滿足的課程優(yōu)先進行排考。如果這些課程在排考后期才開始安排，此時很多資源已被占用。因為雖然總的資源數(shù)量是一定的，但到了排考的后期，剩余的資源特別可能會出現(xiàn)類似存儲管理中的資源碎片問題，即大量空余的資源很少，取而代之的是分布零散的資源碎片。這時為這些較難安排的課程尋找到適合的資源就變得更難了，也就影響了排考的順利進行。排考過程中，課程的參加考試班級數(shù)、參加考試班級的人數(shù)、參加考試班級的考試課程數(shù)等多個因素都會影響課程的考試安排難度，但影響最大的因素還是課程的參加考試班級數(shù)。

2）貪心法安排時間。選定待排考課程之后，接著就是為課程安排考試時間，公共課的考試時間由排考人員直接指定，專業(yè)課程的考試時間在計算機自動排考時是由系統(tǒng)根據(jù)權(quán)值法和貪心法選定。

在安排專業(yè)課程考試時，排考人員首先需要計算每個可排考時間的權(quán)值。管理員可以根據(jù)需要將一天的考試時段分成1～5個不等的時間段。將所有可以排考的時段的權(quán)值存放在權(quán)值數(shù)組periodstate［］中，periodstate［X］表示第X個時間段的權(quán)值。當(dāng)我們需要表示考試安排區(qū)間中的第M天的第L個時段的權(quán)值時，有如下公式：

式中：N——每天可排考的時段數(shù)。

在為課程選擇考試時間時，首先初始化時段權(quán)值數(shù)組，將所有的考試時段的初始權(quán)值為同一值10 000。然后逐時段分析計算各個考試時段的權(quán)值。權(quán)值的計算方法如下：

首先，如果該時段排考課程中的任何一個參考班級在此時段已安排了考試，則該時段的權(quán)值為0。其次，為了使得軟約束中的要為學(xué)生留有一定的備考時間的條件盡量得到滿足，一個班級盡可能不在一天安排多場考試，即一天在可能的情況下最多只安排一場考試。因此，檢查該天是否有班級已安排了考試課程，如果有，每增加一個已在該天安排了考試課程的班級，則相應(yīng)地降低該時段的部分權(quán)值。

在使用權(quán)值的計算辦法處理完所有時段的權(quán)值后，就可以使用貪心策略來選擇課程的考試時間了。貪心法是一種改進了的分級處理方法，就是在對問題求解時，總是做出在當(dāng)前看來是最好的選擇，每一步都應(yīng)是局部最優(yōu)解，不從整體最優(yōu)上加以考慮，所做出的僅是在某種意義上的局部最優(yōu)解［8］。貪心法通過不斷求解局部最優(yōu)解逐步構(gòu)造全局解的方式，對許多問題可以產(chǎn)生整體最優(yōu)解，即使不能得到整體最優(yōu)解，也能找到最優(yōu)解的較好的近似解。并且排考問題實際上并不一定需要找出整體最優(yōu)解，排考問題最優(yōu)解的定義也是個難題。所以在很大程度上，只需要求得一個次優(yōu)解或者滿足解即可。在安排課程考試時間上采用貪心法，能在保證速度的前提下求得局部最優(yōu)解，符合速度和效用的平衡，從而獲得整體最優(yōu)解的良好特性，進而使其在排考系統(tǒng)的應(yīng)用中能夠發(fā)揮其主要的特性。

3）最佳適應(yīng)法安排場地。最佳適應(yīng)算法（Best Fit）是動態(tài)存儲分配解決方案中最為常見的一種方案。最佳適應(yīng)算法就是在內(nèi)存空間中為將要加入的作業(yè)選擇大于該作業(yè)需要的空間大小，并且是最小的內(nèi)存空間來存放該作業(yè)［9］。排考時的安排考試場地與模擬內(nèi)存分配十分類似，可以模擬其分配方式。

安排考試場地，首先必須從數(shù)據(jù)庫中獲取在排的考試班級的人數(shù)K，接著從數(shù)據(jù)庫中獲取屬于開考班級院系且容積大于K的所有考試場地的信息，然后逐個考試場地進行比較選擇。比較選擇時，在確定考試場地在安排的課程考試時間時是空閑的情況下，計算考試場地容積S與班級人數(shù)K的差值，與已有的場地中的容積與班級人數(shù)之差的最小值MIN（S－K）做比較。如果當(dāng)前的S－K值更小，則記錄下當(dāng)前的考試場地編號和新的MIN（S－K），否則直接選取下一個場地。如此判斷比較直至比較完所有的考試場地，此時記錄的考試場地即是算法所求的場地。

4）等概率分配法安排監(jiān)考教師。在安排了考試的時間和考試場地之后，最后要做的是安排監(jiān)考教師。依據(jù)高校的有關(guān)考試規(guī)定，每個考場安排兩位監(jiān)考教師監(jiān)考。監(jiān)考教師原則上選取學(xué)生所在系的教師。在安排監(jiān)考教師時應(yīng)考慮教師的在崗情況及監(jiān)考意愿。同時，在滿足教師監(jiān)考意愿的前提下，應(yīng)考慮教師工作量的均衡，因而對于可任意參加監(jiān)考的教師使用等概率分配法來安排監(jiān)考教師。為了方便解決考試中可能出現(xiàn)的一些問題，在安排監(jiān)考時，優(yōu)先安排授課教師參加監(jiān)考，如果該授課教師還未被安排監(jiān)考，則將其安排到他所擔(dān)任課程的班級監(jiān)考。然后獲取所有在崗且愿意參加監(jiān)考的教師信息，以相同的概率分配監(jiān)考任務(wù)。

3 結(jié) 語

排考問題是一個有約束的、非線性的、模糊多目標(biāo)優(yōu)化的、難解的、時空組合的數(shù)學(xué)問題［4］。目前還沒有找到在多項式步驟內(nèi)解決的有效算法，只能在一定范圍內(nèi)尋求最優(yōu)解。根據(jù)高校的具體實際所設(shè)計的排考算法實現(xiàn)較容易，求出解的合理性也較高，能適應(yīng)大部分高校排考系統(tǒng)算法設(shè)計的要求。

［1］ 朱菊芳．高等教育學(xué)教程［M］．南京：南京師范大學(xué)出版社，1995．

［2］ 王玲．分布估計算法在排考中的應(yīng)用［D］：［碩士學(xué)位論文］．長沙：湖南師范大學(xué)，2008．

［3］ 李紅，陳晏輝．高校課程考試管理的思考［J］．長春工業(yè)大學(xué)學(xué)報：高教研究版，2008，29（4）：31－32．

［4］ 張磊，張博鋒．分組遺傳算法優(yōu)化大學(xué)考試時間表［J］．計算機工程與應(yīng)用，2009，45（23）：236－238．

［5］ 胡荷芬．高校考試自動安排算法研究和系統(tǒng)設(shè)計［D］：［碩士學(xué)位論文］．上海：上海師范大學(xué)，2008．

［6］ 唐洪英，周敏．基于分層次、貪心算法的排課系統(tǒng)的設(shè)計與實現(xiàn)［J］．微計算機信息，2006，22（3）：237－240．

［7］ 胡峰，王國胤．基于分治法的快速確定規(guī)則獲取算法［J］．模式識別和人工智能，2010，23（3）：349－356．

［8］ 常友渠，肖貴元，曾敏．貪心法的探討與研究［J］．重慶電力高等?？茖W(xué)校學(xué)報，2008，13（3）：40－42．

［9］ 宗大華，宗濤，陳吉人．操作系統(tǒng)［M］．北京：人民郵電出版社，2009．