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

張媛

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

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

1 排課問題分析

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

2 排課問題算法設(shè)計

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

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

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

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

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

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

圖1 排課算法流程圖

3 信息定義與預(yù)處理算法

3.1 基本信息定義

針對排課問題涉及的要素，設(shè)：

課程集合：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ù)定義

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

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

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

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

RNum(s)(s∈S)。

3.3 組合信息定義

課程任務(wù)集合，即預(yù)處理步驟的輸入，為：

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。

設(shè)任務(wù)組為：

Group={g|g=(c,h,l,s),c∈C,h∈H，l∈L,s∈S}。其中，表示任務(wù)元的為g，其余含義與task相同。則預(yù)處理步驟的輸出，即任務(wù)組的集合為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的元任務(wù)安排在r教室里。最終，輸出結(jié)果即為課表單元集合。

3.4 預(yù)處理算法

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

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

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

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

4.1 排課問題定義域

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

4.2 目標函數(shù)

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

表1 時間權(quán)值表

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

其中，g.l表示訪問任務(wù)元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）鄰域結(jié)構(gòu)、禁忌對象和候選解。

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

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

3）禁忌表及其長度。

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

4.4 禁忌搜索算法步驟

禁忌搜索算法步驟為：

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

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

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

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

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

算法流程，如圖2所示。

圖2 算法流程圖

5 教室分配

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

1）i←0。

2）i←i+1。若i大于預(yù)設(shè)的值Q，算法結(jié)束；反之，取課時分配的最優(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）尋找教室能夠容納的學(xué)生數(shù)略大于班級人數(shù)的教室r(Type(r)=g.s)，則進行下一步。

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

算法結(jié)束，輸出最終周課表CT。

6 仿真驗證

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

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

圖4 課表查詢與打印圖

7 結(jié)束語

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