高校排課多元優(yōu)化策略與自動(dòng)實(shí)現(xiàn)方法的研究

【摘要】通過分析高校排課需求，提出高校排課諸多優(yōu)化與合理性要求：包括排課時(shí)間、學(xué)生班級(jí)、教師、教室等相關(guān)的多項(xiàng)合理性原則，以及最佳時(shí)間間隔均度、最佳時(shí)間分布均度、最大耦合度、最小流動(dòng)值、最大利用率等指標(biāo)。將排課過程進(jìn)行分類分步驟實(shí)現(xiàn)，每類課程有各自的排入優(yōu)先次序和排入時(shí)間段，通過循環(huán)給出有限的合理時(shí)間模式、進(jìn)行耦合匹配檢測(cè)、多級(jí)回溯等方法實(shí)現(xiàn)各類課程的自動(dòng)排課，最后再進(jìn)行補(bǔ)排、調(diào)整，使排課結(jié)果更合理。

【關(guān)鍵詞】高校自動(dòng)排課；合理化指標(biāo)；時(shí)間模式及匹配；耦合；回溯

【中圖分類號(hào)】G40-057 【文獻(xiàn)標(biāo)識(shí)碼】A 【論文編號(hào)】1009—8097（2011）07—0105—05

引言

排課在高校教務(wù)管理工作中處于核心地位，課程編排的合理與否直接關(guān)系到每個(gè)學(xué)生的學(xué)習(xí)效率、教師的教學(xué)效果和教室的利用率等等。排課又是所有教務(wù)工作中最復(fù)雜的，不但要考慮學(xué)生、教師、教室的排課時(shí)間不沖突，還要考慮各排課要素的合理性。特別是高校課程，存在著單雙周、前后節(jié)、分段、分班、合班、教師合上、教師多課、大教室、小教室、特殊教室等諸多復(fù)雜因子，使得高校排課非常費(fèi)時(shí)費(fèi)工。

因此，計(jì)算機(jī)自動(dòng)排課是必須的。盡管國內(nèi)外關(guān)于計(jì)算機(jī)排課的研究一直不間斷地進(jìn)行著，但研究主要集中在排課算法方面[1]， 主要解決排課四要素不沖突問題，是關(guān)于自動(dòng)排課是否可用的問題，并沒有一種可以一鍵解決所有問題的方法。另外，排課算法也很難兼顧最優(yōu)化[5]與合理性，合理性是關(guān)于自動(dòng)排課是否用得好的問題，合理性不易靠算法實(shí)現(xiàn)。

為此，應(yīng)從研究排課的合理性原則出發(fā)，給出基于合理性原則的自動(dòng)排課實(shí)現(xiàn)方法，以最優(yōu)化地解決高校排課在時(shí)間、教室、學(xué)生班級(jí)和教師等方面多元合理性問題。

一 高校排課復(fù)雜性分析

任何排課系統(tǒng)都必須考慮時(shí)間、教室、教師、班級(jí)四要素[1]，而高校課程系統(tǒng)中，四要素又各有自己的復(fù)雜性[2]。

關(guān)于學(xué)生班級(jí)：中小學(xué)行政班級(jí)就是授課班級(jí)，且各班人數(shù)基本相等，排課的基本單位就是行政班級(jí)。高校課程體系中不但各行政班級(jí)人數(shù)差別較大，且存在著許多班級(jí)組合與拆分的課程組合情況，如許多社科類、基礎(chǔ)類課程是多班合上的大課，許多專業(yè)基礎(chǔ)課是兩三個(gè)專業(yè)合上的小合班課，許多具有實(shí)驗(yàn)環(huán)節(jié)的課程的實(shí)驗(yàn)部分是分班課，等等。因此，高校排課系統(tǒng)不但要考慮按基本的行政班排課，還要考慮合班上課情況和分班上課情況，合班包含大合班和兩班合上的小合班情況，分班包含全部課時(shí)分班上和部分課時(shí)分班上的情況。另外高校還存在不按班級(jí)排課的公共選修課。

