摘 要： 排課是學(xué)校教學(xué)管理中非常重要的工作。排課問題是一個有約束、多目標(biāo)的優(yōu)化組合問題，并且已經(jīng)被證明是一個NP完全問題。高職院校與一般中小學(xué)校相比，課程的編排需考慮的因素更多，極為復(fù)雜。以廣東農(nóng)工商職業(yè)技術(shù)學(xué)院計算機(jī)系實(shí)訓(xùn)室排課系統(tǒng)的算法作為研究對象，根據(jù)我院的一校多區(qū)等實(shí)際情況和計算機(jī)實(shí)訓(xùn)課程的特點(diǎn)進(jìn)行排課算法的研究，采用多重優(yōu)先法則與遺傳算法相結(jié)合的方法有效解決了排課問題，不但排課效率高，而且容易得到優(yōu)質(zhì)課表。

　　關(guān)鍵詞： 排課；實(shí)訓(xùn)室；遺傳算法；多重優(yōu)先

0 引言

　　排課問題就是在給定教師資源、教室資源和開課計劃的前提下，如何合理地安排課表問題。其實(shí)質(zhì)是含約束條件的目標(biāo)函數(shù)優(yōu)化問題，是運(yùn)籌學(xué)中的時間表問題(Timetable Problems，TTPs)[1]。1975 年， Even S 證明了高校排課問題在本質(zhì)上屬于NP完全問題[2]。遺傳算法 GA作為隨機(jī)優(yōu)化與搜索方法，通過對可行解進(jìn)行選擇、交叉、變異等遺傳算法的作用使種群不斷進(jìn)化，最后得到全局最優(yōu)解或近似最優(yōu)解，成為求解排課問題的主要方法[3]。

　　近年來，高職院校不斷進(jìn)行擴(kuò)招，專業(yè)、學(xué)生、教師不斷增加，使得教室、實(shí)訓(xùn)室等資源變得緊缺，排課問題變得越來越嚴(yán)峻。由于各個學(xué)校的具體情況各不相同，通用的排課軟件已不能很好地適應(yīng)每個學(xué)校。本文對我院一校多區(qū)等實(shí)際情況和計算機(jī)實(shí)訓(xùn)室課程的特點(diǎn)進(jìn)行了深入分析，在使用遺傳算法的基礎(chǔ)上結(jié)合多重優(yōu)先的方法先得到初始種群，然后通過遺傳算法的選擇、交叉、變異、迭代進(jìn)行尋優(yōu)，最終得到優(yōu)質(zhì)課表[4]。相對于其他利用遺傳算法解決排課問題的算法，該算法更具針對性，主要體現(xiàn)在對課程的多重優(yōu)先的分層編排和課程編碼設(shè)計上。

1 計算機(jī)系實(shí)訓(xùn)室排課問題分析

　　本學(xué)院有約兩萬名學(xué)生，計算機(jī)系有學(xué)生兩千多名，分布在兩個校區(qū)，一、二年級的學(xué)生在北校區(qū)、三年級的學(xué)生在西校區(qū)。教師同時擔(dān)任兩個校區(qū)的課程。學(xué)院教務(wù)處負(fù)責(zé)安排理論+實(shí)踐課程的理論學(xué)時（在多媒體教室上），計算機(jī)系負(fù)責(zé)安排理實(shí)一體化課程和理論+實(shí)踐課程的實(shí)訓(xùn)學(xué)時（在本系實(shí)訓(xùn)室上），計算機(jī)實(shí)訓(xùn)室排課是在教務(wù)處已排好的理論課課表的基礎(chǔ)上進(jìn)行。本系有30多間實(shí)訓(xùn)室，除少數(shù)專業(yè)實(shí)訓(xùn)室（如攝影室、手繪室、網(wǎng)絡(luò)實(shí)訓(xùn)室等），大部分均為普通機(jī)房，可承擔(dān)一般課程的實(shí)訓(xùn)教學(xué)，普通機(jī)房的配置分為高、中、低三級，根據(jù)課程的要求最大化地利用好實(shí)訓(xùn)資源，提高教學(xué)效果。

　　根據(jù)本學(xué)院的實(shí)際情況，實(shí)訓(xùn)室排課除了要滿足一般課表的要求，還有一些特別要求，應(yīng)遵循的基本原則有：

　?。?）硬約束條件，即必須滿足的條件：

　?、俳處煵荒軟_突，同一教師在同一時間不能教授兩門課程（課程包括實(shí)訓(xùn)課和理論課）；

