張赫男，張紹文

北京林業(yè)大學(xué) 經(jīng)濟(jì)管理學(xué)院，北京 100083

1 引言

排課問題是一個(gè)在教育機(jī)構(gòu)中廣泛存在的問題，能否有效地解決排課問題將直接關(guān)系到教學(xué)質(zhì)量的好壞。近年來，隨著高校的擴(kuò)招，學(xué)生的數(shù)量日益增多，并且隨著社會的發(fā)展，專業(yè)和課程的種類也都在與日俱增。在這樣的環(huán)境下，教師和教室等資源顯得愈發(fā)緊張。因此，一個(gè)有效的課程安排已經(jīng)成為教師、學(xué)生以及學(xué)校管理人員的共同訴求。

排課問題是一種多約束和多目標(biāo)的組合優(yōu)化問題，它已被證明是一個(gè)NP難問題[1-2]。國內(nèi)外的學(xué)者已經(jīng)提出了一些解決排課問題的方法。早期的解決方法主要有直接啟發(fā)式方法[3]，圖著色法[4-5]，整數(shù)線性規(guī)劃法[6-8]，網(wǎng)絡(luò)流法[9-10]，這些方法能夠解決問題的規(guī)模都很有限。隨著計(jì)算機(jī)技術(shù)的發(fā)展，尤其是20世紀(jì)90年代以來，越來越多的智能算法被應(yīng)用于解決排課問題，如遺傳算法[11-13]，模擬退火算法[14]，禁忌搜索算法[15]，以及多種智能算法相結(jié)合的混合算法[16-17]。這些算法都能在一定程度上解決排課問題，但也存在著一些不足：（1）考慮的約束條件不夠全面，如對合班的情況考慮比較少[18-19]；（2）目標(biāo)函數(shù)僅僅取決于約束條件被違反的次數(shù)，并沒有考慮到不同課程的重要程度以及不同時(shí)間段具有不同的教學(xué)效果等[13，18]。本文針對這些不足之處提出了改進(jìn)的方法。

遺傳算法具有自組織、自適應(yīng)和自學(xué)習(xí)性，不需要其他的輔助知識，只需要影響搜索方向的目標(biāo)函數(shù)和相適應(yīng)的適應(yīng)度函數(shù)[20]；遺傳算法進(jìn)行的是全空間的并行搜索，并將搜索重點(diǎn)集中于性能高的部分，從而能夠提高效率，而且不容易陷入局部最優(yōu)[21]。遺傳算法采用的是群體并行搜索，局部搜索能力較差；而模擬退火算法采用的是串行優(yōu)化結(jié)構(gòu)，全局搜索能力較弱。二者的結(jié)合能夠互相增強(qiáng)和補(bǔ)充進(jìn)化的能力[21]。因此，本文將遺傳算法與模擬退火算法相結(jié)合，用以解決高校排課問題。

2 高校排課問題分析及數(shù)學(xué)建模

2.1 問題描述

排課問題是一種資源分配問題，是要將班級，課程，教師，時(shí)間和教室等要素進(jìn)行合理的安排，在滿足各種約束條件的前提下，使目標(biāo)函數(shù)盡量達(dá)到最優(yōu)。不管是學(xué)生，教師，還是管理人員，都傾向于同一門課程在同一學(xué)期內(nèi)固定在同一個(gè)教室，因此本文沒有考慮周次的概念，而是重點(diǎn)研究了課程安排最為密集的一周，若這周的課程可以得到合理的安排，則其他周次的課程安排只須在該周的基礎(chǔ)上做一定的刪減。

2.2 相關(guān)術(shù)語

小班：以專業(yè)名稱、年級和班級編號確定下來的班級，例如“會計(jì)10-1”表示會計(jì)專業(yè)10級1班。

班級：在同一時(shí)間同一地點(diǎn)學(xué)習(xí)同一科目的小班的集合，可以只由一個(gè)小班組成，也可以由多個(gè)小班組成。

