排課問題的數(shù)學(xué)模型研究

陳 輝，何 軍

(安徽商貿(mào)職業(yè)技術(shù)學(xué)院 教務(wù)處，安徽 蕪湖 241002)

?

排課問題的數(shù)學(xué)模型研究

陳 輝，何 軍

(安徽商貿(mào)職業(yè)技術(shù)學(xué)院 教務(wù)處，安徽 蕪湖 241002)

通過對排課問題中課程、班級、教師和場地的約束條件進(jìn)行數(shù)學(xué)抽象，將排課方案的優(yōu)化表示為場地利用情況和課時(shí)安排合理性的評價(jià)，給出了一個(gè)較為精煉的排課問題數(shù)學(xué)模型，在一定的問題規(guī)模下，得到了較好的排課效果。在此基礎(chǔ)上，針對高校排課實(shí)際應(yīng)用場景，基于貪心算法給出了排課問題的一種高效的近似求解方案，為基于排課的教務(wù)管理信息系統(tǒng)的構(gòu)建提供了參考借鑒。

排課問題；排課算法；整數(shù)規(guī)劃模型；貪婪算法；Lingo

排課涉及班級、教師、教學(xué)場地和各種教學(xué)資源的調(diào)配，是教學(xué)管理中復(fù)雜性最高、難度最大的問題。人們一直都在嘗試?yán)糜?jì)算機(jī)信息手段來實(shí)現(xiàn)自動排課。早在1962年Gotlieb即在其著作“The Construction of Class-Teacher Time Tables”中研究了排課問題的數(shù)學(xué)模型[1]，并將其視為組合規(guī)劃問題進(jìn)行相應(yīng)地深入研究。S.Even等在1976年完成了運(yùn)籌學(xué)中時(shí)間表問題(Timetable Problem,TTP)的復(fù)雜度分析研究，并首次證明排課問題作為時(shí)間表問題的具體應(yīng)用，是“多項(xiàng)式復(fù)雜程度的非確定性問題(NP完全問題)”[2]。隨著90年代計(jì)算機(jī)技術(shù)的逐漸普及，課表的計(jì)算機(jī)編排開始大量出現(xiàn)，但由于問題本身的復(fù)雜性，在高校這樣復(fù)雜的教學(xué)場景中，計(jì)算機(jī)通常只是作為手工排課的輔助手段。直到Paecher等通過對時(shí)空排列和布局尋找，找到了處理時(shí)間表問題的一些方法[3]。近年來，隨著遺傳算法、模擬退火算法、蟻群算法等智能算法的興起，國內(nèi)學(xué)者對排課問題投入了大量的研究[4-10]，在取得豐富成果的同時(shí)，也存在著普遍的問題。以遺傳算法為例，雖然經(jīng)過多次迭代可以獲得較好的解，但在實(shí)際應(yīng)用過程中由于過多的約束條件，可能會出現(xiàn)兩個(gè)較好的父代經(jīng)過交叉后產(chǎn)生較差的子代，導(dǎo)致其對可行解的搜索能力較貪婪算法并沒有突出的優(yōu)勢。從現(xiàn)實(shí)意義上說，排課問題首先關(guān)注的是在合理的時(shí)間內(nèi)快速有效地給出可行解，然后盡可能地滿足一系列特定條件。智能算法在處理諸如排課問題這類約束條件很多的強(qiáng)約束規(guī)劃問題方面，還有待進(jìn)一步研究。

通過對排課問題進(jìn)行數(shù)學(xué)抽象，采取適當(dāng)?shù)募记桑瑢?shí)現(xiàn)了易于求解的排課問題數(shù)學(xué)模型的構(gòu)建。并在此基礎(chǔ)上，給出了關(guān)于排課問題的一種高效的貪婪搜索算法。

1 排課問題的數(shù)學(xué)模型

排課問題需要在滿足資源獨(dú)占性的硬性約束條件(時(shí)間、教師、教室不會沖突)下，盡可能滿足特定的(排課時(shí)間均勻、課程優(yōu)先時(shí)間段等)軟性約束條件的情況下，使得教學(xué)資源盡可能充分使用。

