基于禁忌搜索的排課系統(tǒng)的設計

張媛，祁蘭

（榆林學院 數(shù)學與統(tǒng)計學院，陜西 榆林719000）

基于禁忌搜索的排課系統(tǒng)的設計

張媛，祁蘭

（榆林學院 數(shù)學與統(tǒng)計學院，陜西 榆林719000）

為了實現(xiàn)自動排課，以提高高等學校的工作效率。提出了一種基于禁忌搜索的排課方案，該系統(tǒng)首先采用網(wǎng)絡流的處理方法，將排課任務分成若干組；再使用禁忌搜索算法，找到時間和任務組的最優(yōu)解，從而實現(xiàn)自動排課。實際應用表明，該系統(tǒng)具有使用快捷方便等特點，達到了設計要求。

排課；分組；禁忌搜索；最優(yōu)化

排課是高校教學管理中一項基本且重要的工作。在教學改革不斷深化，教學任務逐年增加的情況下，如何利用有限的資源，實現(xiàn)配置的最優(yōu)化，有著重要的意義。排課問題是涉及班級、時間、教室、教師等資源的決策優(yōu)化問題，在排課系統(tǒng)中，處理排課問題所用的算法處于核心地位，由于排課問題本身的復雜性，尋找一個有效的算法還是有相當?shù)碾y度。

系統(tǒng)采用禁忌搜索算法解決排課問題。首先使用網(wǎng)絡最大流算法預處理，把排課任務分成若干組，以保證同一時間內(nèi)可以進行同一個組的任務，并且教室的供應數(shù)量大于需求數(shù)量；再使用禁忌搜索找到最佳組合的任務集；。最后給任務分配教室輸出課表[1]。

1　禁忌搜索算法介紹

禁忌搜索算法是一種啟發(fā)式算法，可用于解決組合優(yōu)化問題。禁忌搜索從模擬人的智力過程入手，在算法中引入記憶裝置。算法從一個初始可行解出發(fā)，選擇一系列的特定搜索方向作為試探，選擇實現(xiàn)使目標函數(shù)值減少最多的移動。為了避免陷入局部最優(yōu)解，禁忌搜索中采用了一種靈活的“記憶”技術(shù)，即對已經(jīng)進行的優(yōu)化過程進行記錄和選擇，指導下一步的搜索方向，這就是禁忌表的建立[2]。禁忌表中保存了最近若干次迭代過程中所實現(xiàn)的移動，凡是處于禁忌表中的移動，在當前迭代過程中是不允許實現(xiàn)的[3]，這樣可以避免算法重新訪問在最近若干次迭代過程中已經(jīng)訪問過的解，從而防止了循環(huán)，幫助算法擺脫局部最優(yōu)解[4]。另外，為了盡可能不錯過產(chǎn)生最優(yōu)解的移動，禁忌搜索還采用藐視準則的策略，當某個禁忌候選解的適配值優(yōu)于“best so far”狀態(tài)，則解禁此候選解為當前狀態(tài)和新的“best so far”狀態(tài)[5]。

2　禁忌搜索的排課模型

榆林學院的現(xiàn)狀是，現(xiàn)有15個院系，全日制在校學生14869人，教職員工957人。學校現(xiàn)有普通教室128個，媒體教室46個，語音教室5個，排課任務繁重。根據(jù)排課人員的經(jīng)驗，考慮的問題主要有如下6條：

1）同一教師在同一時間只能安排一門課程；

2）同一班級在同一時間只能安排一門課程；

3）同一教室在同一時間只能安排一門課程[6]；

4）教室容量大于班級人數(shù)，且教室類型符合課程要求；

5）權(quán)值較高的課程安排在上午，權(quán)值低的課程安排在下午；

6）每周上多次的課程，課程間隔應大于一天。

前4條為硬標準，后兩條為軟標準。根據(jù)實際情況，建立如下模型。

授課任務：TASK={task|task=（c，h，l，s，w），c∈C，h∈H，l∈L，s∈S，w＞0）}表示c班級上h教室的l課程，教室類型為s，課時是w。TrType（c,h）表示h教師給c班級上課的教室類型

課表單元：CT={ct|ct=（C，h，l，t，r），c∈C，h∈H，l∈L，t∈T，r∈R}，表示h教師給c班級上的l課程安排在t時間的r教室。排課問題的目標是找出一個從授課任務到教室時間的二元組的映射關系[7]：F：task∈TASK→（t，r）∈T×R該映射關系滿足以下約束條件，且目標函數(shù)值是最優(yōu)的[8]。

表示上課人數(shù)小于等于教室容量，且教室類型滿足課程需要。

根據(jù)上述目標函數(shù)和約束條件，建立模型如下：

這里f（x）表示盡量滿足的條件，且假定最優(yōu)解能使得f （x）值最大。

3　禁忌搜索求解排課問題的算法實現(xiàn)

根據(jù)設計排課系統(tǒng)的需要，結(jié)合榆林學院的實際情況，排課系統(tǒng)的算法設計流程如圖1所示[10]。

圖1　排課工作流程

3.1輸入任務集合

授課任務集合TASK={task|task=（c，h，l，s，w），c∈C，h∈H，l∈L，s∈S，w＞0）}是預處理部分的輸入；任務組集合GList= {Group}是預處理部分的輸出，對其進行時間分配，實際是尋找一個從任務組集合到時間集合的一個映射；課表單元集合CT就是最終的輸出結(jié)果[1]。