科目：一名固定的教師和一個(gè)固定的班級所對應(yīng)的課程。若存在不同的班級或不同的教師對應(yīng)名稱相同的科目，則在原始數(shù)據(jù)預(yù)處理過程中通過修改科目名稱和賦予不同的編號作為區(qū)分。一個(gè)班級可以對應(yīng)多門科目，但一門科目只能對應(yīng)一個(gè)班級。

時(shí)間段：以每一節(jié)課時(shí)長45 min為例，在現(xiàn)實(shí)的教學(xué)中，一般都是2～4節(jié)課連在一起進(jìn)行教學(xué)，如上午1～2節(jié)，上午1～4節(jié)，等等。根據(jù)這個(gè)特點(diǎn)，將每天的教學(xué)時(shí)間劃分為5個(gè)時(shí)間段，上午1～2節(jié)為第1個(gè)時(shí)間段，上午3～4節(jié)為第2個(gè)時(shí)間段，以此類推。若是3節(jié)課連在一起，如下午2～4節(jié)，則等同于下午要占用2個(gè)時(shí)間段，因?yàn)樵谶@種情況下，下午的第1節(jié)已無法再安排其他課程。由于晚上一般最多只會安排一個(gè)科目，因此把晚上的教學(xué)時(shí)間記為每天的第5個(gè)時(shí)間段。

2.3 數(shù)據(jù)結(jié)構(gòu)和變量

本文對變量的命名采用“屬性+類”的方式，變量名中排在后面的單詞首字母要大寫，以便于閱讀。若變量為一個(gè)元素，則首字母小寫；若變量為一個(gè)集合，則首字母大寫。如表示教師i的編號的變量命名為idTeacheri，表示班級j要學(xué)習(xí)課程的編號集合的變量命名為IdSubjectClassj。

原始數(shù)據(jù)包括以下4個(gè)表：

（1）配置表（CONFIG）：每天的時(shí)間段數(shù)nbPeriodDay=5，每周上課的天數(shù)nbDayWeek=5?？梢杂?jì)算出每周的總時(shí)間段數(shù)nbPeriodWeek=nbPeriodDay×nbDayWeek=25， 每周所有時(shí)間段的集合PeriodWeek={1，2，…，nbPeriodWeek}。

（2）教室表（ROOM）：共有nbRoom個(gè)教室，教室i對應(yīng)的編號和容量分別為idRoomi和capacityRoomi。

（3）科目表（SUBJECT）：共有nbSubject門科目，科目i對應(yīng)的編號、學(xué)分和每周的課次分別為idSubjecti，creditSubjecti和nbPeriodSubjecti。

（4）小班表（SMALLCLASS）：共有nbSmallclass個(gè)小班，小班i對應(yīng)的編號和人數(shù)分別為idSmallclassi和sizeSmallclassi。

通過Access與Matlab混合編程，生成建模和求解所需要的其他數(shù)據(jù)，包括以下2個(gè)表：

（1）班級表（CLASS）：共有nbClass個(gè)班級，班級i對應(yīng)的編號、包含的小班的編號集合、總?cè)藬?shù)、科目的編號集合、每周的課次分別為idClassi，IdSmallclassClassi，sizeClassi，IdSubjectClassi和nbPeriodClassi。

（2）教師表（TEACHER）：共有nbTeacher名教師，教師i對應(yīng)的編號和科目的編號集合分別為idTeacheri和IdSubjectTeacheri。

2.4 硬約束條件

硬約束指的是必須被滿足的、符合客觀邏輯的約束[22]。本文考慮了4個(gè)硬約束條件：

（1）同一時(shí)間，同一班級最多只能有一門課程。

（2）同一時(shí)間，同一教師最多只能有一門課程。

（3）同一時(shí)間，同一教室最多只能有一門課程。

