張媛

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

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

1 排課問題分析

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

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）的情況。當課程任務(wù)安排數(shù)目多達上千個時，則該算法性能較差。因狀態(tài)鄰域空間的增大而使算法速率下降，計算時間增加，且沖突事件發(fā)生概率變大。從而使得解空間中不可行解增多，算法收斂速度降低[10-11]。

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

1）預(yù)處理分組授課任務(wù)。依據(jù)完成任務(wù)所需時間對任務(wù)進行分組，不同任務(wù)其老師跟學生也應(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 基于禁忌搜索的排課算法

對教學任務(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ù)教學效果的優(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]。對鄰域空間元素的適配值進行計算，并按從大到小的順序排列，存放在列表中。從列表表頭開始找起，找到滿足特赦準則的禁忌解或非禁忌解，且具有最大適配值來替代當前解。

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ù)求得當前解的領(lǐng)域解N（x），并確定y∈N(x)的適配值adt(y)，并由二元組以及適配值構(gòu)成候選解列表，且維持適配值不減。

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

5）對候選解所對應(yīng)的禁忌屬性進行判斷，并更新其中具有最佳狀態(tài)的非禁忌對象為當前解[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）尋找教室能夠容納的學生數(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)高校教學排課的復(fù)雜性質(zhì)與現(xiàn)行的大學課表問題模型求解方案的不足，本文分析了有約束的多目標NP完全問題與其各種解決方法。將現(xiàn)代啟發(fā)式的禁忌搜索算法與傳統(tǒng)經(jīng)典的網(wǎng)絡(luò)流算法進行結(jié)合，提出了一種基于禁忌搜索算法的排課系統(tǒng)設(shè)計方案。該方案將兩種算法優(yōu)勢互補，提高了問題處理能力，并用此方案設(shè)計了新的排課系統(tǒng)。通過實驗驗證與實際使用情況表明，所設(shè)計的系統(tǒng)操作性強且搜索速率得到較大提高，能夠完成目標要求，同時，具有可用性與可適性。