關(guān)于教室：中小學(xué)班級(jí)教室一般就是行政班級(jí)的上課教室，且教室種類單一。高校一般不存在班級(jí)教室，且教室具有多樣性。按容量分：包括階梯教室、大教室、小教室，按功能分：包括普通教室、語音教室、機(jī)房、專業(yè)實(shí)驗(yàn)室等。

關(guān)于教師：中小學(xué)一個(gè)教師主上一門課。高校教師存在著一個(gè)教師上多門課和多個(gè)教師合上一門課的情況。

關(guān)于時(shí)間：中小學(xué)課程基本是一門課程占一時(shí)間單元，即排課的基本單位是一節(jié)課。高校排課時(shí)間的安排是最復(fù)雜的。首先，高校大多數(shù)課程是按兩節(jié)課連排的，即排課的基本單位是連續(xù)二節(jié)課，但高校許多課程的周學(xué)時(shí)卻是單數(shù)的，存在著1、3、5學(xué)時(shí)課程，一般要通過單雙周排課的方法解決，3、5學(xué)時(shí)的課程也可通過三節(jié)連上的方法解決。其次，即使是二節(jié)課連上的情況，還存在著前節(jié)和后節(jié)需要不同安排的情況，如大學(xué)英語課一般是4學(xué)時(shí)，其中有1學(xué)時(shí)是聽力課，需要在語音室上課，所以大學(xué)英語課每周排兩次，其中一次課的前后兩節(jié)中有一節(jié)要安排在語音室上課，因此，高校排課時(shí)間上還要解決前后節(jié)組合的問題。第三，對(duì)于許多特殊專業(yè)課還存在一段時(shí)間連續(xù)上課的情況，如藝術(shù)類的課程，往往是集中安排在連續(xù)的幾周內(nèi)完成，每周上課時(shí)間或是完整的一天，或是半天，此類課程稱為分段授課課程。

二 高校排課合理性原則與策略

高校排課不但排課要素的復(fù)雜程度高，對(duì)排課還有一定的原則性要求?？傇瓌t是四要素不能沖突，這是必要條件。另外還有一些非必要性的原則與策略，即合理性原則，四要素有其內(nèi)在的和相關(guān)的合理性原則。

關(guān)于學(xué)生班級(jí)與教室相關(guān)的合理性原則，主要是班級(jí)教室最少移動(dòng)性和容量最佳耦合性。班級(jí)教室最少移動(dòng)性是指一個(gè)班級(jí)所有課程應(yīng)盡量安排在同一教室內(nèi)，雖然高校班級(jí)上課地點(diǎn)不要求固定，但如果一個(gè)班的課程大多數(shù)被安排在相對(duì)固定的教室，不但可以減少學(xué)生課間換教室的時(shí)間，更可給予班級(jí)歸宿感。容量最佳耦合性是指為所有班級(jí)分配的教室容量與班級(jí)人數(shù)差值的平均值最小。由于高校班級(jí)人數(shù)不等，教室容量不一，應(yīng)避免小班占大教室的情況，優(yōu)先保證多班的大合班課程占用大教室，以節(jié)省教室資源。

關(guān)于學(xué)生班級(jí)與上課時(shí)間相關(guān)的合理性原則，主要是同班級(jí)課程總體分布均勻性和同班級(jí)課程的時(shí)間最佳耦合性。課程總體分布均勻性是指一個(gè)班級(jí)的所有課程應(yīng)盡量均勻分布在五天上課時(shí)間內(nèi)，每天課時(shí)總量盡量相當(dāng)，既要避免出現(xiàn)某天課程排得過滿，也要避免某天課時(shí)太少，甚至沒有課。時(shí)間最佳耦合性主要是單雙周課程最佳耦合，在某個(gè)班級(jí)有多個(gè)單節(jié)課的情況下，最好單雙周平分，且時(shí)間安排上使一組單周課和雙周課共用一個(gè)連續(xù)二節(jié)的課時(shí)。這樣使學(xué)生不至于因周數(shù)忘記上課，也有利用學(xué)生集中時(shí)間選其它課程。

