面向高校統(tǒng)一教學(xué)資源排課問(wèn)題的啟發(fā)式方法

張德珍，陳剛，王營(yíng)，郭賽君，李永華

（1.大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院，遼寧大連 116026；

2.大連海事大學(xué)研究生院，遼寧大連 116026；

3.大連拓?fù)鋫I(yè)科技有限公司，遼寧大連 116600）

面向高校統(tǒng)一教學(xué)資源排課問(wèn)題的啟發(fā)式方法

張德珍1，陳剛1，王營(yíng)2，郭賽君1，李永華3

（1.大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院，遼寧大連 116026；

2.大連海事大學(xué)研究生院，遼寧大連 116026；

3.大連拓?fù)鋫I(yè)科技有限公司，遼寧大連 116600）

面向高校整體教學(xué)資源環(huán)境下的復(fù)雜多約束排課問(wèn)題，提出了一種啟發(fā)式方法.基于實(shí)際教學(xué)過(guò)程中涉及學(xué)生、任課教師、上課教室，以及各自的可行時(shí)間段等教學(xué)資源下的復(fù)雜多約束條件建立了約束函數(shù)，構(gòu)建了以學(xué)生每周上課節(jié)次的均勻度與教師對(duì)任課時(shí)間滿意度最大化為目標(biāo)函數(shù)的優(yōu)化模型.在求解過(guò)程中，將各約束條件轉(zhuǎn)化為關(guān)系代數(shù)的關(guān)系運(yùn)算，在縮小解空間的基礎(chǔ)上進(jìn)而采用啟發(fā)式策略進(jìn)行優(yōu)選.最后，以一個(gè)實(shí)際高校的排課算例驗(yàn)證本文方法的有效性.

高校排課問(wèn)題；優(yōu)化；啟發(fā)式算法；關(guān)系運(yùn)算

1 引言

高校排課問(wèn)題隨著我國(guó)高等教育改革的不斷深化，變得越來(lái)越突出.一方面，在招生規(guī)模擴(kuò)大，學(xué)生個(gè)性化培養(yǎng)模式不斷出現(xiàn)的情況下，以往的以“班級(jí)”為單位的排課方法與新的培養(yǎng)模式不相符；另一方面，由于高校招生類別不斷細(xì)化，如本科、學(xué)術(shù)型碩士、專業(yè)學(xué)位碩士與博士等，而現(xiàn)階段我國(guó)本科和研究生教學(xué)體系是分開(kāi)進(jìn)行的，缺乏統(tǒng)一教學(xué)資源管理平臺(tái)，同一學(xué)校又公用統(tǒng)一教學(xué)資源，即教學(xué)場(chǎng)館（所）及其可用時(shí)間段、任課教師及其可支配時(shí)間段、選課學(xué)生及其可行時(shí)間段和所開(kāi)設(shè)的課程，以往僅單方面針對(duì)某一學(xué)生類別的排課策略，不僅是當(dāng)前多類別學(xué)生排課理論的缺失，而且在教學(xué)資源的計(jì)劃統(tǒng)籌、優(yōu)化配置等方面，極易造成浪費(fèi)，缺乏有效科學(xué)方法指導(dǎo).

排課問(wèn)題是典型的多目標(biāo)組合優(yōu)化問(wèn)題，Even等［1］證明排課問(wèn)題為NP完全類問(wèn)題.在早期，排課問(wèn)題的解決方法主要為模擬手工排課的啟發(fā)式方法［2,3］，該方法具有人工排課的靈活性特點(diǎn)，一定程度上減輕了手工排課的繁雜工作量，但由于缺乏全局范疇的優(yōu)化統(tǒng)籌，當(dāng)教學(xué)資源相對(duì)緊缺，排課量大時(shí)，容易造成排課后期部分課程無(wú)解，即排課失敗，而不得不返回重新調(diào)整.后來(lái)，研究者們將排課問(wèn)題簡(jiǎn)化為一些經(jīng)典問(wèn)題來(lái)求解，出現(xiàn)了整數(shù)規(guī)劃法［4］、拉格朗日松弛法［5］、切割平面法［6］以及基于網(wǎng)絡(luò)流方法［7］等.此類方法很大程度上簡(jiǎn)化了排課問(wèn)題，但也往往忽略了部分實(shí)際過(guò)程中的約束條件.隨著計(jì)算機(jī)技術(shù)和現(xiàn)代智能優(yōu)化技術(shù)的發(fā)展，應(yīng)用模擬退火［8］、禁忌搜索［9］、遺傳算法［10］、蟻群算法［11,12］以及HSA［13］等方法，在局部尋優(yōu)求解方面具有較好性能.但類似算法通常針對(duì)某些高校自身教學(xué)體系的特點(diǎn)進(jìn)行個(gè)性化設(shè)計(jì)，缺乏對(duì)實(shí)際問(wèn)題的復(fù)雜多約束性考慮，忽略了統(tǒng)一教學(xué)資源環(huán)境下各種資源的綜合調(diào)配及優(yōu)化處理.因而，缺少通用性及系統(tǒng)性，這種現(xiàn)象在我國(guó)當(dāng)前在用的排課系統(tǒng)中較為突出.