（4）教室的容量不小于在該教室上課的班級的總?cè)藬?shù)。

硬約束是否被滿足決定了排課方案是否可行。

2.5 軟約束條件

軟約束指的是在客觀上可以被違反，但會影響到教學(xué)質(zhì)量的約束[22]。本文考慮了4個(gè)軟約束條件：

（1）重要的課程應(yīng)盡量安排在教學(xué)效果更好的時(shí)間段。

（2）對于同一個(gè)班級的同一門課程，若每周的課次較多，則應(yīng)盡量避免安排在同一天。

（3）對于每一個(gè)班級，要在考慮到課程重要程度的前提下盡量把課程均勻安排在每一天，避免出現(xiàn)某天重要性較高的課程過多或某天重要性較低的課程過少的情況。

（4）盡量實(shí)現(xiàn)班級人數(shù)與教室容量的匹配，以提高教室的利用率。

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

目標(biāo)函數(shù)的優(yōu)劣由軟約束的滿足情況決定，軟約束被滿足的情況越好，目標(biāo)函數(shù)越優(yōu)。本文的目標(biāo)函數(shù)是對各個(gè)軟約束條件被滿足情況的綜合評價(jià)。

（1）時(shí)間段安排效果

對于小班i，找出所有跟該小班有關(guān)的科目的學(xué)分以及時(shí)間段的安排，評價(jià)函數(shù)如下：

其中weightPeriodm表示第m個(gè)時(shí)間段的權(quán)重值。將每天的第1、3和5個(gè)時(shí)間段的權(quán)重值設(shè)置為1，每天的第2和4個(gè)時(shí)間段的權(quán)重值設(shè)置為0.5。課程的重要程度直接用學(xué)分的大小來衡量。

（2）同一課程應(yīng)盡量避免安排在同一天

記小班i的課程安排總體效果為f2Smallclassi，初始值為0。對于小班i的科目j，計(jì)算該科目每周一共有多少課次。本文一共有3種情況。

①科目j每周只有1課次。則對該科目有f2Smallclassi=f2Smallclassi+2。

②科目j每周共有2課次。分別計(jì)算出2個(gè)課次對應(yīng)的是一周的哪一天，并轉(zhuǎn)化為對應(yīng)的數(shù)字，如周一為1，周二為2。用較大數(shù)減去較小數(shù)。評價(jià)方法如表1所示。

表1 每周共有2課次的科目的評價(jià)方法

③科目j每周共有3課次。分別計(jì)算出3個(gè)課次對應(yīng)的是一周的哪一天，轉(zhuǎn)化為對應(yīng)的數(shù)字并從小到大排列。對相鄰的兩個(gè)數(shù)，用較大數(shù)減去較小數(shù)，得到兩個(gè)差值。評價(jià)方法如表2所示。

表2 每周共有3課次的科目的評價(jià)方法

（3）同一小班的課程應(yīng)盡量均勻安排在每一天

對于小班i，統(tǒng)計(jì)該班一周內(nèi)每天的課次數(shù)，計(jì)算出標(biāo)準(zhǔn)差，標(biāo)準(zhǔn)差的值越小，安排的效果越好。評價(jià)函數(shù)如下：

若標(biāo)準(zhǔn)差為0，則將f3Smallclassi賦值為3。

（4）教室的利用率

計(jì)算所有已有安排的教室的平均利用率。評價(jià)函數(shù)如下：

則總的評價(jià)函數(shù)為：

這種評價(jià)方式可以進(jìn)一步擴(kuò)大科目數(shù)量更多、科目重要程度更高、每周總課次更多的小班在目標(biāo)函數(shù)中所占的比重，使這些小班在排課過程中具有更高的優(yōu)先級。以該函數(shù)作為本文混合遺傳算法的適應(yīng)度函數(shù)，函數(shù)值越大，解就越優(yōu)。

3 高校排課問題的混合遺傳算法設(shè)計(jì)