　?、趯?shí)訓(xùn)室不能沖突，同一實(shí)訓(xùn)室在同一時間不能安排兩門課程；

　?、郯嗉壊荒軟_突，同一班級在同一時間不能安排兩門課程（課程包括實(shí)訓(xùn)課和理論課）；

　　④教師不能在同一個半天在不同校區(qū)上課；

　　⑤課程必須安排在符合基本實(shí)訓(xùn)要求的實(shí)訓(xùn)室上，專業(yè)性很強(qiáng)的課程要專門安排專業(yè)性實(shí)訓(xùn)室，一般課程按內(nèi)容要求不能低于最低配置的實(shí)訓(xùn)室；

　?、迣?shí)訓(xùn)室容量必須滿足上課學(xué)生人數(shù)，現(xiàn)有實(shí)訓(xùn)室的容量一般都大于班級人數(shù)的編排；

　　⑦全院公共選修課時間段不安排課程。

　　（2）軟約束條件，不一定要滿足，但滿足能得到較優(yōu)解：

　　①同一門課程在一周之內(nèi)應(yīng)間隔排列。如某課程周學(xué)時為4學(xué)時，以2學(xué)時為一個教學(xué)單位，需安排兩次，兩次的安排時間有合理間隔；

　?、谕话嗉壍恼n程應(yīng)在一周內(nèi)分散安排；

　?、壅n程盡量安排在上課效果好的時間段，晚上和周五的下午盡量不排課；

　?、軐τ谏险n時間有特殊要求的教師和課程盡量滿足其時間要求。

　　在以上列出的軟硬約束中，硬約束必須要滿足，而軟約束是在滿足硬約束的前提下盡量滿足。

2 排課遺傳算法設(shè)計

　　2.1 編碼設(shè)計

　　使用二維矩陣來表示一個總的課表。橫坐標(biāo)表示時間，縱坐標(biāo)表示實(shí)訓(xùn)室，課程信息包括課程名稱、授課教師、班級、實(shí)訓(xùn)室要求等信息。排課就可以簡化成將課程信息放入這個二維矩陣。采用這種操作，不可能出現(xiàn)同一時間的教室沖突，只要保證在同一時間中教師和班級不沖突，同一半天中教師沒有被安排在不同校區(qū)就可以得到一份可行課表。具體編碼設(shè)計如下：

　　（1）二維矩陣的橫坐標(biāo)表示時間片

　　高職院校的課程一般兩節(jié)課連上，兩節(jié)課為一次課，上午兩次課，下午兩次課，因課程較多，有時晚上也需排課。每次課作為一個時間片來安排課程，每天6個時間片，每周5天，則可分為30個時間片。

　　每個時間片表示為Tij, i∈{1,2,3,4,5}，j∈{1,2,3,4,5,6}，i表示星期幾，j表示一天內(nèi)的哪一個時間片。具體如表1所示。

　?。?）二維矩陣的縱坐標(biāo)表示實(shí)訓(xùn)室

　　實(shí)訓(xùn)室代碼設(shè)置為4位，R=（R1 R2 R3 R4），其中：R1表示實(shí)訓(xùn)室所在校區(qū)：1表示北校區(qū)，2表示本部；R2表示實(shí)訓(xùn)室的配置類型：1表示高配置，2表示中配置，3表示低配置，4表示攝影室，5表示手繪室，6表示網(wǎng)絡(luò)實(shí)訓(xùn)室；R3表示實(shí)訓(xùn)室可容納的學(xué)生數(shù)；R4表示各類型實(shí)訓(xùn)室的編號。

　?。?）課程信息代碼

　　課程信息代碼設(shè)置為10位，C=（C1 C2 C3 C4 C5 C6 C7 C8 C9 C10），其中：C1表示實(shí)訓(xùn)室所在校區(qū)：1表示北校區(qū)；2表示本部；C2表示對實(shí)訓(xùn)室的配置類型要求，具體代碼表示與R2相同；C3表示班級人數(shù)；C4、C5表示班級代碼；C6、C7表示教師代碼；C8、C9表示課程名稱；C10表示課程每周需上的次數(shù)。每門課程根據(jù)學(xué)時確定每周需上課的次數(shù)，一般為1~3。

　　2.2 初始群體

　　2.2.1 初始群體的產(chǎn)生

　　排課需考慮的約束很多，如果全部直接使用隨機(jī)生成的方式很難得到有效的無沖突課表，故本文根據(jù)實(shí)訓(xùn)室排課的特點(diǎn)，有針對性地設(shè)計了多重優(yōu)先和隨機(jī)生成相結(jié)全的方法，生成無沖突課表作為初始基因。