本文面向高校整體教學(xué)資源環(huán)境下的復(fù)雜多約束排課問(wèn)題，提出了一種啟發(fā)式方法，綜合考慮了全校整體教學(xué)資源的優(yōu)化配置，并基于實(shí)際教學(xué)過(guò)程中的復(fù)雜多約束條件，構(gòu)建了以學(xué)生每周上課節(jié)次的均勻度與教師對(duì)任課時(shí)間滿意度加權(quán)和最大化為目標(biāo)函數(shù)的優(yōu)化模型，將啟發(fā)式規(guī)則轉(zhuǎn)化為關(guān)系運(yùn)算的方式，在縮小后的解空間內(nèi)采用啟發(fā)式方法求解，以實(shí)際排課問(wèn)題加以應(yīng)用驗(yàn)證.

2 問(wèn)題描述及模型

2.1 符號(hào)定義

本文中關(guān)于排課問(wèn)題的集合定義、變量表示及符號(hào)定義如下：

教學(xué)時(shí)間段集合為D=P×W×J，其中P為每學(xué)期開(kāi)課的周次，P=｛1,2,...,｝,≤20；

Timet表示教師t的可用時(shí)間段，Timet=｛（p,w,j）｝,p∈P,w∈W,j∈J；

Rrpwj表示教室r在第p周的第w天的第j時(shí)間段是否安排課程的二進(jìn)制變量，若該時(shí)間段可以安排課程，則Rrpwj=1，否則Rrpwj=0；

asj表示第s個(gè)學(xué)生的第j節(jié)課與第j+1節(jié)課之間的時(shí)間間隔是否滿足均勻間隔Js的二進(jìn)制變量，若滿足均勻間隔，則asj=1，否則asj=0；

pcpwj表示教師對(duì)課程c安排在第p周的第w天的第j時(shí)間段的滿意程度，若（p,w,j）∈Timet，則pcpwj=1，否則pcpwj=0；

xcrpwj為決策變量，若課程c安排于第p周的第w天的第j時(shí)間段在教室r上課，則xcrpwj=1，否則xcrpwj=0.

2.2 問(wèn)題描述

高校排課問(wèn)題是將教學(xué)計(jì)劃擬開(kāi)設(shè)的課程集C，分配到教室資源集R，并分布到各可用時(shí)間段集D中，給每門課程安排所需的教室和合理的時(shí)間段.其中課程集C中的每門課程c由若干學(xué)生（隸屬集合S）選修，并由一名或多名教師（隸屬集合T）任教，同時(shí)，一個(gè)學(xué)生可以選修多門課程，一名教師可以任教多門課程，對(duì)教室資源R中的每一間教室r，其可用時(shí)間段隸屬于集合D.以下建立排課過(guò)程涉及到的約束條件和目標(biāo)函數(shù).

1）約束條件

課程表是基于排課諸要素滿足必要條件的有意義的編排.針對(duì)實(shí)際應(yīng)用中的排課問(wèn)題，建立約束條件如下：

在同一時(shí)間，學(xué)生s∈S只能上一門課程，即

在同一時(shí)間，教師t∈T只能講授一門課程，即

在同一時(shí)間，教室r∈R只能進(jìn)行一門課程，即

對(duì)每門課程c∈C需達(dá)到預(yù)定的教學(xué)時(shí)數(shù)nc，即

教室容量br大于等于該教室上課人數(shù)，即教室總數(shù)ˉr大于等于同一時(shí)間安排的課程總數(shù)，即

特殊課程需安排在特殊類型的教室里，其中RTSR表示教室集合R中去掉特殊教室TSR的剩余教室集合，即

若教室r在時(shí)間（p,w,j）上不能安排課程，即Rrpwj=0，則任何一門課程c在時(shí)間（p,w,j）都不能安排在教室r，即

2）目標(biāo)函數(shù)