3.1 編碼方法

排課問題是要把各個(gè)班級、科目和教師安排在合理的時(shí)間和地點(diǎn)，即時(shí)間段和教室。建立以每周總時(shí)間段數(shù)nbPeriodWeek為行數(shù)，以教室總數(shù)nbRoom為列數(shù)的二維矩陣，矩陣中的每一個(gè)非空位置的元素都包含了三個(gè)變量：班級編號，科目編號和教師編號。沒有元素的位置則表示該時(shí)間段的該教室沒有安排。采用這種編碼方式可以直接滿足第三個(gè)硬約束條件）。編碼方法如圖1所示。

3.2 初始種群的產(chǎn)生

每一個(gè)初始可行解即為初始種群中的一個(gè)個(gè)體。每一個(gè)可行解的產(chǎn)生過程如圖2所示。

圖1 編碼方法

圖2 可行解的產(chǎn)生過程

按照本文產(chǎn)生可行解的方法，若先安排每周課次較多的班級，由于解空間被過早壓縮，容易導(dǎo)致后面的班級無法被安排，即無法產(chǎn)生可行解。因此在進(jìn)行排課之前，先把各個(gè)班級按照每周課次從小到大的順序進(jìn)行排序，這樣就避免了解空間的過早壓縮，能夠很快地產(chǎn)生可行解。

如果在每次產(chǎn)生可行解的過程中班級的順序都固定不變，那么不同的可行解之間難免會具有一定的相似性，這樣就使得遺傳算法容易陷入局部最優(yōu)解，不利于全局的搜索。因此，有必要進(jìn)行一定的亂序處理，使不同的個(gè)體之間具有比較大的差異，這樣才能使遺傳算法能夠在范圍更大的解空間內(nèi)進(jìn)行搜索，以找到全局最優(yōu)解。

本文采取的亂序處理有兩個(gè)步驟。首先，在各個(gè)班級按照每周課次從小到大的順序進(jìn)行排序后，把每周課次相同的班級分為一組，在組內(nèi)進(jìn)行隨機(jī)的重新排序。如圖3和圖4所示。

圖3 亂序處理前的班級編號

圖4 亂序處理后的班級編號

然后，對于每個(gè)班級的所有科目，在排課過程中也進(jìn)行隨機(jī)的重新排序，如圖5所示。

圖5 科目的亂序處理

3.3 選擇算子

本文的選擇算子引入了保留最優(yōu)個(gè)體策略，即適應(yīng)度最高的個(gè)體直接進(jìn)入下一代，其余進(jìn)入下一代的個(gè)體通過賭輪盤法選出。對種群中的每個(gè)個(gè)體進(jìn)行評價(jià)，適應(yīng)度越高的個(gè)體越有可能進(jìn)入下一代種群。把個(gè)體i的適應(yīng)度記為fi，則該個(gè)體進(jìn)入下一代種群的概率為：

其中nbIndividual為一代種群中個(gè)體的數(shù)量。

3.4 交叉算子

每個(gè)可行解都是在滿足了許多約束條件的情況下產(chǎn)生的，若交叉操作的規(guī)模較大，則產(chǎn)生的子代很容易是一個(gè)非可行解，因此本文采用了兩點(diǎn)交叉操作。此外，為了保證交叉操作對解的改進(jìn)作用，本文還引入了競爭機(jī)制。具體操作過程如下。

（1）對于兩個(gè)將要進(jìn)行交叉操作的個(gè)體父代1（個(gè)體i）和父代2，找出它們對應(yīng)的矩陣中都有安排、且坐標(biāo)相同、且對應(yīng)的科目編號不同的位置，把這些位置作為交叉操作的候選位置。