關(guān)于教室與時(shí)間相關(guān)的合理性原則，主要是同教室的時(shí)間最佳耦合性。這里專指英語聽力課程，由于一般高校語音教室資源有限，應(yīng)避免語音教室空置的情況。而語音聽力課周學(xué)時(shí)為一節(jié)，一般安排在連續(xù)二節(jié)中的前節(jié)或后節(jié)。對(duì)于多個(gè)班的語音聽力課，應(yīng)盡量平分前后節(jié)，使二個(gè)班的聽力課可以按前后節(jié)耦合在同一個(gè)二節(jié)時(shí)間段里，分用語音室。

關(guān)于教師與時(shí)間相關(guān)的合理性原則，主要是不同課程的時(shí)間最佳耦合性和教師最少移動(dòng)性。時(shí)間最佳耦合性是指同教師單雙周耦合，有利于教師記住上課時(shí)間。教師最少移動(dòng)性是指同一教師的課程，應(yīng)在總體分布均勻合理且日課程量不超過四節(jié)的前提下，盡量安排在同天，這樣既保證教師的授課效果，也減少教師多次往返學(xué)校的時(shí)間。

關(guān)于時(shí)間與課程相關(guān)的合理性原則，主要是同課程時(shí)間間隔均勻性。應(yīng)避免一門課程連續(xù)上兩天或三天情況。

三 自動(dòng)排課合理性指標(biāo)

基于以上原則，計(jì)算機(jī)自動(dòng)排課算法或方法的量化指標(biāo)應(yīng)包括如下合理性指標(biāo)：

最佳時(shí)間間隔均度：盡量使每門課程上課時(shí)間日間隔均勻分布，連上率或連空率最低，每次課時(shí)數(shù)不大于3，且最好上下午節(jié)次分布均勻。

最佳時(shí)間分布均度：每班級(jí)每天課程安排分布均勻，日上課時(shí)數(shù)均方差最小。

最大耦合度：從班級(jí)、教師、教室多方面盡量提高單雙周、前后節(jié)的耦合度，單雙節(jié)和前后節(jié)周課數(shù)差最小。

最小流動(dòng)值：盡量安排同班同教室， 使同班級(jí)教室轉(zhuǎn)換率最??；在教師日授課時(shí)數(shù)小于4的前提下，盡量安排同教師同天上課，使教師授課天數(shù)最少。

最大利用率：相同節(jié)次時(shí)間內(nèi)每教室容量與班級(jí)人數(shù)差最小。

四 排課設(shè)計(jì)與實(shí)現(xiàn)方法

1 排課總流程

由于高校課程存在著合班、分班、多教師、單雙周、前后節(jié)、分時(shí)段、公選、實(shí)驗(yàn)等諸多排課復(fù)雜因素，排課又要盡量滿足各種合理性原則和指標(biāo)，且不能發(fā)生任何沖突，所以自動(dòng)排課算法難度非常大。自動(dòng)排課應(yīng)根據(jù)高校課程的特性將課程分類，包括合班課、分班課、分段課、公英課、公共課、實(shí)驗(yàn)課、任選課等等，不同類別課程按相應(yīng)優(yōu)先級(jí)和不同的時(shí)間模式[3]進(jìn)行分步排課，每類課程可分別采用相對(duì)應(yīng)的自動(dòng)排課算法。各類課程數(shù)據(jù)來源、優(yōu)先次序、時(shí)間段模式原則具體如下（其中時(shí)間段分為上午一二節(jié)和三四節(jié)、下午五六節(jié)和七八節(jié)、晚上九十節(jié)）。

#61548;公英課：為4學(xué)時(shí)的大學(xué)英語課，其中一節(jié)為聽力。優(yōu)先次序：教師課多者優(yōu)先，再班級(jí)數(shù)多者，再課時(shí)多的。排課時(shí)間模式：上午一二節(jié)和三四節(jié)、下午五六節(jié)。

#61548;實(shí)驗(yàn)課：為理化實(shí)驗(yàn)、英語聽力、計(jì)算機(jī)上機(jī)等課程。優(yōu)先次序：班級(jí)數(shù)多者優(yōu)先，再課時(shí)數(shù)多的。排課時(shí)間模式：不排上午一二節(jié)。

#61548;公共課：為社科、體育等課程。優(yōu)先次序：班級(jí)數(shù)多者優(yōu)先，再課時(shí)數(shù)多的。排課時(shí)間模式：不排上午一二節(jié)和晚上九十節(jié)。