3.2分組預處理

分組預處理部分的解決采用基于網(wǎng)絡流的預處理算法[11]。網(wǎng)絡流G=（V，E）是一個有向圖，其中每條邊（V，E）均有一個非負的容量值，記為C=（U，V）≥0。如果（U，V）不包含E，則可以規(guī)定C=（U，V）=0。網(wǎng)絡流中有兩個特殊的頂點，即源點s和匯點t。

解決最大流問題，我們使用的是增廣路算法。增廣路算法是一種迭代算法[12]，首先要對圖中所有頂點對的流大小清零，此時的網(wǎng)絡流大小也為0；在每次的迭代中，通過尋找一條“增廣路徑”來增加流的值[13]。增廣路徑可以看作是源點s到匯點t的一條路徑，并且沿著這條路徑可以增加更多的流，直至迭代無法再找到增廣路徑位置，此時必然從源點到匯點的所有路徑中都至少有一條邊的滿邊 （即邊的流的大小等于邊的容量大?。?。分組預處理完成后，得到一個任務組集合GList，再對其進行時間分配[14]，主要使用禁忌搜索算法進行最優(yōu)化求解。

3.3基于禁忌搜索的時間分配算法

以隨機方式產(chǎn)生初始解，如x*=（1，2，…，10，0，0，0，0）[15]，f （x）表示目標函數(shù)值，禁忌表tabulist:=Φ；，最優(yōu)解best_x:=Φ；

循環(huán)：

while結(jié)束條件不滿足do

begin

1）生成x的鄰域N（x）

2）生成候選解集：

從x的鄰域N（x）中找出一定數(shù)量的解作為候選解集合openlist（x）.

3）搜索：

4）禁忌表更新

算法運行結(jié)束，求得最優(yōu)解。再基于貪心思想分配教室，最后就能得到周課表的分配方案。

3.4算法運行實例

如圖2所示，是算法運行完畢，生成的課程查詢頁面的截圖。

4　結(jié)束語

該系統(tǒng)符合教室分配的實際情況，可以方便的調(diào)整算法參數(shù)，使得排課結(jié)果更令人滿意，且有較高的搜索效率。該排課系統(tǒng)已用于榆林學院數(shù)統(tǒng)院排課系統(tǒng)進行測試，實際應用表明該系統(tǒng)具有排課快捷方便、人機界面友好等特點，達到了設計要求。

[1]彭超.禁忌搜索求解排課問題的應用研究[D].西安電子科技大學，2007.

[2]王連山.關于遺傳、蟻群、禁忌搜索算法的比較[J].電腦編程技巧與維護，2009（24）18-21.

[3]郭娜.基于節(jié)約算法和移動方向的禁忌搜索算法 [D].大連：大連理工大學，2009.

[4]李益華，林文南.一種改進的Tabu Search算法及其在區(qū)域電網(wǎng)無功優(yōu)化中的應用 [J].電力科學與技術(shù)學報，2008 （2）：60-65.

[5]劉光遠，賀一，溫萬惠.禁忌搜索算法及其應用[M].北京:科學出版社，2014.

[6]王惠君，方明.淺析高校課程表的編排[J].中國科技信息，2010（11）：273-274，284.

[7]陳小紅，陳曉東.禁忌搜索算法解決賦權(quán)覆蓋問題[J].價值工程，2011（26）：89-91.

[8]劉長彬.基于遺傳算法和禁忌搜索算法的排課系統(tǒng)研究[J].軟件導刊，2014（10）：68-70.

[9]周芬.遺傳算法在多校區(qū)排課系統(tǒng)中的應用[J].科技信息，2010（6）：234.

[10]張媛.基于J2EE的實驗室排課系統(tǒng)的設計與實現(xiàn)[D].西安：西安電子科技大學，2010.

[11]趙禮峰，陶曉莉.最小費用最大流問題的一種新算法[J].計算機技術(shù)與發(fā)展，2014（1）：130-132.

[12]馬毅，嚴余松，戶佐安.網(wǎng)絡優(yōu)化的最大利潤問題及其增廣路算法[J].計算機工程與應用，2015（1）：1-4，80.

[13]王勤波.最小費用流問題及其擴展[D].青島：青島大學，2009.

[14]丁振國，趙紅維.禁忌搜索求解排課問題的應用研究[J].微電子學與計算機，2008（4）：27-29.

[15]鄧志杰.基于圖模型與遺傳算法相結(jié)合的排課問題研究[J].信息技術(shù)，2014（1）：146-149.

Design of course scheduling system based on Tabu Search

ZHANG Yuan，QI Lan
（School of Mathematics and Statistics，Yulin University，Yulin 719000，China）

In order to realize the automatic arrangement and improve the work efficiency of the university.The system is based on the method of network flow，which is divided into several groups.Then，the optimal solution of the time and task groups is found by using the tabu search algorithm.The practical application shows that the system has the characteristics of quick and easy use，and can meet the design requirements.

scheduling；grouping；tabu search；optimization

圖2　課程查詢頁面截圖

TN915.02-34；TP391

A

1674－6236（2016）22-0071-03

2015-11-23稿件編號：201511221

榆林學院青年科技基金（14yk33）

張 媛（1981—），女，陜西榆林人，碩士，講師。研究方向：計算機及其應用、算法。