（2）從候選位置中隨機(jī)選出一個(gè)位置，記父代1和父代2在該位置對應(yīng)的元素分別為元素1和元素2，交換該位置的元素1和元素2。則父代1中了多了一個(gè)元素2，少了一個(gè)元素1；父代2中多了一個(gè)元素1，少了一個(gè)元素2。從父代1中找出其他位置的元素2，放入集合1；從父代2中找出其他位置的元素1，放入集合2。從集合1中任選一個(gè)元素2，從集合2中任選一個(gè)元素1，將它們在兩個(gè)子代個(gè)體中的位置進(jìn)行交換。交叉和修正的過程如圖6所示。

圖6 交叉操作過程

由于集合1和集合2的規(guī)模都很小，為了保證交叉操作的質(zhì)量，這里采用局部遍歷的方式將集合1中的元素2和集合2中的元素1按照它們在各自集合中的次序逐個(gè)進(jìn)行交換，直到某一次交叉操作產(chǎn)生的兩個(gè)子代個(gè)體都是可行解，則把它們與兩個(gè)父代個(gè)體都存放在集合GenerationTemp中，停止遍歷，交叉過程結(jié)束。

（3）引入競爭機(jī)制，對集合GenerationTemp中的2個(gè)父代個(gè)體和2個(gè)子代個(gè)體逐一進(jìn)行評價(jià)，從中挑選出表現(xiàn)最好的一個(gè)，作為本次交叉操作最終得到的最優(yōu)個(gè)體，進(jìn)入下一代種群。

此外，為了控制運(yùn)算的時(shí)間，設(shè)置了進(jìn)行交叉操作的嘗試次數(shù)限制。交叉操作的流程如圖7所示。

圖7 交叉操作流程圖

3.5 變異算子

對于要進(jìn)行變異的父代個(gè)體，在其矩陣中隨機(jī)選出兩行，交換這兩行的元素，產(chǎn)生一個(gè)新的個(gè)體。由本文的編碼方式可知，經(jīng)過這種變異操作所產(chǎn)生的子代也是可行解。變異的過程如圖8所示。

圖8 變異操作過程

圖9 模擬退火過程

3.6 種群的進(jìn)化

種群進(jìn)化的流程如圖10所示。

3.7 檢查機(jī)制

為了驗(yàn)證算法的可行性，本文引入了4個(gè)檢查機(jī)制：

（1）每個(gè)時(shí)間段是否有同一個(gè)班級出現(xiàn)在不同的教室。

（2）每個(gè)時(shí)間段是否有同一名教師出現(xiàn)在不同的教室。

圖10 種群進(jìn)化的流程圖

（3）每個(gè)教室的容量是否不小于在此上課的班級的總?cè)藬?shù)。

（4）一個(gè)解中所有元素的個(gè)數(shù)是否等于所有班級的總課次數(shù)。

檢查結(jié)果顯示，種群中的每一個(gè)個(gè)體都滿足了所有的硬約束條件，并且沒有任何班級、教師或科目存在安排遺漏的情況。

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

4.1 實(shí)例數(shù)據(jù)

本文的實(shí)驗(yàn)數(shù)據(jù)來自于XX大學(xué)XX學(xué)院2013—2014學(xué)年秋季課程安排，共包括79個(gè)班級（其中包括93個(gè)不同的小班），145門科目，85名教師，18間教室。

4.2 參數(shù)設(shè)置

初始種群規(guī)模nbIndividual=100，迭代次數(shù)nbIteration=180，交叉概率pc和變異概率pm采用了自適應(yīng)參數(shù)設(shè)置。

其中pc1=0.9，pc2=0.6，pm1=0.2，pm2=0.02，fi為要進(jìn)行交叉或變異操作個(gè)體的評價(jià)值，favg為當(dāng)前種群的平均評價(jià)值，fmax為當(dāng)前種群的最大評價(jià)值。

