基于SVC的考試時間安排的實現

殷玉霞， 張彬， 帥小應

(泰州學院，1.圖書館，2.信息工程學院，江蘇，泰州 225300)

0 引言

考試安排是學校考試均要面對的問題，隨著高校在校生人數以及專業數量的增加，尤其是選修課程的增多，這些都帶給考試安排工作不小的壓力。同一學生選修的多門課程不能安排在同一時間段參加考試。考試安排工作是一種典型的調度問題，在有限的時間區域約束條件下尋找最優解使得考試安排的周期最短。

針對考試安排問題，張磊等[1]建立學生選課關系圖，運用關系著色圖對時間表問題進行了研究，開發了業余大學的考試安排系統。針對學校希望縮短考試周期而學生渴望增大考試間隔的矛盾，運用分組遺傳算法優化大學考試時間表[2]。針對課程排考問題，李睿等[3]改進了FFD算法并將其應用在解決此類問題中。學生選修課程間的關系可用無向圖來表示，課程當作圖中的頂點，用邊連接有學生同時選修的兩門課程，相連接的課程不能安排在同一時考試。利用序列點著色(SVC，sequential vertex coloring)能很好解決考試安排問題。序列點著色是按照節點的度對節點進行降序排列，依次對節點進行著色，第1個節點著上顏色1；然后向后順序查找沒有著色的結點，用最小可用的顏色著色，直到所有節點均著上色[4]。馬國強等[5]利用微信小程序設計與開發了能發考試信息、安排考試時間的考試安排系統。針對高校考試安排中的資源、任務與時間分配合理要求，張培培等[6]利用貪心法設計了考試安排系統。本文利用貪心法與序列點著色方法選擇節點度最大的課程優先安排考試，直到所有的課程均安排為止，算法在確定考試安排周期最短的情況下提高了安排的靈活性。

1 問題建模

考試安排實際是時間表問題，其與教師、教室、時間、課程等諸多因素有關，是一個多約束條件的目標優化問題。同一個學生選修的若干門課程不能安排在同一場次考試。課程間的關系可用無向圖來表示，頂點表示課程，若兩門課被同一個學生選修則這門課程間用邊連接。

表1為某班部分學生的選課表，則此部同學的選課關系可用圖1來表示。張山選修了“算法設計”與“神經網絡”，這兩門課程分別用點A與點B表示并用邊(A，B)連接。

表1 學生選課表

圖1 課程關系圖

若兩個頂點間有邊則表示不能安排在同一場次考試，考試安排問題能夠用圖的著色方法解決。如圖1，頂點A與B間有邊(A，B)，則分別上不同的兩種顏色，A與B不能安排在同場考試。用最少色數使得所有的頂點著上色。用dij表示課程i與課程j沖突，如式(1)，全部選修課程的沖突矩陣如圖2。沒有沖突的課程可以安排在同一場次考試。

圖2 沖突矩陣

(1)

課程i安排在第j場考試則Sij設置為1，如式(2)。

(2)

考試安排解決在一定約束條件下周期最短的優化問題；設K為考試場數，同一時間段內的考試為1場；N為課程總數，考試安排目標如下：

(3)

約束條件：

(4)

(5)

約束條件(4)表示每門課程均要安排考試，約束條件(5)表示沖突的任意兩門課程不能安排在同一場次考試。

2 算法

2.1 SVC算法

SVC算法對節點進行排列，然后依次對節點進行著色，第1個節點著顏色1；向后順序查找沒有著色的結點，用最小可用的顏色著色，直到所有節點均著上色。算法如下：

算法1

輸入：頂點數N

輸出：顏色數c

Order nodes by specified criterion as 1,2,…,N

Colorc=1;

i=1;

While(i<=N)

Forj=1 tocdo

If vertex can color withjthen color; break;

EndFor

If(j>c)then colorc++;

i++;

EndWhile

2.2 最小化考試周期

安排考試時優先安排與其他課程沖突大的課程即圖中頂點度數大的課程，再安排沖突小的課程。首先按照節點的度對課程進行降序排列；然后依次對課程進行考試時間安排，第1門課程安排第1場次；再向后順序查找沒有安排的課程，用最小可用的場次安排考試，直到所有課程都安排了為止，具體如算法2。

算法2

輸入：課程數N

輸出：考試安排

按度對課程進行降序排列

初始化，場次k=1;課程i=1

While(i<=N)

j=1;Sij=0;

While 課程i不能安排在j場考試

j++;

EndWhile

Ifj>kthenk=j;

Sij=1;

i++;

EndWhile

2.3 場次調整

經過算法2每門課程均會合理分配考試的時間，但考試受到多種因素的影響，某門課程的安排可能會發生變動。為了在不增加考試周期的情況下靈活利用場次的安排，可人工指定若干門考試課程的考試場次，也可以利用算法3在算法2結果的基礎上為一門課程提供若干個可能的考試時間選擇。

算法3

輸入：考試安排表

輸出：新考試安排表

對課程進行排序

Fori=1 toN

Forj=1 tok

如果課程i也可以安排在j場次進行考試，則Sij=1

EndFor

EndFor

3 仿真實驗

運用C語言在Win 10系統中設計仿真程序，分別對圖1與圖3的課程進行考試安排。首先運行算法2，安排結果如表2；再運行算法3，安排結果如表3。

圖3 15門課程的選課關系圖

表2 安排結果

表3 安排結果

4 總結

考試時間安排問題是高校教務期末工作的重點與難點問題，隨著學生人數與選修課程數的增多，考試安排問題也越來越復雜。把考試課程間的關系用圖結構來表示，利用序列點著色算法與貪心法對考試時間進行安排，得到周期最短的無沖突的考試安排。仿真結果表明本算法能有效地解決考試時間安排問題。考試安排受到多種條件的約束，本算法沒有考慮到同一個學生考試間隔安排問題。今后將進一步探討實際運用中各種約束條件下的安排優化問題，如考試周期最短的前提下同一個學生選修課程考試間隔問題等。