　　初始基因（無沖突課表）的生成分為兩大部分：

　　（1）初排

　　先將課表分為北校區(qū)課表和西校區(qū)課表兩部分，分別進(jìn)行預(yù)排。初排時將課室信息采用多重優(yōu)先和隨機(jī)的方法將其分層安排到相關(guān)的教室，對課室的安排先遵守約束性再隨機(jī)，使得實(shí)訓(xùn)資源的分配達(dá)到最大化。安排的時間片均隨機(jī)。具體如下：

　?、僭谝雅藕美碚撜n的課表基礎(chǔ)上，將全院選修課的時間片標(biāo)注出來，該時間段不排課；

　　②將少量的對實(shí)訓(xùn)室有特別要求的課程排入指定的實(shí)訓(xùn)室，如攝影課排入攝影室，手繪課排入多功能手繪室，時間隨機(jī)；

　　③將少量人數(shù)多的課程安排到能容納該人數(shù)的符合要求的實(shí)訓(xùn)室，時間隨機(jī)。因?yàn)橹挥袠O少的班級人數(shù)比較多，也只有一兩個實(shí)訓(xùn)室的容量比較大，一般實(shí)訓(xùn)室的容量都是60位，一般班級的人數(shù)也不超過60，所以一般實(shí)訓(xùn)室能容納大部分的班級；

　?、軐?shí)訓(xùn)室配置要求為高的課程隨機(jī)排入高配置實(shí)訓(xùn)室，時間隨機(jī)；

　?、輰?shí)訓(xùn)室配置要求為中的課程隨機(jī)排入剩余的高配置實(shí)訓(xùn)室后，再隨機(jī)排入中配置實(shí)訓(xùn)室，時間隨機(jī)；

　?、迣?shí)訓(xùn)室配置要求為低的課程隨機(jī)排入剩余的中配置實(shí)訓(xùn)室后，再隨機(jī)排入低配置實(shí)訓(xùn)室，時間隨機(jī)。

　　在分配時，同一課程優(yōu)先分配到同一實(shí)訓(xùn)室。

　　（2）調(diào)整

　　經(jīng)過預(yù)排后，所安排的實(shí)訓(xùn)室已能滿足課程的需要，而且配置高的實(shí)訓(xùn)室利用率比較高，實(shí)現(xiàn)了資源的最大化利用。但現(xiàn)階段的課表有可能會出現(xiàn)教師上課時間沖突、學(xué)生上課時間沖突、教師同一個半天被分配到不同校區(qū)等問題，所以要進(jìn)行總體調(diào)整。具體操作流程如下：

　　① 將預(yù)排好的北校區(qū)和西校區(qū)課表合并成一個總課表；

　?、谠谕粫r間上檢查是否有同一個老師，如果有，則調(diào)整到該老師沒有上課的其他時間片，實(shí)訓(xùn)室不變；

　?、墼诒毙^(qū)、西校區(qū)同一半天的時間上檢查是否有同一個老師，如果有，則調(diào)整時間片，實(shí)訓(xùn)室不變。

　?、茉谕粫r間上檢查是否有同一個班級，如果有，則調(diào)整到該班級沒有上課的其他時間片，實(shí)訓(xùn)室不變。

　　經(jīng)過調(diào)整，得到初始無沖突課表。課表的樣式如表2所示。一份課表作為一個基因V。

　　2.2.2 初始群體規(guī)模

　　使用同樣的方法生成一定數(shù)量初始基因構(gòu)成遺傳算法的初始群體。初始群體的規(guī)模不宜過大或過小。過大計算量大，收斂慢；過小則不利于得到最優(yōu)解。這里的初始群體規(guī)模設(shè)為30，得。

　　2.3 適應(yīng)度函數(shù)

　　初始群體均為無沖突課表，滿足了課表的硬約束條件，但對軟約束條件的滿足是不一樣的。為了判斷課表的優(yōu)質(zhì)程度，得到最優(yōu)課表，需根據(jù)排課的軟約束條件構(gòu)造相應(yīng)的適應(yīng)度函數(shù)進(jìn)行評價。初排時已充分考慮實(shí)訓(xùn)室優(yōu)質(zhì)資源的高效使用，現(xiàn)評價只需考慮課程安排的時間。

　　（1）上課時間效果值計算

