排考場次分配方法及其SQL實現

袁子昂

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

0 引言

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

1 場次分配的帶權頂點著色算法

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

圖1 選課集二部圖

由選課集可導出帶權的課程沖突關系如圖2，圖2中的含權頂點表示課程，頂點的權表示學生數，頂點間的邊表示沖突，頂點的度表示與該課程有沖突的課程總數。

圖2 課程沖突關系圖

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

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

圖3 頂點著色貪心算法

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

帶權頂點最小著色算法

（1）k=1。

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

（3）從無色且權值小于rest且與k色頂點無連接的頂點中，找到與無色頂點連接數最大的頂點vi，染色為k,rest=rest-wi,重復本步直到沒有滿足條件的頂點。

（4）從圖中刪除k色頂點及其關聯的邊。

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

2 算法的SQL實現

在SQL Server上，通過設計數據庫、預處理、分配、檢查結果等四個步驟完成場次分配。

2.1 數據庫設計

在SQL Server上創建一個數據庫，其中創建三個表：選課表、場次表和沖突表。

表1 選課表

選課表用于存放選課數據，表中的每一行表示一個學生要參加一門課程的考試。

表2 場次表

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

表3 沖突表

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

2.2 預處理

預處理用于生成選課表數據、場次表初始數據和沖突表初始數據。

選課表數據可從Excel表導入到數據庫，也可從現有的信息系統中取得。

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

生成場次表初始數據的T-SQL腳本：

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

生成沖突表初始數據的T_SQL腳本：

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

2.3 場次分配

場次分配用一個存儲過程來實現，該存儲過程有一個輸入參數@max，執行該過程會更新場次表。

創建存儲過程的T_SQL腳本：

2.4 檢查結果

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

場內沖突檢查的SQL腳本：

3 實驗

取某校2017學年第一學期的選課數據，含10037名學生，193門課程，36714條選課記錄，每一場次的容限為5000人。經過預處理，得到課間沖突關系共2796對，場次分配過程在5秒內執行結束，得到考試場次共20場，分場次的課程數和學生人數如表4。

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

表4 場次考生數量

4 結語

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