摘 要： 排課是學(xué)校教學(xué)管理中非常重要的工作。排課問(wèn)題是一個(gè)有約束、多目標(biāo)的優(yōu)化組合問(wèn)題，并且已經(jīng)被證明是一個(gè)NP完全問(wèn)題。高職院校與一般中小學(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é)合的方法有效解決了排課問(wèn)題，不但排課效率高，而且容易得到優(yōu)質(zhì)課表。

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

0 引言

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

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

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

　　本學(xué)院有約兩萬(wàn)名學(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)遵循的基本原則有：

　　（1）硬約束條件，即必須滿足的條件：

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

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

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

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

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

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

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

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

　　①同一門(mén)課程在一周之內(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ì)

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

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

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

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

　　（2）二維矩陣的縱坐標(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)。

　　（3）課程信息代碼

　　課程信息代碼設(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ù)。每門(mén)課程根據(jù)學(xué)時(shí)確定每周需上課的次數(shù)，一般為1~3。

　　2.2 初始群體

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

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

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

　　（1）初排

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

　　①在已排好理論課的課表基礎(chǔ)上，將全院選修課的時(shí)間片標(biāo)注出來(lái)，該時(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ù)也不超過(guò)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)過(guò)預(yù)排后，所安排的實(shí)訓(xùn)室已能滿足課程的需要，而且配置高的實(shí)訓(xùn)室利用率比較高，實(shí)現(xiàn)了資源的最大化利用。但現(xiàn)階段的課表有可能會(huì)出現(xiàn)教師上課時(shí)間沖突、學(xué)生上課時(shí)間沖突、教師同一個(gè)半天被分配到不同校區(qū)等問(wèn)題，所以要進(jìn)行總體調(diào)整。具體操作流程如下：

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

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

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

　　④在同一時(shí)間上檢查是否有同一個(gè)班級(jí)，如果有，則調(diào)整到該班級(jí)沒(méi)有上課的其他時(shí)間片，實(shí)訓(xùn)室不變。

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

　　2.2.2 初始群體規(guī)模

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

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

　　初始群體均為無(wú)沖突課表，滿足了課表的硬約束條件，但對(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表示該位置無(wú)排課，1表示該位置有排課。

　　（2）課程間隔效果值計(jì)算

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

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

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

　　（3）適應(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è)體使用“輪盤(pán)選種”的方法選擇進(jìn)入下一代基因。

　　2.5 交叉

　　因?yàn)樽鳛槊總€(gè)基因的課表都是無(wú)沖突課程，故在進(jìn)行交叉和變異時(shí)要設(shè)計(jì)好交叉的方法，不改變課表無(wú)沖突的狀態(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)程序的編寫(xiě)工具。程序中通過(guò)導(dǎo)入外部文件的方式，可隨時(shí)設(shè)置教室、班級(jí)、教師、課程、學(xué)時(shí)安排等約束條件，通過(guò)遺傳算法的多次迭代得出具有較高適應(yīng)度的課表。程序運(yùn)行結(jié)果表明，算法的前期收斂速度很快，后期變慢，因?yàn)槌跏蓟蛞褳闊o(wú)沖突課表，要得到效率值較優(yōu)的課表只需較少的迭代次數(shù)與時(shí)間即可。

5 結(jié)論

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

參考文獻(xiàn)

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

　　[2] 崔玉連,楊新峰.改進(jìn)遺傳算法在排課問(wè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.