#61548;合班課：為班級(jí)數(shù)大于2的課程。優(yōu)先次序：班級(jí)數(shù)多者優(yōu)先。排課時(shí)間模式：任何時(shí)間。

#61548;教師多班課：為授課教師的課程數(shù)大于1的課程。優(yōu)先次序：課多的教師優(yōu)先，再課時(shí)多的。排課時(shí)間模式：任何時(shí)間。

#61548;教師單班課：為授課教師的課程數(shù)等于1的課程且非合班課程。優(yōu)先次序：班級(jí)課程多者優(yōu)先，再同班級(jí)課時(shí)多的。排課時(shí)間模式：任何時(shí)間。

每類課程各自按如下步驟自動(dòng)排課：排序——匹配——耦合與沖突檢測(cè)——回溯。排課設(shè)計(jì)分步分類的總體流程如下：

#61548;準(zhǔn)備排課數(shù)據(jù)：排課對(duì)象是課程，對(duì)課程進(jìn)行分班、合班、分段等處理，建立排課課程列表；排課就是排教室和時(shí)間[4]，建立班級(jí)時(shí)間課表和教室時(shí)間課表；班級(jí)和教師是排課的主體，計(jì)算教師的學(xué)時(shí)數(shù)，班級(jí)課時(shí)數(shù)等。

#61548;手工先排：對(duì)于特殊要求課程、大于6學(xué)時(shí)課程、分段課程、連上3節(jié)課程，采用手工先排。

#61548;分步分類自動(dòng)排課：按課程類型分步自動(dòng)安排不同類型的課程，不同類型課程自動(dòng)安排策略不同。每一課程自動(dòng)安排的具體步驟包括模式匹配、耦合檢測(cè)、回溯[2]重排等：

#61550;循環(huán)給出時(shí)間匹配模式，不同課程類型按不同時(shí)間段模式排課；

#61550;對(duì)每一給出的模式進(jìn)行沖突檢測(cè)和耦合檢驗(yàn)，判斷是否可用、是否存在耦合；

#61550;如可以排入，進(jìn)行課程耦合或直接排入；

#61550;如不可排入，進(jìn)行簡單回溯重排；

#61548;自動(dòng)補(bǔ)排：通過排序變更、多級(jí)回溯[6]等方法處理未排入課程。

#61548;自動(dòng)調(diào)整：全部排完后，進(jìn)行班級(jí)和教室優(yōu)化調(diào)整。

#61548;手工后排：手工排入未自動(dòng)排入的課程。

2 關(guān)鍵技術(shù)

（1）模式匹配

通過分析，排課其實(shí)并不需要非常復(fù)雜的算法，課程可排天數(shù)就5天，可排節(jié)數(shù)就5個(gè)時(shí)間段——上午一二、三四節(jié)、下午五六、七八節(jié)、晚上九十節(jié)，因此，可以按一定模式進(jìn)行組合，給出所有可排時(shí)間，下面進(jìn)行具體分析。

高校課程超過6學(xué)時(shí)的課程非常少，這樣的課程可以采用手工排。因此，在設(shè)計(jì)自動(dòng)排課時(shí)，只考慮1至6學(xué)時(shí)的課程。另一方面，高校下午七八節(jié)和晚上基本是安排公選課和課外活動(dòng)，也可手工排。因此，在設(shè)計(jì)自動(dòng)排課時(shí)，可以只考慮上午一二節(jié)、三四節(jié)和下午五六節(jié)三個(gè)時(shí)間段。

對(duì)于5、6學(xué)時(shí)的課程，合理的排課時(shí)間應(yīng)該是排三天，且間隔要合理，不應(yīng)出現(xiàn)連排三天的情況。這樣，有效的天排列組合為：124、125、134、135、145、235、245（1-5表示周一至周五），而125、145也非最佳，相當(dāng)于連排三天，也可不予考慮，于是就剩五種情況，有效的天組合數(shù)據(jù)表示如下：

rk3i[1，1]=1; rk3i[1，2]=3; rk3i[1，3]=5

