基于SVC的考試時間安排的實現(xiàn)

殷玉霞， 張彬， 帥小應(yīng)

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

0 引言

考試安排是學(xué)校考試均要面對的問題，隨著高校在校生人數(shù)以及專業(yè)數(shù)量的增加，尤其是選修課程的增多，這些都帶給考試安排工作不小的壓力。同一學(xué)生選修的多門課程不能安排在同一時間段參加考試?？荚嚢才殴ぷ魇且环N典型的調(diào)度問題，在有限的時間區(qū)域約束條件下尋找最優(yōu)解使得考試安排的周期最短。

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

1 問題建模

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

表1為某班部分學(xué)生的選課表，則此部同學(xué)的選課關(guān)系可用圖1來表示。張山選修了“算法設(shè)計”與“神經(jīng)網(wǎng)絡(luò)”，這兩門課程分別用點A與點B表示并用邊(A，B)連接。

表1 學(xué)生選課表

圖1 課程關(guān)系圖

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

圖2 沖突矩陣

(1)

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

(2)

考試安排解決在一定約束條件下周期最短的優(yōu)化問題；設(shè)K為考試場數(shù)，同一時間段內(nèi)的考試為1場；N為課程總數(shù)，考試安排目標(biāo)如下：

(3)

約束條件：

(4)

(5)

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

2 算法

2.1 SVC算法

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

算法1

輸入：頂點數(shù)N

輸出：顏色數(shù)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 最小化考試周期

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

算法2

輸入：課程數(shù)N

輸出：考試安排

按度對課程進(jì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 場次調(diào)整

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

算法3

輸入：考試安排表

輸出：新考試安排表

對課程進(jìn)行排序

Fori=1 toN

Forj=1 tok

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

EndFor

EndFor

3 仿真實驗

運用C語言在Win 10系統(tǒng)中設(shè)計仿真程序，分別對圖1與圖3的課程進(jìn)行考試安排。首先運行算法2，安排結(jié)果如表2；再運行算法3，安排結(jié)果如表3。

圖3 15門課程的選課關(guān)系圖

表2 安排結(jié)果

表3 安排結(jié)果

4 總結(jié)

考試時間安排問題是高校教務(wù)期末工作的重點與難點問題，隨著學(xué)生人數(shù)與選修課程數(shù)的增多，考試安排問題也越來越復(fù)雜。把考試課程間的關(guān)系用圖結(jié)構(gòu)來表示，利用序列點著色算法與貪心法對考試時間進(jìn)行安排，得到周期最短的無沖突的考試安排。仿真結(jié)果表明本算法能有效地解決考試時間安排問題?？荚嚢才攀艿蕉喾N條件的約束，本算法沒有考慮到同一個學(xué)生考試間隔安排問題。今后將進(jìn)一步探討實際運用中各種約束條件下的安排優(yōu)化問題，如考試周期最短的前提下同一個學(xué)生選修課程考試間隔問題等。