◆范 萍

基于禁忌搜索算法的高職院校排課問題初探

◆范 萍

（泰山職業(yè)技術(shù)學(xué)院 山東 271000）

排課問題一直是各學(xué)校備受關(guān)注的重要問題。本文對禁忌算法在高職院校排課問題中的應(yīng)用進(jìn)行探討，通過目標(biāo)函數(shù)保證重要課程的排課時間，通過沖突函數(shù)，可以兼顧學(xué)生、老師的利益。

排課問題；禁忌搜索；沖突函數(shù)

排課問題一直是各學(xué)校關(guān)注的重要問題，隨著國家對職業(yè)教育的高度重視，高職院校發(fā)展迅速，招生規(guī)模不斷擴(kuò)大。編排合理的、科學(xué)的、人性化的課表對高職的教學(xué)管理起著至關(guān)重要的作用。排課問題首先需要合理安排時間和教師資源，保證老師能正常為學(xué)生上課，學(xué)生能正常入教室聽課，此外還需注重人性化，如盡量將老師的課程安排集中，避免老師多次來校上課，盡量將同一門課兩次授課間隔時間在一天以上，保證同學(xué)的聽課質(zhì)量等。

排課問題被證明是一個多約束條件的NP-hard問題，無法保證在多項(xiàng)式的時間內(nèi)找到最優(yōu)解。禁忌搜索算法是對局部搜索算法的擴(kuò)展，通過設(shè)置禁忌對象，跳出局部最優(yōu)化，得到全局最優(yōu)解。對優(yōu)化課表，解決排課沖突問題起到很好的作用。

1 排課問題的要求

為保證課程順利開展，排課需要滿足基礎(chǔ)條件和優(yōu)化條件。

1.1 基礎(chǔ)條件

一個班級只能在同一時間內(nèi)上一門課。

一個老師只能在同一時間內(nèi)教一門課。

兩門課不能在同一時間內(nèi)安排在同一個教室。

教室容量應(yīng)不小于學(xué)生容量。

1.2 優(yōu)化條件

同一門課程兩次授課時間在一天以上：

老師的課程安排盡量集中、連續(xù)授課，根據(jù)老師時間安排課程時間。

必修課、限選課盡量安排在上午，選修課、通識課安排在下午和晚上。

基礎(chǔ)條件是排課必須滿足的條件，優(yōu)化條件是完善課程安排的條件，不是必須滿足的條件。探討排課問題時，做如下假設(shè)和簡化：

（1）教室資源充足。各類型教室數(shù)遠(yuǎn)遠(yuǎn)大于同一時間段的需求。

（2）一天共有5個大課時，每門課每次上課僅占一個課時。

（3）不存在合班上課的情況。

（4）課表由學(xué)校統(tǒng)一安排，不存在課程提前被安排的現(xiàn)象。

2 排課問題的建模

教師集合：T={t1，t2，…，tm}；

班級集合：C={c1，c2，…，cn}；Num（ch）表示班級ch的人數(shù)。

課程集合：L={l1，l2，…，lu}；

教室集合：R={r1，r2，…，rv}；Cap（rk）表示教室rk的容量。

教室類型：S={s1，s2，…，sz}；Type（rk）表示教室rk的類型，Type（rk）∈S

時間集合：P={p1，p2，…，pd}；

教師時間偏好集合：A={A[t1][ p1]，…A[t1][pd]，…A[tm][pd]}

授課任務(wù)集合：TASK={task |task =（c，t，l，s，w），c∈C，t∈T，l∈L，r∈R }表示教師h在班級c講授課程l，需要s類型的教室，每周共講授w次課。

最終的課程表CT={ct |ct =（c，t，l，p，r），c∈C，t∈T，l∈L，p∈P，r∈R }表示在p時間段內(nèi)，教師t在r教室為c班級講授課程l。相較于TASK，最終課表CT將需要教室類型s、上課次數(shù)w具體為上課教室和每次上課具體時間。

排課首先要滿足基礎(chǔ)條件：