rk3i[2，1]=1; rk3i[2，2]=3; rk3i[2，3]=4

rk3i[3，1]=2; rk3i[3，2]=3; rk3i[3，3]=5

rk3i[4，1]=1; rk3i[4，2]=2; rk3i[4，3]=4

rk3i[5，1]=2; rk3i[5，2]=4; rk3i[5，3]=5

對(duì)于3、4學(xué)時(shí)的課程，合理的排課時(shí)間應(yīng)該是排二天，且間隔要合理，同樣不應(yīng)存在連排二天的情況。有效的天排列組合為：13、14、15、24、25、35，其中15也非最佳，不予考慮，于是就剩五種情況，有效的天組合數(shù)據(jù)表示如下：

rk2i[1，1]=1; rk2i[1，2]=4

rk2i[2，1]=2; rk2i[2，2]=5

rk2i[3，1]=2; rk2i[3，2]=4

rk2i[4，1]=1; rk2i[4，2]=3

rk2i[5，1]=3; rk2i[5，2]=5

對(duì)于節(jié)的情況，分析5、6學(xué)時(shí)課，對(duì)于只排上午一二、三四節(jié)情況，可將其中三次課全排一二節(jié)或全排三四節(jié)的情況歸入非優(yōu)化九種組合中，則有六種情況，有效節(jié)組合數(shù)據(jù)表示如下（式中：1表示一二節(jié)、2表示三四節(jié)、依此類推）：

rk3j[1，1]=1; rk3j[1，2]=2; rk3j[1，3]=1

rk3j[2，1]=2; rk3j[2，2]=1; rk3j[2，3]=2

rk3j[3，1]=1; rk3j[3，2]=1; rk3j[3，3]=2

rk3j[4，1]=2; rk3j[4，2]=2; rk3j[4，3]=1

rk3j[5，1]=1; rk3j[5，2]=2; rk3j[5，3]=2

rk3j[6，1]=2; rk3j[6，2]=1; rk3j[6，3]=1

類似地可以有一二節(jié)和五六節(jié)組合六種情況和三四節(jié)與五六節(jié)組合六種情況，合計(jì)有十八種情況。另外還有非優(yōu)化的其它九種全天組合：

rk3k[1，1]=1; rk3k[1，2]=2; rk3k[1，3]=3

rk3k[2，1]=1; rk3k[2，2]=3; rk3k[2，3]=2

rk3k[3，1]=2; rk3k[3，2]=1; rk3k[3，3]=3

rk3k[4，1]=2; rk3k[4，2]=3; rk3k[4，3]=1

rk3k[5，1]=3; rk3k[5，2]=1; rk3k[5，3]=2

rk3k[6，1]=3; rk3k[6，2]=2; rk3k[6，3]=1

rk3k[7，1]=2; rk3k[7，2]=2; rk3k[7，3]=2

rk3k[8，1]=1; rk3k[8，2]=1; rk3k[8，3]=1

rk3k[9，1]=3; rk3k[9，2]=3; rk3k[9，3]=3

確定時(shí)間匹配模式后，自動(dòng)排5或6學(xué)時(shí)課程時(shí)，用簡單循環(huán)即可實(shí)現(xiàn)：

for ii=1 to 5

for kk=1 to 3

rk3j分別取12、13、23節(jié)組合

for jj=1 to 6

rr1=rk3i[ii，1];cc1=rk3j[jj，1]

rr2=rk3i[ii，2];cc2=rk3j[jj，2]

rr3=rk3i[ii，3];cc3=rk3j[jj，3]

next jj， next kk

for jj=1 to 9

rr1=rk3i[ii，1];cc1=rk3k[jj，1]

rr2=rk3i[ii，2];cc2=rk3k[jj，2]

rr3=rk3i[ii，3];cc3=rk3k[jj，3]

next jj， next ii

式中：rr1-rr3表示天，cc1-cc3表示節(jié)，kk表示每天上課時(shí)間段類型：

kk=1：表示只排上午一二和三四節(jié)；

kk=2：表示只排上午一二和下午五六；

kk=3：表示只排下午七八節(jié)和晚上九十節(jié)；