排課問(wèn)題是在諸多可行方案中進(jìn)行優(yōu)選的過(guò)程，衡量排課方案的優(yōu)劣往往難以用一個(gè)指標(biāo)進(jìn)行評(píng)判.本文綜合考慮學(xué)生的學(xué)習(xí)接受能力及任課教師的教學(xué)、科研時(shí)間搭配等影響因素，將目標(biāo)函數(shù)歸結(jié)為學(xué)生每周上課節(jié)次的均勻度與教師任課時(shí)間滿意度之加權(quán)和，即

3 模型求解

本文的優(yōu)化模型是在滿足條件（1）～（9）的情況下，使目標(biāo)函數(shù)（10）達(dá)到最大，即綜合考慮學(xué)生的學(xué)習(xí)接受能力及任課教師的教學(xué)、科研時(shí)間搭配等影響因素，使學(xué)生每周上課節(jié)次的均勻度與教師任課時(shí)間滿意度之加權(quán)和達(dá)到最大值.

3.1 問(wèn)題規(guī)模

排課問(wèn)題的NP-hard本質(zhì)，決定了求解的困難性，特別是在排課數(shù)量大（通常超過(guò)300門），學(xué)生選課情況復(fù)雜（多類別、跨專業(yè)）的情況下，其排課問(wèn)題的求解規(guī)模極大.以下針對(duì)2.2節(jié)中的問(wèn)題描述，討論其排課問(wèn)題的規(guī)模.

以大連海事大學(xué)2013-2014第一學(xué)期統(tǒng)招碩士、統(tǒng)招博士的523門待排課程為例，總學(xué)時(shí)數(shù)為13856，可用教室數(shù)為363，則排課的規(guī)模為

對(duì)如此規(guī)模的問(wèn)題，需要采取有效的方法進(jìn)行求解.考慮到課程表是排課諸要素滿足必要條件的有意義的編排，本文采用啟發(fā)式方法，首先將排課約束條件轉(zhuǎn)變?yōu)閱l(fā)式規(guī)則，并采用關(guān)系代數(shù)表達(dá)式將對(duì)應(yīng)的約束函數(shù)等價(jià)變換為關(guān)系之間的運(yùn)算，進(jìn)而轉(zhuǎn)化為關(guān)系型數(shù)據(jù)庫(kù)中的SQL操作，逐步縮小解空間的搜索范圍，在此基礎(chǔ)上采用啟發(fā)式方法在縮小后的可行解空間中進(jìn)行優(yōu)選.

3.2 約束的關(guān)系代數(shù)轉(zhuǎn)換

首先定義排課相關(guān)的關(guān)系模式如下：

學(xué)生選課關(guān)系模式SC：學(xué)號(hào)（GID），課程號(hào)（CID），任課教師（TID），班級(jí)（Cls），學(xué)時(shí)（Shr），學(xué)分（Cre）；

課程關(guān)系模式CI：課程號(hào)（CID），課程名（CNm），課程類別（CIt），上課時(shí)間（ST）；

教室關(guān)系模式CR：教室號(hào)（RID），教室名（RNm），最大容納人數(shù)（MCp），教室類型（Rty），教室需求（Cnd）；

教室與時(shí)間關(guān)系模式NR：教室號(hào)（RID），上課時(shí)間（ST），教室不可用時(shí)間（NT）；

課程與教室關(guān)系模式CD：課程號(hào)（CID），教室號(hào)（RID）.

將上述約束條件（1）～（9）轉(zhuǎn)化為如下關(guān)系代數(shù)表示，其中??表示自然連接操作，∏表示投影操作，σ表示選擇操作，*表示所有屬性，count（·）表示計(jì)數(shù)函數(shù)，G表示聚集操作.

式（1）轉(zhuǎn)化為

把學(xué)生s∈S的上課時(shí)間投影到q1，將q1中的上課時(shí)間按時(shí)間進(jìn)行分組聚集操作，將分組的結(jié)果記錄為Q1，因在同一時(shí)間，學(xué)生s∈S只能上一門課程，故Q1中所有元素均小于等于1.

式（2）轉(zhuǎn)化為

把教師t∈T的上課時(shí)間投影到q2，將q2中的上課時(shí)間按時(shí)間進(jìn)行分組聚集操作，將分組的結(jié)果記錄為Q2，因在同一時(shí)間，教師t∈T只能講授一門課程，故Q2中所有元素均小于等于1.

式（3）轉(zhuǎn)化為