由于標(biāo)準(zhǔn)模擬退火算法需要消耗很長的時(shí)間，而本文主要是借鑒模擬退火算法的思想，因此和模擬退火算法有關(guān)的參數(shù)設(shè)置較小。初始溫度t0=100，最低溫度tmin=0.1，退火系數(shù)a=0.9，溫度下降方式為t=t×a，每個(gè)溫度下對鄰域解的搜索次數(shù)為1。

4.3 實(shí)驗(yàn)結(jié)果

對于同一初始種群，分別用4種方法對其進(jìn)行優(yōu)化：（1）文獻(xiàn)[23]的改進(jìn)遺傳算法，記為GA1；（2）本文所設(shè)計(jì)的遺傳算法，記為GA2；（3）全局引入模擬退火算法的遺傳算法；（4）局部（前50次迭代）引入模擬退火算法的遺傳算法。進(jìn)化情況如圖11所示。

圖11 同一初始種群在不同算法下的優(yōu)化效果

從圖11中可以看出，本文所設(shè)計(jì)的遺傳算法有效地避免了種群的退化，并且跳出了局部最優(yōu)解，在更大的解空間內(nèi)搜索到了更好的解。在引入具有跳變能力的模擬退火算法之后，搜索的效率得到了進(jìn)一步的提高。由于在算法的前期應(yīng)當(dāng)盡量擴(kuò)大搜索范圍以提高找到更優(yōu)解的概率，而在中后期則應(yīng)集中對局部解空間的搜索，因此本文又嘗試僅在進(jìn)化前期引入模擬退火算法以增大搜索范圍，而在中后期只使用遺傳算法以加強(qiáng)局部搜索，進(jìn)一步提高了解的質(zhì)量。分別把方法（1）和（4）得到的各項(xiàng)評價(jià)指標(biāo)進(jìn)行對比，如表3所示。

表3 評價(jià)指標(biāo)比較

表3中各評價(jià)項(xiàng)目的計(jì)算方法如下?！敖虒W(xué)時(shí)間段的安排效果（每天第1、3和5個(gè)教學(xué)時(shí)間段）”的計(jì)算方法是：對于一周內(nèi)每天的第1、3和5個(gè)教學(xué)時(shí)間段，找出在這些時(shí)間段有教學(xué)安排的所有教室，用在該教學(xué)時(shí)間段和該教室上課的班級的小班數(shù)目乘以所學(xué)習(xí)科目的學(xué)分，作為相應(yīng)的科目安排效果的評價(jià)值，最后將所有教學(xué)時(shí)間段的所有教室的科目安排效果評價(jià)值相加?！翱颇康陌才判Ч钡挠?jì)算方法是：分別計(jì)算出每個(gè)小班的科目的安排效果，然后再取平均值?！翱傉n次的均勻程度”的計(jì)算方法是：分別計(jì)算出每個(gè)小班在一周內(nèi)每天總課次的標(biāo)準(zhǔn)差，然后再取平均值。

從表3中可以看出，每天教學(xué)效果最好的時(shí)間段，即第1，3和5個(gè)教學(xué)時(shí)間段，得到的評價(jià)值要明顯高于第2和4個(gè)教學(xué)時(shí)間段，達(dá)到了重要程度更高的科目被安排在教學(xué)效果更好的教學(xué)時(shí)間段的目的?？颇康陌才判Ч徒淌依寐识嫉玫搅烁倪M(jìn)，課次的分布也更為均勻。這里的教室利用率是一個(gè)接近50%的數(shù)值，說明學(xué)生在上課時(shí)能夠基本以間隔一個(gè)位置的方式就坐，這樣學(xué)生上課的舒適度會更高。

5 結(jié)束語

對于高校排課問題，合班教學(xué)是一個(gè)廣泛存在的現(xiàn)象，本文針對這個(gè)特點(diǎn)對問題進(jìn)行了數(shù)學(xué)建模，并設(shè)計(jì)了引入模擬退火算法的混合遺傳算法進(jìn)行求解，使兩種算法能夠互相彌補(bǔ)。實(shí)驗(yàn)結(jié)果表明，與一般的遺傳算法相比，本文提出的混合遺傳算法具有更高的搜索效率。