共有循環(huán)（3*6+9）*5=135次，即135種組合情況。但實(shí)際高校課程學(xué)時(shí)結(jié)構(gòu)中，5、6學(xué)時(shí)的課程不超百分之五。

分析3、4學(xué)時(shí)課，共有九種情況，有效節(jié)組合數(shù)據(jù)如下：

rk2j[1，1]=1; rk2j[1，2]=2

rk2j[2，1]=2; rk2j[2，2]=1

rk2j[3，1]=1; rk3j[3，2]=1

rk2j[1，1]=1; rk2j[1，2]=3

rk2j[2，1]=3; rk2j[2，2]=1

rk2j[3，1]=2; rk3j[3，2]=2

rk2j[1，1]=3; rk2j[1，2]=2

rk2j[2，1]=2; rk2j[2，2]=3

rk2j[3，1]=3; rk3j[3，2]=3

確定時(shí)間匹配模式后，自動(dòng)排3和4學(xué)時(shí)課程時(shí)，用簡單循環(huán)即可實(shí)現(xiàn)：

for ii=1 to 5

for kk=1 to 3

rk2j分別取12、13、23節(jié)組合

for jj=1 to 3

rr1=rk2i[ii，1]; cc1=rk2j[jj，1]

rr2=rk2i[ii，2]; cc2=rk2j[jj，2]

next jj， next kk， next ii

共有5*3*3=45種情況，3、4學(xué)時(shí)的課程是高校課程的主要學(xué)時(shí)結(jié)構(gòu)，一般占50%以上。

最后是1或2學(xué)時(shí)課程情況，一次上完，沒有間隔要求，只要簡單的循環(huán)即可實(shí)現(xiàn)：

for ii=1 to 5

for jj=1 to 4

rr1=ii; cc1=jj

next jj， next ii

共有20種組合情況。

通過組合模式的設(shè)計(jì)，使自動(dòng)排課滿足課程最佳時(shí)間間隔均度量化指標(biāo)要求，保證了同課程時(shí)間間隔均勻性原則。

（2）單排流程

每門自動(dòng)安排的課程對(duì)于每個(gè)時(shí)間組合模式都要進(jìn)行教師、班級(jí)、教室三方面耦合匹配與沖突檢測(cè)，以判斷是否可排入?？梢园丛摻處熓欠褚雅耪n情況分別考慮，每種情況下又分單學(xué)時(shí)課和雙學(xué)時(shí)課。

如果該教師沒排過，對(duì)于2、4、6學(xué)時(shí)課程，教師、班級(jí)、教室都不需耦合，只要判斷沖突，即判斷班級(jí)和教室排入時(shí)間是否有課，如果都沒課，排課成功。

如果該教師沒排過，對(duì)于1、3、5學(xué)時(shí)課程，需要進(jìn)行班級(jí)耦合，如果班級(jí)已排課程存在單節(jié)課，則進(jìn)行班級(jí)耦合；否則如果有教室已排課程存在單節(jié)課，則進(jìn)行教室耦合；再否則只要判斷班級(jí)和教室是否有課，如果都沒課，排課成功。

如果該教師已排過，對(duì)于2、4、6學(xué)時(shí)課程，教師、班級(jí)、教室都不需要耦合，但需計(jì)算教師每天上課的課時(shí)數(shù)，并在每天課時(shí)總數(shù)不超4和盡量多的與已排天相同的前提下選擇組合模式進(jìn)行沖突檢測(cè)。

如果該教師已排過，對(duì)于1、3、5學(xué)時(shí)課程，不但需要進(jìn)行班級(jí)耦合，還要考慮教師每天上課的課時(shí)數(shù)，在每天課時(shí)總數(shù)不超4和盡量多與已排天相同的前提下選擇組合模式。排課情況較為復(fù)雜，以5學(xué)時(shí)課程為例，自動(dòng)排課流程如下：

先計(jì)算教師每天學(xué)時(shí)數(shù)，之后可分七輪進(jìn)行，任何一輪條件滿足，排課成功，否則繼續(xù)下一輪：

第一輪：班級(jí)耦合優(yōu)先，判斷班級(jí)已排課程是否存在單節(jié)課，教師對(duì)應(yīng)三天均有課且教師每天學(xué)時(shí)小于4；