1.1 變量表示

1)教學(xué)課程元集合M：其主要包含課程名稱、授課教師、周學(xué)時(shí)和班級人數(shù)等，設(shè)有m個(gè)教學(xué)課程元。典型的教學(xué)課程元和教學(xué)場所元，具體如表1所示。

表1 教學(xué)課程元示例

其中，Mi={M1,…,Mi,…,Mm}為所有課程構(gòu)成的集合，共有m條記錄，并且按課程上課班級|c(Mi)|=|βs|人數(shù)從大到小排列；函數(shù)c(·)用來映射課程元素Mi所指定的班級為βs；函數(shù)h(·)用來映射課程元素Mi所指定的教師為αk。Wi表示課程Mi對授課場所的要求標(biāo)準(zhǔn)，這種標(biāo)準(zhǔn)已經(jīng)按從低到高排序，比如，W1：普通教室

2)教學(xué)場所元集合N：其主要包含校區(qū)名稱、樓宇名稱、教室名稱、教室類型和教室可容納人數(shù)(多少個(gè)座位或多少臺機(jī)位等)，這里設(shè)有n個(gè)教學(xué)場所元，N={Nj|j=1,2,…,n}。

3)授課時(shí)間元集合T：其主要定義的是教學(xué)時(shí)間段，按照現(xiàn)有模式每天分為上午1-2節(jié)、上午3-4節(jié)、下午1-2節(jié)、下午3-4節(jié)和晚上共計(jì)5個(gè)時(shí)間段，并按每周的時(shí)間順序編碼，每周共有25個(gè)授課時(shí)間元。為了方便排課算法的求解，將單雙周合并計(jì)算，共50條記錄，T={Tt|t=1,2,…,50}。比如T1表示單周周一上午1-2節(jié)課，T5表示單周周一晚上9-10節(jié)課，T30表示單周周五晚上9-10節(jié)課，T32表示雙周周一上午3-4節(jié)課等等，依次類推。這樣做雖然可能會在教學(xué)資源緊缺的情況下導(dǎo)致某門課程在單雙周的上課地點(diǎn)與時(shí)間不同，但卻形成了極為靈活的排課方式，排課模型的可行解空間得到了極大的推廣，只要教學(xué)資源沒有出現(xiàn)過于匱乏的情況，一般都能成功排課。在用窮舉貪婪方式搜索排課方式的時(shí)候，也可以在條件允許的情況下優(yōu)先將單雙周上課安排在相同的地點(diǎn)與時(shí)間上。

6)根據(jù)以上表述，可以將課程Mi的排課結(jié)果Ri?N×T表示為教學(xué)場所和時(shí)間段之間的有序元素對(Nj,Tt)構(gòu)成的集合，即課程Mi被安排在Nj教室在Tt時(shí)間段進(jìn)行兩個(gè)課時(shí)的教學(xué)。排課結(jié)果Ri由若干個(gè)有序元素對(Nj,Tt)構(gòu)成。

7)使用rijt表示排課決策變量，其含義為

由此，可以將排課結(jié)果表示為

Ri={(j,t)|xijt≠0}，i=1,2,…,m

(1)

1.2 約束條件

1)硬約束條件

①課程Mi的課時(shí)總量約束

(2)

其中，i=1,2,…m。

②場地容量約束

?(j,t)∈Ri，|Nj|≥|c(Mi)|

(3)

其中，|Nj|和|c(Mi)|分別用來表示教室和班級的學(xué)生容量，i=1,2,…,m。

③資源時(shí)間獨(dú)占

場地時(shí)間獨(dú)占可以表示為：

(4)

對任意的時(shí)間段和場地，j=1,2,…,n，t=1,2,…,50，保證場地在所有課程排課中不會產(chǎn)生時(shí)間沖突。

教師時(shí)間獨(dú)占可以表示為：

(5)

對任意時(shí)間段t=1,2,…,50，保障全院各教師(αk是列向量)所在的各行，在所有的排課結(jié)果中不會出現(xiàn)兩次(求和小于1)，即保證教師在排課中不會出現(xiàn)時(shí)間沖突。

