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

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

0 引言

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

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

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

　　本學(xué)院有約兩萬名學(xué)生,，計(jì)算機(jī)系有學(xué)生兩千多名，分布在兩個(gè)校區(qū),，一,、二年級(jí)的學(xué)生在北校區(qū)、三年級(jí)的學(xué)生在西校區(qū),。教師同時(shí)擔(dān)任兩個(gè)校區(qū)的課程,。學(xué)院教務(wù)處負(fù)責(zé)安排理論+實(shí)踐課程的理論學(xué)時(shí)（在多媒體教室上），計(jì)算機(jī)系負(fù)責(zé)安排理實(shí)一體化課程和理論+實(shí)踐課程的實(shí)訓(xùn)學(xué)時(shí)（在本系實(shí)訓(xùn)室上）,，計(jì)算機(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í),，根據(jù)課程的要求最大化地利用好實(shí)訓(xùn)資源,，提高教學(xué)效果。

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

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

　　①教師不能沖突,，同一教師在同一時(shí)間不能教授兩門課程（課程包括實(shí)訓(xùn)課和理論課）,；

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

　　③班級(jí)不能沖突,，同一班級(jí)在同一時(shí)間不能安排兩門課程（課程包括實(shí)訓(xùn)課和理論課）,；

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

　?、菡n程必須安排在符合基本實(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)室的容量一般都大于班級(jí)人數(shù)的編排,；

　　⑦全院公共選修課時(shí)間段不安排課程,。

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

　?、偻婚T課程在一周之內(nèi)應(yīng)間隔排列。如某課程周學(xué)時(shí)為4學(xué)時(shí),，以2學(xué)時(shí)為一個(gè)教學(xué)單位,，需安排兩次，兩次的安排時(shí)間有合理間隔,；

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

　　③課程盡量安排在上課效果好的時(shí)間段,，晚上和周五的下午盡量不排課；

　?、軐?duì)于上課時(shí)間有特殊要求的教師和課程盡量滿足其時(shí)間要求,。

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

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

　　2.1 編碼設(shè)計(jì)

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

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

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

　　每個(gè)時(shí)間片表示為Tij, i∈{1,2,3,4,5},，j∈{1,2,3,4,5,6}，i表示星期幾,，j表示一天內(nèi)的哪一個(gè)時(shí)間片,。具體如表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)室的編號(hào)。

　?。?）課程信息代碼

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

　　2.2 初始群體

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

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

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

　　（1）初排

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

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

　?、趯⑸倭康膶?duì)實(shí)訓(xùn)室有特別要求的課程排入指定的實(shí)訓(xùn)室，如攝影課排入攝影室,，手繪課排入多功能手繪室,，時(shí)間隨機(jī)；

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

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

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

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

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

　　（2）調(diào)整

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

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

　　②在同一時(shí)間上檢查是否有同一個(gè)老師，如果有,，則調(diào)整到該老師沒有上課的其他時(shí)間片,，實(shí)訓(xùn)室不變；

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

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

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

　　2.2.2 初始群體規(guī)模

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

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

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

　　（1）上課時(shí)間效果值計(jì)算

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

　　整個(gè)課程表中占用上課時(shí)間的效果值之和為：

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

　?。?）課程間隔效果值計(jì)算

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

　　整個(gè)課表的課程間隔效果值為：

　　式（2）中，E表示同一課程一周內(nèi)的間隔時(shí)間的效果值,，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％的個(gè)體使用“輪盤選種”的方法選擇進(jìn)入下一代基因,。

　　2.5 交叉

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

　　2.6 變異

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

　　2.7 判斷終止條件

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

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

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

3 各類型課程表的生成

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

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

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

5 結(jié)論

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

參考文獻(xiàn)

　　[1] 廖宇力.基于遺傳算法的排課問題適應(yīng)度函數(shù)設(shè)計(jì)[J].現(xiàn)代計(jì)算機(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é)報(bào),2012，19（5）:4-8.

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