第二輪：班級(jí)耦合優(yōu)先，判斷班級(jí)已排課程是否存在單節(jié)課，教師對(duì)應(yīng)二天均有課且教師每天學(xué)時(shí)小于4；

第三輪：班級(jí)耦合優(yōu)先，判斷班級(jí)已排課程是否存在單節(jié)課，教師每天學(xué)時(shí)小于4；

第四輪：教師耦合優(yōu)先，判斷教師已排課程是否存在單節(jié)課，教師對(duì)應(yīng)三天均有課且教師每天學(xué)時(shí)小于4；

第五輪：教師耦合優(yōu)先，判斷教師已排課程是否存在單節(jié)課，教師對(duì)應(yīng)二天均有課且教師每天學(xué)時(shí)小于4；

第六輪：非耦合，判斷教師對(duì)應(yīng)三天是否均有課，且教師每天學(xué)時(shí)小于4；

第七輪：非耦合，判斷教師對(duì)應(yīng)二天是否均有課，且教師每天學(xué)時(shí)小于4。

另外，對(duì)于一教師只上一門課的單班課程情況，可采用特殊的單排流程在最后進(jìn)行，其方法是：計(jì)算班級(jí)每天學(xué)時(shí)數(shù)——按學(xué)時(shí)數(shù)排序天——選出課時(shí)最少的3或2天，且3或2天間隔大于2——進(jìn)行耦合檢測(cè)和沖突檢測(cè)，排入課程。這樣保證了每班級(jí)五天課程的均勻分布。

通過以上設(shè)計(jì)，使自動(dòng)排課滿足課程最大耦合度、教師最小流動(dòng)值、班級(jí)最佳時(shí)間分布均度等量化指標(biāo)要求，保證了所有課程的時(shí)間最佳耦合性、教師最少移動(dòng)性和班級(jí)課程總體分布均勻性原則。

（3）回溯重排

當(dāng)某一課程通過模式匹配、耦合匹配無法排入時(shí)，可對(duì)同班級(jí)已排課程進(jìn)行回溯，即把已排課程取回，進(jìn)行換位排序，之后再排未排入課程。回溯可分四級(jí)進(jìn)行：

第一級(jí)：無回溯，在第一輪自動(dòng)排課時(shí)，不進(jìn)行回溯；

第二級(jí)：單級(jí)回溯，在第二輪自動(dòng)排課時(shí)，只進(jìn)行簡單回溯，取同班級(jí)的上一門課進(jìn)行換位重排；

第三級(jí)：多級(jí)回溯，也叫補(bǔ)排，在二輪自動(dòng)排課結(jié)束后，針對(duì)未排入課程的班級(jí)進(jìn)行補(bǔ)排，取同一班級(jí)所有課程，由下向上，逐一換位重排，即：每次向上回溯一級(jí)，如回溯課與未排課都成功，則回溯成功；否則，恢復(fù)上一級(jí)原位置，向更上一級(jí)取課，進(jìn)行換位重排。

第四級(jí)：換序回溯，如多級(jí)回溯仍不成功，可對(duì)該班級(jí)所有課程全部取出重排，重排之前，進(jìn)行換序，使未排入課程排在最前面，優(yōu)先排入。

通過回溯重排，可解決排入率最大化的問題。

（4）均衡調(diào)整

當(dāng)所有課程排完后，可進(jìn)行班級(jí)均衡和教室均衡處理。

班級(jí)均衡：從班級(jí)時(shí)間表取所有已排的非合班課程—按班級(jí)、學(xué)時(shí)排序，課時(shí)多者優(yōu)先排序—計(jì)算每個(gè)班級(jí)每天課時(shí)數(shù)—查找是否存在某天無課的情況，如存在，逐一重排該班課程，直到所有天都有課。

教室均衡在不改變?nèi)魏握n程已排時(shí)間的前提下進(jìn)行。方法是：從教室時(shí)間表取所有教室（普通教室）—按容量排序—取出對(duì)應(yīng)課程，且課程按人數(shù)排序—重新排入。對(duì)于一二、五六節(jié)課程：先排可耦合的，再按序排，從耦合和容量差兩方面提高教室利用率；對(duì)于三四節(jié)課程：先排與一二節(jié)同班的，再排可耦合的，最后按序排，實(shí)現(xiàn)同班級(jí)少換教室。