遺傳算子的方法設(shè)計(jì)并不只有一種，遺傳算法與其他智能算法的結(jié)合也有多種選擇，如何設(shè)計(jì)出合適的算子以及與更多智能算法相結(jié)合，是下一步將要研究的重點(diǎn)。

[1]Even S，Itai A，Shamir A.On the complexity of time table and multi-commodity flow problems[J].SIAM Journal of Computation，1976，5（4）：691-703.

[2]Carter W M，Tovey C.When is the classroom assignment problem hard?[J].Operations Research，1989，40（S1）：28-39.

[3]Junginger W.Timetabling in Germany-asurvey[J].Interface，1986，16（4）：66-74.

[4]Neufeld G A，Tartar J.Graph coloring conditions for the existence of solutions to the timetable problem[J].Communications of the ACM，1974，17（8）：450-453.

[5]de Werra D.An introduction to timetabling[J].European Journal of Operational，1985，19（2）：151-162.

[6]Shih W，Sullivan J A.Dynamic course scheduling for college faculty via zero-one programming[J].Decision Sciences，1977，8（4）：711-721.

[7]McClure R H，Wells C E.A mathematical programming model for faculty course assignments[J].Decision Sciences，1984，15（3）：409-420.

[8]Tripathy A.School timetabling-a case in large binary integer linear programming[J].Management Science，1984，30（12）：1473-1489.

[9]Ostermann R，de Werra D.Some experiments with a timetabling system[J].OR Spectrum，1982，3（4）：199-204.

[10]Mulvey J M.A classroom/time assignment model[J].European Journal of Operational Research，1982，9（1）：64-70.

[11]Yu E，Sung K S.A genetic algorithm for a university weekly courses timetabling problem[J].International Transactions in Operational Research，2002，9（6）：703-717.

[12]Ueda H，Ouchi D，Takahashi K，et al.Comparisons of genetic algorithms for timetabling problems[J].Systems and Computers in Japan，2004，35（7）：1-12.

[13]Kohshori M S，Liri M S.Multi population hybrid genetic algorithms for university course timetabling[J].International Journal for Advances in Computer Science，2012，3（1）：12-22.

[14]Liu Y，Zhang D，Leung S C H.A simulated annealing algorithm with a new neighborhood structure for the timetabling problem[C]//Proceedings of the 1st ACM/SIGEVO Summit on Genetic and Evolutionary Computation，2009.

[15]Minh K N T T，Thanh N D T，Trang K T，et al.Using tabu search for solving a high school timetabling problem[M]//Studiesin computationalintelligence，2010：305-313.

[16]Jat S N，Yang S.A hybrid genetic algorithm and tabu search approach for post enrolment course timetabling[J].Journal of Scheduling，2011，14（6）：617-637.

[17]Chiarandini M，Birattari M，Socha K，et al.An effective hybrid algorithm foruniversity course timetabling[J].Journal of Scheduling，2006，9（5）：403-432.

[18]汪曉飛，李曉寧.GA編碼方案在高校排課系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（17）：4565-4567.

[19]李紅蟬，朱顥東.采用十進(jìn)制免疫遺傳算法求解高校排課問題[J].系統(tǒng)工程理論與實(shí)踐，2012，32（9）：2031-2036.

[20]王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安：西安交通大學(xué)出版社，2002.

[21]王凌.智能優(yōu)化算法及其應(yīng)用[M].北京：清華大學(xué)出版社，2004.

[22]LewisR.A survey ofmetaheuristic-based techniques foruniversity timetabling problems[J].OR Spectrum，2008，30（1）：167-190.

[23]李紅蟬，朱顥東.基于最佳個(gè)體置換策略的高校排課問題求解[J].計(jì)算機(jī)工程，2011，37（19）：186-188.