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

張媛

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

隨著高校規(guī)模的不斷擴大與學生數(shù)量的增多，在學校教學資源有限的情況下，排課問題已成為高校管理中的關注重點。學校的排課問題需要綜合教師、教室、時間和班級等各種因素，是一種具有多種約束與多目標決策尋優(yōu)的NP完全問題[1-2]。求解NP完全問題的各種方法中，現(xiàn)代啟發(fā)式優(yōu)化算法具有可行性[3-5]，其中禁忌搜索算法相比模擬退火等算法性能最優(yōu)。針對目前國內(nèi)高校教學排課的復雜性質與現(xiàn)行的大學課表問題模型求解方案的不足，本文分析了有約束的多目標NP完全問題與其各種解決方法，將現(xiàn)代啟發(fā)式的禁忌搜索算法與傳統(tǒng)經(jīng)典的網(wǎng)絡流算法進行結合，提出了一種基于禁忌搜索算法的排課系統(tǒng)設計方案。該方案將兩種算法優(yōu)勢互補，提高了問題處理的能力，并用此方案設計了排課系統(tǒng)。

1 排課問題分析

學校的課表編排需要綜合教師、教室、時間和班級四種因素，將其進行組合并得到最優(yōu)決策。因而需要進行規(guī)劃，獲得無沖突的課表。此外，課表還應滿足課程對教室類型、老師上課時間的要求等。高校上課時間一般為周1至周5，每天上課時間分為上午、下午和晚上。相同的老師既能上一門課同時也能上多節(jié)課，若相同班級一個老師教多門課，則將教師與課程設為同一變量會引起混亂；若一個教師教多個班級，則會出現(xiàn)同一時間給多個班級上課的沖突等問題。教室可分布在不同教學區(qū)域，一個完善且合理的課表需要令教師與學生上下節(jié)課走動少，并可將教學區(qū)域的遠近分為不同等級以進行課表的編排?？偨Y以上問題，課表編排過程中涉及同一老師同一時間只教一門課、同一教師同一時間只安排一門課、教室容量滿足上課人數(shù)等必須遵循的硬約束。同時，教師或學生的課程安排一天盡量在同一校區(qū)或教學區(qū)、同一門課安排在固定教室、多學時課程安排在不相鄰的教學日等盡量滿足的軟約束。

2 排課問題算法設計

設由教室、時間二元組組成的元素為pairi=(ti,ri)，表示在時間ti將第i個課程任務安排在ri教室里。則由此可構成，狀態(tài)空間的定義域為序列(pair1,pair2,...,pairi,...,pairn)[6-9]。序列的長度與任務的總數(shù)相等，但該做法僅適用于課程任務安排數(shù)目較少（低于1 000）的情況。當課程任務安排數(shù)目多達上千個時，則該算法性能較差。因狀態(tài)鄰域空間的增大而使算法速率下降，計算時間增加，且沖突事件發(fā)生概率變大。從而使得解空間中不可行解增多，算法收斂速度降低[10-11]。

針對將教室、時間二元組組成一個元素所出現(xiàn)的問題，本文將時間、教室當成課程排課問題中的兩個子問題來進行處理以加快算法搜索效率。因此，課表編排任務過程如下：

1）預處理分組授課任務。依據(jù)完成任務所需時間對任務進行分組，不同任務其老師跟學生也應有所不同，且不同類型的教室供應數(shù)量大于需求數(shù)量。

2）對不同的任務組與時間資源進行尋優(yōu)組合，使用禁忌搜索法尋找其最優(yōu)組合方式，判斷沖突的工作量因分組預處理而減少，從而提高算法的收斂速度。

3）對尋優(yōu)后的課程任務使用沖突檢查或貪心思想來安排教室，并形成課表。

排課算法流程，如圖1所示。

圖1 排課算法流程圖

3 信息定義與預處理算法

3.1 基本信息定義

針對排課問題涉及的要素，設：

課程集合：L={l1,l2,...,lp}；

教室集合：R={r1,r2,...,rk}；

教室類型集合：S={s1,s2,...,sD}；

教師集合：H={h1,h2,...,hM}；

