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

張媛

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

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

1 排課問題分析

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

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

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

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

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

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

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

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

圖1 排課算法流程圖

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

3.1 基本信息定義

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

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

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

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

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

班級(jí)集合：C={c1,c2,...,cN}；

時(shí)間集合：T={t1,t2,...,tQ}。

3.2 基本函數(shù)定義

設(shè)c班級(jí)的人數(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)表示的是班級(jí)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時(shí)間，班級(jí)c被教師h講授課程l的元任務(wù)安排在r教室里。最終，輸出結(jié)果即為課表單元集合。

3.4 預(yù)處理算法

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

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

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

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

4.1 排課問題定義域

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

4.2 目標(biāo)函數(shù)

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

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

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

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

4.3 參數(shù)描述

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

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

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

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

2）鄰域結(jié)構(gòu)、禁忌對(duì)象和候選解。

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

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

3）禁忌表及其長度。

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

4.4 禁忌搜索算法步驟

禁忌搜索算法步驟為：

1）禁忌表初始化為空，即元素值全為0，隨機(jī)產(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é)束；否則進(jìn)行下一步，且iter←iter+1。

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

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

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

算法流程，如圖2所示。

圖2 算法流程圖

5 教室分配

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

1）i←0。

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

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

4）j←0 。

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

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

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

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

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

6 仿真驗(yàn)證

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

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

圖4 課表查詢與打印圖

7 結(jié)束語

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