把教室r∈R的上課時(shí)間投影到q3，將q3中的上課時(shí)間按時(shí)間進(jìn)行分組聚集操作，將分組的結(jié)果記錄為Q3，因在同一時(shí)間，教室r∈R只能進(jìn)行一門課程，故Q3中所有元素均小于等于1.

式（4）轉(zhuǎn)化為

按課程進(jìn)行分組聚集操作，記錄課程c∈C的上課次數(shù)為Q4，因?qū)γ块T課程c∈C需達(dá)到預(yù)定的教學(xué)時(shí)數(shù)nc，故Q4=nc.

式（5）轉(zhuǎn)化為

記錄課程c∈C的上課人數(shù)為Q5，記錄課程c∈C所在上課教室的最大容納人數(shù)MCp記為，因教室容量大于等于該教室上課人數(shù)，故Q5≤.

式（6）轉(zhuǎn)化為

記錄某時(shí)刻d∈D開(kāi)設(shè)課程的總數(shù)為Q6，因教室總數(shù)大于等于同一時(shí)間安排的課程總數(shù)，故Q6≤.

式（8）轉(zhuǎn)化為σCID=c,Cnd=Rty（CICDCR）.該式表示課程c∈C安排的教室類型Rty與教室類型需求Cnd相同的記錄，若記錄為空，則表示課程c∈C安排的教室類型與教室類型需求不相同，若記錄不為空，則兩者相同.

式（9）轉(zhuǎn)化為q9←（σST=NT（CICDNR））.將上課時(shí)間與教室不可用時(shí)間相同的記錄進(jìn)行選擇并記錄為q9，若q9=?，則表示上課時(shí)間在教師可用時(shí)間范圍內(nèi).若教室r∈R在某時(shí)間不能安排課程，則任何一門課程c（c∈C）在該時(shí)間都不能安排在教室r（r∈R），即q9=?時(shí)，約束3中的Q3=0.

上述各關(guān)系代數(shù)形式實(shí)際上是一種啟發(fā)式規(guī)則的表現(xiàn)，在關(guān)系數(shù)據(jù)庫(kù)中通過(guò)結(jié)構(gòu)化查詢語(yǔ)言（SQL）實(shí)現(xiàn)操作，從而獲得縮小后的解空間，為在此基礎(chǔ)上的啟發(fā)式方法求解提供基礎(chǔ).

3.3 算法步驟

步驟1初始化排課基礎(chǔ)數(shù)據(jù)i=1，擬開(kāi)設(shè)課程集C，教室資源集R，可用教室集R′（R′?R），學(xué)生集合S，選擇課程c（c∈C）的所有學(xué)生記錄集記為Sc，教師集合T，教師t（t∈T）的任課記錄集記為Ct，學(xué)生s（s∈S）上課的沖突時(shí)間段集合記為Ds；

步驟3隨機(jī)選擇一門優(yōu)先級(jí)最高的待排課程j；

步驟4獲取選擇課程j的所有學(xué)生記錄集Sj，且j∈C；

步驟5若s∈S，執(zhí)行如下操作：

1）獲取學(xué)生s的所有課程，根據(jù)式（11）標(biāo)記所有沖突時(shí)間段Ds；2）s←s+1；

步驟6若Ds中的元素與所有時(shí)間段都沖突，則調(diào)整已排課程，得到可用時(shí)間段，轉(zhuǎn)到步驟5；

步驟7獲取任教課程j的教師（們）任課記錄集Ct，且t∈Ct；

步驟8根據(jù)上式（12）以及Ct標(biāo)記沖突時(shí)間段；

步驟9若所有時(shí)間段都沖突，則調(diào)整已排課程，得到不沖突時(shí)間段；步驟10獲取可用教室的記錄集R′（R′?R）；

步驟11若可用教室資源為0，則增加可用教室，并轉(zhuǎn)到步驟12；

步驟12在避免上述所有沖突的情況下尋找滿足上述約束（14）～（16）的所有可用教室.若教室資源不足，則增加教室資源；

步驟13獲取任教課程j的教師（們）的禁忌時(shí)間段；

步驟14基于貪心策略選擇教室容量br減去j的上課人數(shù)最小的教室，優(yōu)先選擇符合間隔條件，且與教師禁忌時(shí)間不沖突的時(shí)間段；

步驟15保存課程j的排課結(jié)果，i←i+1，轉(zhuǎn)到步驟2.

4 實(shí)驗(yàn)結(jié)果及分析