班級集合：C={c1,c2,...,cN}；

時間集合：T={t1,t2,...,tQ}。

3.2 基本函數(shù)定義

設c班級的人數(shù)為CNum(c)(c∈C)。

r教室的容量、類型分別為：

Cap(r)、Type(r)(r∈R)。

s類型的教室數(shù)目為

RNum(s)(s∈S)。

3.3 組合信息定義

課程任務集合，即預處理步驟的輸入，為：

TASK={task|task=(c,h,l,s,w),c∈C,h∈H，l∈L,s∈S,w＞0}。其中，task=(c,h,l,s,w)表示的是班級c在s類型教室中上l課程的第w次課，老師是h。

設任務組為：

Group={g|g=(c,h,l,s),c∈C,h∈H，l∈L,s∈S}。其中，表示任務元的為g，其余含義與task相同。則預處理步驟的輸出，即任務組的集合為GList={Group}。

課表單元集合為：

CT={ct|ct=(c,h,l,t,r),c∈C,h∈H，l∈L,t∈T,r∈R}。其中，ct=(c,h,l,t,r)表示t時間，班級c被教師h講授課程l的元任務安排在r教室里。最終，輸出結果即為課表單元集合。

3.4 預處理算法

基于簡化排課模型的預處理算法為：點集X={x1,x2,...,xM}對應教師集合H，點集Y={x1,x2,...,xN}對應班級集合C。若xi與yi間連有w條邊，則表示教師hi給班級cj上w次課，從而形成一個G（X，Y，E）的二部圖[12-15]。一個課程任務組對應著G的一個匹配，實現(xiàn)分組的過程則是求取若干次最大匹配。

任務集合TASK是預處理模塊的輸入，任務組集合GList={Group}為模塊的輸出，本文利用網(wǎng)絡流算法對授課任務進行預處理分組。

4 基于禁忌搜索的排課算法

對教學任務進行分組后的任務集GList進行時間分配，主要目的是得到一個最優(yōu)的從任務集到時間集的函數(shù)映射HF：GList→T。其中，最優(yōu)化求解問題本文采用的是禁忌搜索算法。

4.1 排課問題定義域

假設任務集GList與時間集合T分別為GList={G1,G2,...,Gk,...,GK}、T={t1,t2,...,tq,...,tQ}。x=(a1,a2,...,aQ)表示定義域，且各分量與時間元素對應，表示為：

4.2 目標函數(shù)

時間集合是以兩個課時為單位，表示課程在課表中被安排的節(jié)次。高校上課時間一般為周1至周5，一天有4節(jié)課，每周有20單元的上課時間。根據(jù)教學效果的優(yōu)次對不同時間段的課時加以時間權值進行優(yōu)先規(guī)則的分配，時間權值表如表1所示。表中，數(shù)值為使用pt（t）所表示的時間t的權值。

表1 時間權值表

課程安排的優(yōu)先順序需要根據(jù)課程的重要程度進行確定。本文采用分配權值進行標識，課程l的權值為 pc（l），目標函數(shù)值為：

其中，g.l表示訪問任務元g中的信息。

4.3 參數(shù)描述

1）初始解和適配值函數(shù)。

首先通過隨機組合的方式產(chǎn)生從1～K的隨機排列組合，并在隨機排列中插入0以形成長度為Q的初始解。

本文采用的適配函數(shù)為：

adt(x)=f(x)-w×cols(x)。式中，目標函數(shù)值為f(x)，沖突次數(shù)為cols(x)，比例系數(shù)為較大整數(shù)w。沖突情況一種為同一天安排了同一門課程的兩次課；另一種為臨時安排的課程與事先安排的課程的沖突。

2）鄰域結構、禁忌對象和候選解。

交換整數(shù)序列的解x中元素的位置，即可得到其的鄰域解[16]。鄰域映射函數(shù)FN（x）定義如下：

互換位置的兩個整數(shù)形成一個二元組，用來表示禁忌對象以使得簡化計算。候選解整數(shù)序列集合可由鄰域函數(shù)確定[17]。對鄰域空間元素的適配值進行計算，并按從大到小的順序排列，存放在列表中。從列表表頭開始找起，找到滿足特赦準則的禁忌解或非禁忌解，且具有最大適配值來替代當前解。