（1）一個班級只能在同一時間內(nèi)上一門課。

設(shè)i≠j，

當(dāng)cti.c＝ctj.c

必有 cti.p≠ctj.p

（2）一個老師只能在同一時間內(nèi)教一門課。

設(shè)i≠j，

當(dāng)cti.t＝ctj.t

必有 cti.p≠ctj.p

（3）兩門課不能在同一時間內(nèi)安排在同一個教室。

設(shè)i≠j，

當(dāng)cti.c＝ctj.c and cti.r＝ctj.r

必有 cti.p≠ctj.p

（4）教室容量應(yīng)不小于學(xué)生容量。

Cap（cti.r）≥Num（cti.c）

為了保證排課的順利進(jìn)行，將排課步驟分為三步，第一步對課程表進(jìn)行預(yù)處理，設(shè)置任務(wù)組Group={g | g=（c，t，l，s），c∈C，t∈T，l∈L，s∈S}，可采取貪心算法或網(wǎng)絡(luò)流算法，將任務(wù)組安排到不同時間段，保證同一個任務(wù)組單位能在一個時間段內(nèi)完成。對任務(wù)組預(yù)處理后得到Glist={Group}。

第二步對課程表進(jìn)行禁忌搜索，優(yōu)化課程安排的時間，這是本文詳細(xì)探討的部分。第三部對為課程安排相應(yīng)的教室。

3 禁忌算法

3.1 定義域

時間集合為時間集合：={1，2，…，p}。定義域?yàn)橐粋€長度為的整數(shù)序列，表示：=（1，2， …，o）。定義域中各分量跟時間元素是一一對應(yīng)的。

即若o所對應(yīng)的時間段內(nèi)有任務(wù)安排，則顯示任務(wù)安排的編號，若安排則顯示0。

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

不同的上課時間具有不同的賦值，如可按表1為各上課時間段賦值，使用（）表示時間段所具有的權(quán)值（∈）。

表1 各上課時間段賦值

各課程的重要程度也不同，為各課程用（）表示課程具有的權(quán)值（∈）。目標(biāo)函數(shù)值可以如下定義：

該式中，表示訪問任務(wù)元g中的課程信息。

3.3 適配值函數(shù)

排課問題的目的是盡最大可能減少課程沖突，協(xié)調(diào)老師、學(xué)生的上課權(quán)益。本文禁忌搜索算法的目標(biāo)是是適配值函數(shù)（）=（）-1（）-2（）-3（）的值最大。（）為目標(biāo)函數(shù)，即保證課程安排時間加權(quán)后最合理。1（）、2（）、3（）為三個沖突函數(shù)。、、為三個較大整數(shù)，根據(jù)解除沖突的重要性賦予不同權(quán)值。

3.4 沖突函數(shù)

1（）表示為累計(jì)老師時間沖突。表示教師時間沖突權(quán)重。首先定義老師偏好沖突1（，）為：

通過遍歷整個定義域內(nèi)，查找每個非零定義域元素對應(yīng)的任務(wù)組中的老師是否在定義域?qū)?yīng)的時間段內(nèi)有空，若有空側(cè)無沖突，若沒時間則增加沖突1。

基于1（，），定義1（）為老師時間沖突之和：

2（）表示為老師課程分散程度，表示教師課表集中度權(quán)重。首先定義連續(xù)函數(shù)2，

即連續(xù)授課則無沖突，非連續(xù)授課沖突記為1。

定義教師課表分散程度2（），表示老師不連續(xù)授課的總次數(shù)。

3（）表示為學(xué)時安排合理沖突，表示學(xué)時安排合理權(quán)重。首先定義連續(xù)函數(shù)3，

即當(dāng)一門課時兩次時間在同一天內(nèi)，則記為有沖突，否則記為無沖突

3.5 鄰域結(jié)構(gòu)及候選解

解是一個整數(shù)序列，交換中兩個元素的位置就能得到其鄰域解。使用互換操作定義來定義域映射函數(shù)（）如下：