以大連海事大學(xué)2012-2013學(xué)年第二學(xué)期和2013-2014學(xué)年第一學(xué)期，全體學(xué)術(shù)型碩士研究生、全日制專業(yè)學(xué)位研究生和博士研究生的教學(xué)計(jì)劃課程編排為例，采用本文提出的啟發(fā)式算法進(jìn)行求解，系統(tǒng)運(yùn)行于C/S（客戶端/服務(wù)器）網(wǎng)絡(luò)體系結(jié)構(gòu)，其中客戶端硬件配置為CPU-Intel Core E4600，內(nèi)存3GB，OS-windows7 ultimate；服務(wù)器硬件配置為CPU-Intel Core E5200，內(nèi)存-4GB，OS-Windows Server 2008；編譯環(huán)境為visual Studio 2010.表1顯示大連海事大學(xué)研究生院兩個(gè)學(xué)期的有關(guān)排課數(shù)據(jù).

在實(shí)際排課過(guò)程中，可按需設(shè)置目標(biāo)函數(shù)中的α值，使排課結(jié)果側(cè)重于教師滿意度或側(cè)重于課程間隔均勻度.當(dāng)α=0.5時(shí)，排課實(shí)驗(yàn)結(jié)果如表2所示.從表2中可以看出，2012-2013學(xué)年第二學(xué)期課程間隔均勻度為72.9%，2013-2014學(xué)年第一學(xué)期全體碩士和博士的課程均勻間隔度為79.1%.教師滿意度數(shù)據(jù)以排課前教師事先錄入的信息為準(zhǔn)，在此不再羅列，計(jì)算得到2012-2013學(xué)年第二學(xué)期的教師滿意度為89.2%，2013-2014學(xué)年第一學(xué)期的教師滿意度為86.8%.

表1 大連海事大學(xué)研究生院兩個(gè)學(xué)期有關(guān)排課數(shù)據(jù)Table 1 The Characteristics of Datasets of two semesters from the Graduate School of DLMU

表2 排課結(jié)果Table 2 Computational results of proposed method

表3給出了部分排課結(jié)果界面，該排課結(jié)果已經(jīng)應(yīng)用于大連海事大學(xué)研究生院2013-2014學(xué)年第一學(xué)期所有類別研究生的教學(xué)過(guò)程中，實(shí)際檢測(cè)無(wú)異常.對(duì)個(gè)別教師上課時(shí)間的個(gè)性化需求，通過(guò)系統(tǒng)的手動(dòng)調(diào)整功能得到滿足.由于綜合考慮了教師滿意度和課程均勻間隔度，使課程的安排最大可能地滿足教師和學(xué)生的上課需求.

表3 部分課程的排課界面Table 3 A partial illustration of a feasible timetable

5 結(jié)束語(yǔ)

本文針對(duì)高校整體教學(xué)資源環(huán)境下的復(fù)雜多約束排課問(wèn)題，構(gòu)建了以學(xué)生課程間隔的均勻度與任課教師滿意度加權(quán)和最大化為目標(biāo)函數(shù)的優(yōu)化模型，為高校排課問(wèn)題的可行解提供了一種新的評(píng)價(jià)方法；在求解過(guò)程中采用啟發(fā)式方法，將排課約束轉(zhuǎn)變?yōu)閱l(fā)式規(guī)則，并采用關(guān)系代數(shù)表達(dá)式將對(duì)應(yīng)的約束函數(shù)等價(jià)變換為關(guān)系之間的運(yùn)算，逐步縮小解空間的搜索范圍，在此基礎(chǔ)上，采用啟發(fā)式方法在縮小后的可行解空間進(jìn)行優(yōu)選，為此類問(wèn)題提供了一種新的求解方法.

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

［2］Black A.Techniques for producing school timetables on a computer and their application to other scheduling problems［J］.The Computer Journal，1961，4（3）：237-245.

［3］GotliebCC.Theconstructionofclass-teachertimetables［C］//ProceedingsoftheInternationalFederationforInformationProcessing Congress.Amsterdam：North-Holland Publishing Co，1963，73-77.

［4］Shaw C C，Yu C C.From timetabling to train regulation：A new train operation model［J］.Information and Software Technology，2005，9（47）：575-585.

［5］Arabinda T.School timetabling：A case in large binary integer linear programming［J］.Management Science，1984，30（12）：1473-1489.

［6］Pasquale A，Igor V.A computational study of a cutting plane algorithm for university course timetabling［J］.Journal of Scheduling，2005，6（8）：497-514.

