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

◆范 萍

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

◆范 萍

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

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

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

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

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

1 排課問題的要求

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

1.1 基礎(chǔ)條件

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

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

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

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

1.2 優(yōu)化條件

同一門課程兩次授課時(shí)間在一天以上：

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

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

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

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

（2）一天共有5個(gè)大課時(shí)，每門課每次上課僅占一個(gè)課時(shí)。

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

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

2 排課問題的建模

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

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

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

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

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

時(shí)間集合：P={p1，p2，…，pd}；

教師時(shí)間偏好集合：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在班級(jí)c講授課程l，需要s類型的教室，每周共講授w次課。

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

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

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

設(shè)i≠j，

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

必有 cti.p≠ctj.p

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

設(shè)i≠j，

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

必有 cti.p≠ctj.p

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

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

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

3 禁忌算法

3.1 定義域

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

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

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

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

表1 各上課時(shí)間段賦值

各課程的重要程度也不同，為各課程用（）表示課程具有的權(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ù)，即保證課程安排時(shí)間加權(quán)后最合理。1（）、2（）、3（）為三個(gè)沖突函數(shù)。、、為三個(gè)較大整數(shù)，根據(jù)解除沖突的重要性賦予不同權(quán)值。

3.4 沖突函數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

3.6 禁忌表及禁忌對(duì)象

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

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

如某鄰域解的適配值大于當(dāng)前最優(yōu)值，則設(shè)該鄰域解為最優(yōu)解，忽略其是否被禁忌的狀態(tài)，同時(shí)更新禁忌表。終止準(zhǔn)則：迭代步數(shù)達(dá)到某個(gè)固定次數(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)前移動(dòng)集合FN（x）中選取非禁忌移動(dòng)產(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)勢(shì)

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

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

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

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

[3]劉長(zhǎng)彬.基于遺傳算法和禁忌搜索算法的排課系統(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].中國(guó)科技信息. 2010（11）.

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

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