班級時(shí)間獨(dú)占可以表示為：

(6)

對任意時(shí)間段t=1,2,…,50，保障全院各班級(βs是列向量)所在的各行，在所有的排課結(jié)果中不會出現(xiàn)兩次(求和小于1)，即保證班級在排課中不會出現(xiàn)時(shí)間沖突。

④教室類型要求

?(j,t)∈Ri，L(Nj)≥Wi

(7)

其中，對任意課程Mi，i=1,2,…,m，排給他的教室Nj的類型標(biāo)準(zhǔn)L(Nj)大于課程Mi的上課要求Wi。

2)軟約束條件

對教學(xué)課程元集合M和教學(xué)場所元集合N的自身限制條件和要求視為多維約束，例如某老師要求周三上午3-4節(jié)(授課時(shí)間元集合T)在篤學(xué)樓207(教學(xué)場所元集合N)上《計(jì)算機(jī)網(wǎng)絡(luò)基礎(chǔ)》課(教學(xué)課程元集合M)，在算法求解的過程中可以將其定義為教學(xué)課程Mi的子屬性si，并用編碼形式標(biāo)記軟約束條件。因?yàn)檐浖s束最終未必一定需要實(shí)現(xiàn)，所以從原則上只要Ri盡可能滿足Si即可，i=1,2,…,m。

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

任何滿足上述約束條件的可行解都可以對于一種排課方法、不同排課方法的優(yōu)劣通過使用目標(biāo)函數(shù)來評價(jià)。在模型求解的過程中，盡可能優(yōu)化的解會對排課方法(可行解)進(jìn)行優(yōu)化。這里考察的目標(biāo)函數(shù)由兩部分構(gòu)成。

①均勻排課

相同課程的排課結(jié)果Ri在時(shí)間元集合T中盡可能分散，即方差

(8)

盡可能大。

②可利用資源

通常使剩余場地的容量總和盡可能大的可行解，視為最優(yōu)解[11]。換言之，最優(yōu)解是使未分配的場地容量之和最大的可行解

(9)

其中，|Nj|用來表示教室的學(xué)生容量。

綜上，排課問題可以表示為下述整數(shù)線性約束的多目標(biāo)規(guī)劃模型：

(10)

其中，j=1,2,…,n,t=1,2,…,50，i=1,2,…,m。

1.3 優(yōu)化模型的求解

對于問題規(guī)模較小的，比如教室、班級和教師數(shù)量在100以下的排課問題，上述建立的整數(shù)規(guī)劃模型，在軟約束條件適當(dāng)簡化的情況下，可以直接使用Lingo求解。在配置為CPU i7 4790，內(nèi)存32GB的PC下，使用Lingo 11，得到部分計(jì)算結(jié)果如表2所示。

表2 排課優(yōu)化模型的求解

對于更大規(guī)模的排課問題，在數(shù)學(xué)表述和Lingo語言的模型構(gòu)建上并沒有太多差異，但由于變量個(gè)數(shù)隨著問題規(guī)模大幅度上升(教室、班級和教師數(shù)量大于100時(shí)，Lingo顯示的變量總數(shù)在百萬以上)，很難在有限的時(shí)間內(nèi)給出模型的解。

2 貪心排課算法的描述

為解決這種困難，采用兩次貪心選擇：先在M中選未處理且上課人數(shù)最大的課程，再在N中選min{場地容量：場地容量≥上課人數(shù)}且符合課程要求(硬、軟約束條件)的教學(xué)場地，這樣可以使得教學(xué)資源的利用盡可能地高效，剩余場地的容量總和盡可能大。在滿足貪心搜索的退出條件：剩余周學(xué)時(shí)為0，則教學(xué)資源尚有余量時(shí)，認(rèn)為在盡可能優(yōu)化的前提下找到了可行解，即排課成功。

2.1 輔助空間

1)教師資源獨(dú)立標(biāo)記二維數(shù)組HT=H×T，表示教師和50個(gè)授課時(shí)間元的笛卡爾乘積，用來標(biāo)記教師是否在對應(yīng)時(shí)間段被排課占用；