　　課程盡量安排在上課效果好的時間。一般上午上課效果優(yōu)于下午；下午優(yōu)于晚上；周一、周二優(yōu)于周四、周五等。設(shè)定的每天各個時間段的效果值如表3所示。

　　整個課程表中占用上課時間的效果值之和為：

　　式（1）中，D表示課程所在時間段的效果值； i表示時間片；j表示課程實(shí)訓(xùn)室；r表示實(shí)訓(xùn)室總數(shù)；missing image file0表示該位置無排課，1表示該位置有排課。

　?。?）課程間隔效果值計算

　　同一門課程一般一周內(nèi)安排兩次，在一周之內(nèi)應(yīng)間隔排列，間隔效果值如表4所示。

　　整個課表的課程間隔效果值為：

　　式（2）中，E表示同一課程一周內(nèi)的間隔時間的效果值，m為課程的門數(shù)。

　?。?）適應(yīng)度函數(shù)

　　歸總上面約束函數(shù)，得出總的適應(yīng)度函數(shù)為：

　　其中，p、q為權(quán)值，p=30，q=50。

　　2.4 選擇算子

　　為防止已經(jīng)搜尋到的最優(yōu)解丟失，讓上一次群體中適應(yīng)度最大的20％的課表直接進(jìn)入下一代群體中，另外80％的個體使用“輪盤選種”的方法選擇進(jìn)入下一代基因。

　　2.5 交叉

　　因?yàn)樽鳛槊總€基因的課表都是無沖突課程，故在進(jìn)行交叉和變異時要設(shè)計好交叉的方法，不改變課表無沖突的狀態(tài)。這里以半天的2個時間片的課程安排作為交換單元，因?yàn)槿绻砸粋€時間片作為交換因子，有可能在半天里將同一位教師分配到不同校區(qū)。教務(wù)處已排的理論課程、已定的選修課時間、周五晚上的時間單元對應(yīng)的內(nèi)容不作交叉，保留原位。

　　2.6 變異

　　在同一時間片里將課程調(diào)整到達(dá)到最基本配置要求的實(shí)訓(xùn)室的空時間片中。因變異的區(qū)域限定在同一時間片里，故可以保證課程表的沖突狀態(tài)。

　　2.7 判斷終止條件

　　根據(jù)需要進(jìn)行迭代次數(shù)的設(shè)置，可隨時停止運(yùn)算。

　　2.8 得出適應(yīng)度最高的課程表

　　計算出適應(yīng)度最高的課表作為最終優(yōu)質(zhì)課表。

3 各類型課程表的生成

　　由得到的最終優(yōu)質(zhì)課表生成各類型的課程表，包括教室安排表、教師安排表、班級安排表。

4 實(shí)驗(yàn)

　　使用Visual Studio 2010的C#作為實(shí)驗(yàn)程序的編寫工具。程序中通過導(dǎo)入外部文件的方式，可隨時設(shè)置教室、班級、教師、課程、學(xué)時安排等約束條件，通過遺傳算法的多次迭代得出具有較高適應(yīng)度的課表。程序運(yùn)行結(jié)果表明，算法的前期收斂速度很快，后期變慢，因?yàn)槌跏蓟蛞褳闊o沖突課表，要得到效率值較優(yōu)的課表只需較少的迭代次數(shù)與時間即可。

5 結(jié)論

　　本文針對我院一校多區(qū)等實(shí)際情況和計算機(jī)實(shí)訓(xùn)課程的特點(diǎn)，基于遺傳算法，使用多重優(yōu)先的法則先得到無沖突課表作為初始基因，相對于其他使用遺傳算法解決排課問題的方法更高效，設(shè)計了效果適應(yīng)度函數(shù)、選擇、交叉和變異的方法，算法快速收斂，能有效得到優(yōu)質(zhì)課表。

參考文獻(xiàn)

　　[1] 廖宇力.基于遺傳算法的排課問題適應(yīng)度函數(shù)設(shè)計[J].現(xiàn)代計算機(jī)（專業(yè)版），2010(4):53-57.

　　[2] 崔玉連,楊新峰.改進(jìn)遺傳算法在排課問題中的應(yīng)用研究[J].微型電腦應(yīng)用,2013，29（10）:48-51.

　　[3] 鐘耀廣,劉群鋒.基于遺傳算法的高校排課數(shù)學(xué)模型[J].東莞理工學(xué)院學(xué)報,2012，19（5）:4-8.

　　[4] 于干,張軍. 遺傳算法在自動排課中的應(yīng)用研究[J].科技向?qū)?2011(30):10-11.