通過以上均衡調(diào)整設(shè)計(jì)，使自動(dòng)排課滿足班級(jí)最佳時(shí)間分布均度、班級(jí)最小流動(dòng)值、教室最大利用率和最大耦合度等量化指標(biāo)要求，保證了班級(jí)課程總體分布均勻性、班級(jí)教室最少移動(dòng)性和容量最佳耦合性。

五 自動(dòng)排課實(shí)現(xiàn)界面與結(jié)果分析

1 實(shí)現(xiàn)界面

排課系統(tǒng)界面由四個(gè)數(shù)據(jù)窗口組成，可實(shí)現(xiàn)全自動(dòng)排課、分類自動(dòng)排課和手工排課。

2 結(jié)果分析

用以下某學(xué)期實(shí)際排課數(shù)據(jù)對(duì)自動(dòng)排課系統(tǒng)進(jìn)行測(cè)試：

#61548;38個(gè)班：包括10個(gè)專業(yè)；

#61548;240門課：其中2學(xué)時(shí)課98門，3、4學(xué)時(shí)課109門，5、6學(xué)時(shí)課5門，大于6學(xué)時(shí)課、公選課和分段課28門；

#61548;27間教室：其中普通教室19間，特殊教室8間。

測(cè)試結(jié)果是：自動(dòng)排課時(shí)間小于3秒，2門課程未自動(dòng)排入。自動(dòng)排課時(shí)間為秒級(jí)，成功率達(dá)99%以上。進(jìn)一步分析：參與自動(dòng)排課學(xué)時(shí)總數(shù)為：2*98+109*4+5*6=662課時(shí)，參與自動(dòng)排課普通教室提供學(xué)時(shí)數(shù)為：19*5*6=570課時(shí)，可見，教室利用率非常高。在另一次測(cè)試中，以15間教室安排250門課，結(jié)果是上午所有教室均排滿，沒有任何空教室。以上結(jié)果表明此自動(dòng)排課系統(tǒng)具有非常高的性能和實(shí)用價(jià)值。

參考文獻(xiàn)

[1] 許秀林，胡克瑾.基于約束滿足和遺傳算法的排課算法 [J].計(jì)算機(jī)工程，2010，36(14):281-284．

[2] 許榮泉，秦小嶼.排課問題的研究與改進(jìn)[J].軟件導(dǎo)刊，2010，09(03):66-67．

[3] 王俊生，戴云龍.基于層次分析法的自動(dòng)排課課程優(yōu)先級(jí)模型[J] .現(xiàn)代教育技術(shù)，2009，19(11):32-35．

[4] 馬紹惠等．基于資源受限的非線性約束多目標(biāo)排課模型及算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2007，28(03):520-523．

[5] 鄒躍.構(gòu)造人性化的排課算法[J].計(jì)算機(jī)教育，2007，42(06):53-55．

[6] 田嶺．大學(xué)自動(dòng)排課算法設(shè)計(jì)與實(shí)現(xiàn)[J] ．教育信息化，2006，136(13)：44-46．

Research of University Course Arrangement Multivariate Optimization Strategy and Automatic Realization Method

HU Shi-qing

(Department of Educational Technology， Shenzhen University， Shenzhen， Guangdong 518060， China)

Abstract: Through the analysis of the university course arrangement requirements， put forward a lot of reasonable course arrangement principles which is associated with course time， student class， teacher， classroom and a lot of indexes about best time interval evenness， best time distribution evenness， maximum coupling， minimum flow value， Maximum utilization. On this basis， course arrangement is classified and stages， each kind of course has its own priorities and period. By giving limited reasonable time pattern in a circular manner， checking pattern matching and multilevel backtracking， the arrangement of all kinds course is automatic realized. Finally by arrangement and adjusting， make the results more reasonable.

Keywords: university course arrangement; reasonable index; time pattern and pattern matching; coupling; backtracking

收稿日期：2011年5月7日 編輯：紅葉