2)班級資源獨(dú)立標(biāo)記二維數(shù)組CT=C×T，表示教學(xué)班級和50個(gè)授課時(shí)間元的笛卡爾乘積，來標(biāo)記班級是否在對應(yīng)時(shí)間段被排課占用；

3)場地資源獨(dú)立標(biāo)記二維數(shù)組NT=N×T，表示n個(gè)教學(xué)場所和50個(gè)授課時(shí)間元，若NT(j,t)=1，則表示N中j教室在T中Tt時(shí)間段被排課。

2.2 算法描述

1)數(shù)據(jù)預(yù)處理

①將教學(xué)課程元集合M按照班級人數(shù)進(jìn)行降序排列(從大到小)；

②將教學(xué)場所元集合N按照教室可容納人數(shù)進(jìn)行升序排列(從小到大)。

2)處理手工排課

一些特殊的情況，可以事先將特定需求的課程進(jìn)行手工排課，即課程Mi的排課結(jié)果Ri在排課初始時(shí)就不是空集。

對M中元素Mi做遍歷操作：\課程元素循環(huán)開始

判斷Ri是否為空，若Ri不空，則判斷下式是否成立。

(11)

若返回值為真，則報(bào)錯(cuò)信息“手工排課課程課Mi時(shí)總量有誤！”，否則執(zhí)行下述操作：

對Ri的所有排課結(jié)果元素(j,t)循環(huán)：\Ri排課結(jié)果元素(j,t)循環(huán)開始

若HT(h(Mi)t)=1，則報(bào)錯(cuò)信息“手工排課課程Mi在Tt時(shí)間段的任課教師h(Mi)沖突！”，否則標(biāo)記HT(h(Mi)t)=1；

若CT(c(Mi),t)=1，則報(bào)錯(cuò)信息“手工排課課程Mi在Tt時(shí)間段的班級c(Mi)沖突！”，否則標(biāo)記CT(c(Mi)t=1；

若NT(j,t)=1，則報(bào)錯(cuò)信息“手工排課課程Mi在Tt時(shí)間段的場地Nj沖突！”，否則標(biāo)記NT(j,t)=1．

\Ri排課結(jié)果元素(j,t)循環(huán)結(jié)束

\課程元素循環(huán)結(jié)束

手工排課成功。

3)貪心算法排課

接第一步1)，重新對M中元素Mi做遍歷操作：\課程元素循環(huán)開始

對Xi進(jìn)行判斷，若Xi=0，則表示課程Mi已經(jīng)完成排課，返回循環(huán)；

Xi>0,則：

對T中元素Tt做遍歷操作和任意容量大于Mi上課人數(shù)的且類型達(dá)到Mi要求的場地Nj循環(huán)：\時(shí)間與場地循環(huán)開始

如果時(shí)間段Tt與場地Nj滿足Si要求且與Ri中已有的時(shí)間間隔大于5(間隔1天)，則執(zhí)行：

若HT(h(Mi)t)、CT(c(Mi)t)、NT(j,t)取值都為0：

設(shè)置HT(h(Mi),t)=1，CT(c(Mi),t)=1，NT(j,t)=1；

并從課時(shí)數(shù)總量中減去2，即Xi=Xi-2；

并將排課結(jié)果添加到課程Mi中，即Ri=Ri∪{(j,t)}

\時(shí)間與場地循環(huán)結(jié)束

如果時(shí)間與場地循環(huán)結(jié)束時(shí)，Ri未能擴(kuò)充，Xi沒有減小，表示Mi課程本輪排課失敗，則舍棄(j,t)；滿足Si要求的判斷，重新開始本輪時(shí)間與場地循環(huán)。\課程元素循環(huán)結(jié)束

根據(jù)實(shí)際情況，只要教學(xué)資源沒有出現(xiàn)過于匱乏的情況，一般循環(huán)4-6次就能成功完成排課。但若仍有Xi>0的課程，則表示排課失敗，需要根據(jù)教師或教學(xué)場地重新調(diào)整課程元素重新開始。

3 結(jié) 論