3）禁忌表及其長度。

用二維數(shù)組構成禁忌表用來存放禁忌的二元組，其中表長為固定值，且將相應位置的元素設為禁忌的長度與迭代次數(shù)的和用來表示禁忌對象的“任期”。若算法迭代過程中的迭代步數(shù)大于禁忌對象相應元素值，則表明此禁忌對象“任期已滿”，稱為非禁忌的。反之，代表禁忌對象仍處于被禁忌狀態(tài)。

4.4 禁忌搜索算法步驟

禁忌搜索算法步驟為：

1）禁忌表初始化為空，即元素值全為0，隨機產(chǎn)生初始解x，設置迭代步數(shù)為iter，其初始值為0，最大值為Iter_Max，最優(yōu)解為best_x←x，最優(yōu)適配值為best_v←adt(x)。

2）判斷iter≥Iter_Max是否成立。若成立，則算法結束；否則進行下一步，且iter←iter+1。

3）利用映射函數(shù)求得當前解的領域解N（x），并確定y∈N(x)的適配值adt(y)，并由二元組以及適配值構成候選解列表，且維持適配值不減。

4）從候選解列表表頭開始判斷每個候選解y是否滿足adt(y)＞best_v。若滿足，則將y確定為當前的解，同時更新禁忌表相應元素任期以及重新計算最優(yōu)適配值best_x←x,best_v←adt(x)；若不滿足，則繼續(xù)下一步驟。

5）對候選解所對應的禁忌屬性進行判斷，并更新其中具有最佳狀態(tài)的非禁忌對象為當前解[18]，同時更新禁忌表中相應禁忌“任期”。

算法流程，如圖2所示。

圖2 算法流程圖

5 教室分配

在求得課時分配的最優(yōu)解x*后，需要確定每個授課任務時間與教室，從而生成最終的課表單元集合。之前假設任意時刻教室供給數(shù)量大于需求數(shù)量，因而無解情況不會發(fā)生，通過貪心算法來對教室進行分配，步驟如下：

1）i←0。

2）i←i+1。若i大于預設的值Q，算法結束；反之，取課時分配的最優(yōu)解x*的第i個元素ai，進行步驟3）。

3）判斷ai是否大于0。若成立，則取GList第ai個元素并進行步驟4）；否則返回步驟2）。

4）j←0 。

5）j←j+1 。若j＞|Gai|，返回步驟（2）；否則進行下一步。

6）取Gai的第j個元素g。若班級g.c已分配了教室r，且教室類型滿足要求，則進行步驟8）。

7）尋找教室能夠容納的學生數(shù)略大于班級人數(shù)的教室r(Type(r)=g.s)，則進行下一步。

8）CT←CT?{(g.c,g.h,g.l,r,ti) }，轉5）。

算法結束，輸出最終周課表CT。

6 仿真驗證

運用某高校真實課程數(shù)據(jù)對本文算法進行仿真驗證，在滿足各種需求的情況下無沖突產(chǎn)生，且迭代次數(shù)少，搜索效率高，所設計的系統(tǒng)參數(shù)調整方便[19]。圖3、圖4即為所設計的系統(tǒng)主界面圖、課表查詢與打印圖。

圖3 系統(tǒng)主界面圖

圖4 課表查詢與打印圖

7 結束語

針對目前國內(nèi)高校教學排課的復雜性質與現(xiàn)行的大學課表問題模型求解方案的不足，本文分析了有約束的多目標NP完全問題與其各種解決方法。將現(xiàn)代啟發(fā)式的禁忌搜索算法與傳統(tǒng)經(jīng)典的網(wǎng)絡流算法進行結合，提出了一種基于禁忌搜索算法的排課系統(tǒng)設計方案。該方案將兩種算法優(yōu)勢互補，提高了問題處理能力，并用此方案設計了新的排課系統(tǒng)。通過實驗驗證與實際使用情況表明，所設計的系統(tǒng)操作性強且搜索速率得到較大提高，能夠完成目標要求，同時，具有可用性與可適性。