：=（1，2，…，o，o，…o，…o）→{（1，2，…，o，…，o，o）}（1≤≤，≠）

若鄰域解的適配值大于當(dāng)前解的適配值，則設(shè)該解為候選解。

3.6 禁忌表及禁忌對象

禁忌表長度動態(tài)變化，前期規(guī)模小，得到更多分散解，后期規(guī)模大，最優(yōu)解趨于集中。禁忌對象為二元組，由兩個交換位置的整數(shù)組成，簡化方便。

3.7 特赦準(zhǔn)則及終止準(zhǔn)則

如某鄰域解的適配值大于當(dāng)前最優(yōu)值，則設(shè)該鄰域解為最優(yōu)解，忽略其是否被禁忌的狀態(tài)，同時更新禁忌表。終止準(zhǔn)則：迭代步數(shù)達(dá)到某個固定次數(shù)后終止。

3.8 禁忌搜索算法步驟

（1）給出算法參數(shù)，隨機(jī)產(chǎn)生初始可行解x∈X（此解為預(yù)處理后的可行解），初始化各參數(shù)。禁忌表設(shè)為空，迭代步數(shù)gen為0，設(shè)定最大迭代步數(shù)max-gen，x*=x，ads（x*）=ads（x）。

（2）如果gen> max-gen，終止算法，輸出最優(yōu)結(jié)果; 否則gen=gen+1。

（3）根據(jù)選擇策略從當(dāng)前移動集合FN（x）中選取非禁忌移動產(chǎn)生新解x’。

（4）若ads（x’） >ads（x*），則用x’代替最優(yōu)解x*，ads（x’）>ads，更新禁忌表，跳轉(zhuǎn)（2）。

（5）如果ads（x’）> ads（x*），更新最優(yōu)解x=x*，ads（x*）=ads（x’）更新禁忌表T，跳轉(zhuǎn)（2）。

4 禁忌搜索算法優(yōu)勢

通過禁忌搜索算法可以合理分配各任務(wù)組時間。此后進(jìn)行第三步，分配各任務(wù)組所需要的教室。本文中假設(shè)教室足夠充足，因此不存在無解現(xiàn)象?？赏ㄟ^貪心算法求得教室分配。

本文重點(diǎn)講述禁忌搜索在高職院校排課問題中的應(yīng)用。禁忌搜索算法全局搜索思想有效優(yōu)化課表。設(shè)置適配值，搜索結(jié)果一方面盡可能符合目標(biāo)函數(shù)的要求，即滿足重要課程安排時間合理性，另一方面又要避免沖突，保證教師時間安排合理、課程安排集中，學(xué)生上課效率高等。兼顧了排課問題的基礎(chǔ)條件和優(yōu)化條件，對排課完善有一定作用。

[1]李靜，趙建平.高校排課系統(tǒng)優(yōu)化模型的可行性研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識.2018（20）.

[2]張媛，祁蘭.基于禁忌搜索的排課系統(tǒng)的設(shè)計(jì)[J].電子設(shè)計(jì)工程. 2016（22）.

[3]劉長彬.基于遺傳算法和禁忌搜索算法的排課系統(tǒng)研究[J].軟件導(dǎo)刊. 2014（10）.

[4]夏季.排課問題的數(shù)學(xué)模型設(shè)計(jì)[J].信息與電腦（理論版）. 2014（02）.

[5]徐亮.高校智能排課系統(tǒng)的研究[J].電子設(shè)計(jì)工程. 2013（07）.

[6]王慧君，方明.淺談高校課程表的編排[J].中國科技信息. 2010（11）.

[7]丁振國，趙宏維.禁忌搜索求解排課問題的應(yīng)用研究[J].微電子學(xué)與計(jì)算機(jī). 2008（04）.

[8]王偉，余利華.基于貪心法和禁忌搜索的實(shí)用高校排課系統(tǒng)[J].計(jì)算機(jī)應(yīng)用.2007（11）.