首先將高校排課問題描述為整數(shù)線性約束的多目標(biāo)優(yōu)化模型，給出了排課問題的完整數(shù)學(xué)描述，在一定復(fù)雜度規(guī)模內(nèi)得到了較好的效果，得到了排課問題的一種完整、精煉的數(shù)學(xué)抽象，為排課問題的求解算法研究提供了理論基礎(chǔ)；同時(shí)，給出了一種基于貪心算法的排課問題近似求解方案，可以快速有效地得到較好的排課結(jié)果，為教務(wù)排課管理信息系統(tǒng)建設(shè)提供了借鑒參考。

[1]Gotlieb CC.The construction of class-teacher timetables[J].Proc.IFIP Congress ，1962： 73-77.

[2]S.Even ， A.Itai ， A.Shamir.On the complexity of timetabling and multicommodity flow problems[J].SIAM Journal of Computation,1976(4)：691-703.

[3]B.Paechter,H.Luchian,A.Cumming,et al.Two solutions to the general timetable problem using evolutionary methods[C]// IEEE Conference on Evolutionary Computation,Piscataway,NJ,Orlando,1994,1:300-305.

[4]Edmund K.Burke,Dave Elliman,and Rupert F.Weare.A Hybrid Genetic Algorithm for Highly Constrained Timetabling Problems[C]//In Proceedings of the 6th International Conference on Genetic Algorithms,Larry J.Eshelman (Ed.).Morgan Kaufmann Publishers Inc.,San Francisco,CA,USA,1995: 605-610.

[5]Wilke P.,Grobner M.,Oster,N.A hybrid genetic algorithm for school timetabling[J].In: McKay B.,Slaney J.(eds) AI 2002: Advances in Artificial Intelligence.AI 2002.Lecture Notes in Computer Science,2002,2557:455-464.

[6]崔 妍,王 權(quán),王 康,等.排課問題的數(shù)學(xué)模型[J].沈陽工程學(xué)院學(xué)報(bào)：自然科學(xué)版,2016,12(03):276-278，288.

[7]李建麗.基于遺傳算法的排課系統(tǒng)研究[D].黑龍江:哈爾濱工程大學(xué),2009.

[8]王 茹.基于遺傳算法的排課系統(tǒng)關(guān)鍵技術(shù)研究與實(shí)現(xiàn)[D].吉林:吉林大學(xué),2013.

[9]趙惠怡.基于蟻群算法的排課問題的研究[D].遼寧:大連海事大學(xué),2007.

[10]李玉吉,盧才武,劉 冠.蟻群遺傳算法在高校智能排課系統(tǒng)中的應(yīng)用[J].現(xiàn)代電子技術(shù),2010(14):121-123.

[11]朱鳳娟，王 微，趙亞莉.廣義強(qiáng)向量擬均衡問題組的解的存在性[J].渤海大學(xué)學(xué)報(bào)：自然科學(xué)版，2015，36(2)：101-105.

(責(zé)任編輯魏靜敏校對張凱)

MathematicalModelResearchonCourseScheduling

CHEN Hui，HE Jun

(Office of Teaching affairs ，Anhui Business College of Vocational Technology,Wuhu 241002,Anhui Province)

The constraints of courses,classes and teachers are given by mathematical abstraction in course scheduling problems,which will optimize the course scheduling scheme to provide more remaining teaching venues and make course scheduling more reasonable,that is a more refined mathematical model of timetabling problem.As the scale of the problem is not too large,the model achieves effective results.On this basis,according to the actual application of University timetabling scene,an efficient approximate solution was proposed to solve the scheduling problem based on the greedy algorithm,which provided reference for the educational management information system.

Course scheduling problem; Scheduling algorithm; Integer programming model; Greedy algorithm; Lingo

2017-03-20

安徽省高等教育振興計(jì)劃項(xiàng)目(2014zdjy168)；安徽省質(zhì)量工程項(xiàng)目(2015mooc154)

陳 輝(1983-)，男，安徽淮南人，講師，碩士。

10.13888/j.cnki.jsie(ns).2017.03.014

TP301.6;O221

： A

： 1673-1603(2017)03-0273-05