［7］諶效東.實(shí)用化計(jì)算機(jī)輔助排課系統(tǒng)的研究與實(shí)現(xiàn)［J］.西安電子科技大學(xué)學(xué)報(bào)，1991，18（3）：38-44.

Chen Xiaodong.A study and implementation of the practical computer-aided timetable scheduling system［J］.Journal of Xidian University，1991，18（3）：38-44.（in Chinese）

［8］Aldy G，Kien M N，Kim L P.A hybridized Lagrangian relaxation and simulated annealing method for the course timetabling problem［J］.Computers and Operations Research，2012，12（39）：3074-3088.

［9］周小鋒，劉健.基于偶圖匹配和禁忌搜索的排課新算法［J］.系統(tǒng)工程理論與實(shí)踐，2008，28（3）：111-117.

Zhou Xiaofeng，Liu Jian.A new approach to curriculum scheduling based on graph matching and tabu search［J］.Systems Engineering：Theory and Practice，2008，28（3）：111-117.（in Chinese）

［10］Yang S X，Sadaf N J.Genetic algorithms with guided and local search strategies for university course timetabling［J］.IEEE Transactions on Systems，Man，and Cybernetics：Part C，Applications and Reviews，2011，41（1）：93-106.

［11］靳志宏，于波，侯麗曉.基于配載約束的配送優(yōu)化問(wèn)題及其求解算法［J］.系統(tǒng)工程學(xué)報(bào)，2012，27（3）：390-398.

Jin Zhihong，Yu Bo，Hou Lixiao.Vehicle routing optimization problem and its solution method based on vehicle loading constraints［J］.Journal of Systems Engineering，2012，27（3）：390-398.（in Chinese）

［12］Thatchai L，Pupong P.Best-worst ant colony system parameter investigation by using experimental design and analysis for course timetabling problem［C］//Second International Conference on Computer and Network Technology.IEEE Computer Society，2010，467-471.

［13］Mohammed A A，Ahamad T K，Munir Z.University course timetabling using a hybrid harmony search metaheuristic algorithm［J］.

IEEE Transactions on Systems，Man，and Cybernetics：Part C，Applications and Reviews，2012，42（5）：664-681.

University course timetabling problem using a heuristic approach based on uniform teaching resources

Zhang Dezhen1，Chen Gang1，Wang Ying2，Guo Saijun1，Li Yonghua3

（1.College of Information Science and Technology，Dalian Maritime University，Dalian 116026，China；
2.Graduate School，Dalian Maritime University，Dalian 116026，China；
3.Dalian Top Software Science and Technology Ltd，Dalian 116600，China）

The paper studies the university course timetabling problem（UCTP）with the practical-relevant problems based on the union teaching resources of a university for undergraduates，postgraduates and PhD. students.A new heuristic method for UCTP is presented，considering complex multi-constraint conditions based on the uniform teaching resources which include students，teachers and classrooms with feasible times lot，respectively.The constraints are modeled and the objective function is proposed based on the evenness for all the curriculums of a student and a teacher's satisfaction for his/herlecturing time.And then，transform the constraints to relational operation expressed by relation algebra.Thereby heuristic rules are formed by relational calculus.Greedy strategy is applied to search the optimal solutions in the shrunk solution space. Finally，a course timetabling instance from a university is carried out to demonstrate the validation of the new method.

university course timetabling problem；optimization；heuristic algorithm；relational operation

TP273

A

1000-5781（2015）06-0836-08

10.13383/j.cnki.jse.2015.06.011

張德珍（1973-），男，遼寧大連人，博士后，副教授，研究方向：優(yōu)化理論，軟件工程，Email：dezhen.zhang@gmail.com；

陳剛（1989-），男，山東淄博人，碩士生，研究方向：軟件工程，Email：cg82616424@163.com；

王營(yíng)（1980-），女，遼寧大連人，助理研究員，研究方向：研究生教育管理Email：jjxiaoker@163.com；

郭賽君（1989-），女，山西長(zhǎng)治人，碩士生，研究方向：軟件工程，Email：1031348593@qq.com；

李永華（1987-），女，遼寧大連人，工程師，研究方向：應(yīng)用數(shù)學(xué)，Email：605651670@qq.com.

2013-11-05；

2014-05-02.

遼寧省研究生培養(yǎng)機(jī)制改革研究資助項(xiàng)目（201310151-40）；大連海事大學(xué)研究生教育教學(xué)改革資助項(xiàng)目（YJG2013001）；中央高?；究蒲袠I(yè)務(wù)費(fèi)資助項(xiàng)目（01750312）.