袁子昂

（杭州電子科技大學(xué)計算機學(xué)院，杭州310018）

0 引言

高校期末排考場次分配，要將上萬名學(xué)生和數(shù)百門課程安排到若干場次，每一場次不能出現(xiàn)課程沖突（同場的任意兩門課程不能有相同的學(xué)生），也不能超過容量限制（考場數(shù)量和容量所限）?，F(xiàn)實中總是希望考試場次盡量少，以保證在一周左右完成考試。文獻[1]和文獻[2]證明了排考時間表是NP難問題，文獻[3]和文獻[4]提出了用頂點著色算法來解決排考場次分配問題，但未考慮容限。本文用帶權(quán)頂點著色算法求解容限約束下的場次分配問題，并給出了該算法在SQL Server上的具體實現(xiàn)，對其中的T-SQL腳本進行簡單修改就能適應(yīng)各學(xué)校的具體情況。

1 場次分配的帶權(quán)頂點著色算法

場次分配的輸入是選課集SC={（學(xué)號,課程號）}，用二部圖表示如圖1。

圖1 選課集二部圖

由選課集可導(dǎo)出帶權(quán)的課程沖突關(guān)系如圖2，圖2中的含權(quán)頂點表示課程，頂點的權(quán)表示學(xué)生數(shù)，頂點間的邊表示沖突，頂點的度表示與該課程有沖突的課程總數(shù)。

圖2 課程沖突關(guān)系圖

場次分配的輸出是場次集CT={（課程號,學(xué)生數(shù),場次號）}，其中課程號和學(xué)生數(shù)可由選課集得到，初始時，所有的場次號均為0，表示課程待分配。分配完成后，場次號取值為1,2,…,n，并且滿足約束：場次號相同的課程彼此不沖突，同一場次的學(xué)生數(shù)之和低于限額。

在不考慮容限約束時，場次分配與頂點著色問題等價，可用貪心算法求解：①k=1。②若圖中沒有無色頂點則結(jié)束；否則，從圖中找度數(shù)最大的頂點，染色為k。③從無色且與k色頂點無連接的頂點中，找與無色頂點連接數(shù)最大的頂點，染色為k；重復(fù)本步直到?jīng)]有滿足條件的頂點。④從圖中刪除k色頂點及其關(guān)聯(lián)的邊。⑤k=k+1，回第②步。以上步驟如圖3a,3b,3c所示，最后結(jié)果如圖3d，8個頂點被分為3組：第1組（1,4,5）,第 2 組（2,6,7,8）和第 3 組（3）。

圖3 頂點著色貪心算法

考慮容限時，場次分配與帶權(quán)頂點的著色問題等價，每次對一個新的頂點染色時，要檢查改色節(jié)點的權(quán)重之和是否超過容限。容限記為max，余量記為rest，頂點和權(quán)重記為vi和wi，對以上算法進行調(diào)整：

帶權(quán)頂點最小著色算法

（1）k=1。

（2）若圖中沒有無色頂點則結(jié)束；否則，找到度數(shù)最大的頂點vi，染色為k,rest=max-wi。

（3）從無色且權(quán)值小于rest且與k色頂點無連接的頂點中，找到與無色頂點連接數(shù)最大的頂點vi，染色為k,rest=rest-wi,重復(fù)本步直到?jīng)]有滿足條件的頂點。

（4）從圖中刪除k色頂點及其關(guān)聯(lián)的邊。

（5）k=k+1,回第（2）步。

2 算法的SQL實現(xiàn)

在SQL Server上，通過設(shè)計數(shù)據(jù)庫、預(yù)處理、分配、檢查結(jié)果等四個步驟完成場次分配。

2.1 數(shù)據(jù)庫設(shè)計

在SQL Server上創(chuàng)建一個數(shù)據(jù)庫，其中創(chuàng)建三個表：選課表、場次表和沖突表。

表1 選課表

選課表用于存放選課數(shù)據(jù)，表中的每一行表示一個學(xué)生要參加一門課程的考試。

表2 場次表

場次表用于存放場次分配的中間過程和結(jié)果，表中的每一行表示一門課程分配進一個場次，若有n門課程，則共有n行。所有的課程的初始場次都為0，表示未分配；在分配過程中，課程的場次將分別變?yōu)?,2,…，場次號相同的課程屬于同一場次。

表3 沖突表

沖突表用于存放課程關(guān)系，沖突值取1/0表示有/無沖突。為編程方便，一對課程c1和c2會存入兩行：（c1,c2,1/0）和（c2,c1,1/0）。沖突表中的初始數(shù)據(jù)由選課表導(dǎo)出，在分配過程中，數(shù)據(jù)將逐漸減少直至為空。

2.2 預(yù)處理

預(yù)處理用于生成選課表數(shù)據(jù)、場次表初始數(shù)據(jù)和沖突表初始數(shù)據(jù)。

選課表數(shù)據(jù)可從Excel表導(dǎo)入到數(shù)據(jù)庫，也可從現(xiàn)有的信息系統(tǒng)中取得。

場次表初始數(shù)據(jù)從選課表中取得，所有課程的初始場次都置為0。

生成場次表初始數(shù)據(jù)的T-SQL腳本：

沖突表初始數(shù)據(jù)從選課表中取得。首先取得所有的課程對，若有n門課程，則得到n*（n-1）行，所有課程對的沖突都設(shè)為0；然后從選課表中找到有沖突的課程對，將其沖突設(shè)為1。

生成沖突表初始數(shù)據(jù)的T_SQL腳本：

由于沖突表在分配過程中數(shù)據(jù)會逐漸減少，為了對分配后的結(jié)果進行檢查，對沖突表備份得到備份沖突表。

2.3 場次分配

場次分配用一個存儲過程來實現(xiàn)，該存儲過程有一個輸入?yún)?shù)@max，執(zhí)行該過程會更新場次表。

創(chuàng)建存儲過程的T_SQL腳本：

2.4 檢查結(jié)果

對得到的場次表進行檢查，一是檢查是否所有課程都分配了場次，只要場次表中所有行的場次列都不為0，即說明檢查通過；二是檢查每一場次內(nèi)有無沖突，只要場次相同的課程沖突值之和為0，即通過檢查。三是檢查每一場次考生數(shù)是否超過容限。

場內(nèi)沖突檢查的SQL腳本：

3 實驗

取某校2017學(xué)年第一學(xué)期的選課數(shù)據(jù)，含10037名學(xué)生，193門課程，36714條選課記錄，每一場次的容限為5000人。經(jīng)過預(yù)處理，得到課間沖突關(guān)系共2796對，場次分配過程在5秒內(nèi)執(zhí)行結(jié)束，得到考試場次共20場，分場次的課程數(shù)和學(xué)生人數(shù)如表4。

實驗中發(fā)現(xiàn)，后分配的課程不能移入先分配的場次，但某些先分配的課程可以移入某些后分配的場次，這一現(xiàn)象是貪心算法造成的。如圖3中，被放入第1組的5號節(jié)點，也可以放入第2組；而第2組中的6,7,8號節(jié)點，可以全部放入第3組。在實際應(yīng)用中，這一特點為實際排考工作提供了一定的調(diào)整余地。

表4 場次考生數(shù)量

4 結(jié)語

本文將帶容限約束的排考場次分配問題轉(zhuǎn)化為帶權(quán)圖頂點最小著色問題來求解，給出了一種貪心算法，并給出了算法在SQL Server平臺上的具體實現(xiàn)，解決方案易于部署實現(xiàn)，對本文中的T-SQL腳本進行簡單修改就能適應(yīng)各學(xué)校的具體情況。