排課問(wèn)題的數(shù)學(xué)模型

崔　妍，王　權(quán)，王　康，車(chē)玉軍

(沈陽(yáng)工程學(xué)院 信息學(xué)院，遼寧 沈陽(yáng) 110136)

?

排課問(wèn)題的數(shù)學(xué)模型

崔妍，王權(quán)，王康，車(chē)玉軍

(沈陽(yáng)工程學(xué)院 信息學(xué)院，遼寧 沈陽(yáng) 110136)

對(duì)適合于計(jì)算機(jī)編程的排課問(wèn)題的數(shù)學(xué)模型進(jìn)行了初步的探索，應(yīng)用抽象代數(shù)中的cartison理論和圖論中的二部圖理論對(duì)排課資源進(jìn)行合理的抽象，最終建立了兩種排課問(wèn)題的數(shù)學(xué)模型。針對(duì)高校排課系統(tǒng)的現(xiàn)狀，將學(xué)生、課程、教師、教室4個(gè)集合進(jìn)行了配對(duì)，利用層次掃描的方法，成功地解決了排課中的撞課問(wèn)題。

cartesian積；層次掃描；邊著色；二部圖

1　研究背景

隨著高校年年擴(kuò)招，學(xué)生的人數(shù)逐漸增多，而與之配套的教師﹑教室等硬件資源增長(zhǎng)相對(duì)落后。這樣的變化對(duì)教務(wù)處每學(xué)期的排課來(lái)說(shuō)變得“頭疼和難以下手”。 傳統(tǒng)的手工排課方法可以應(yīng)對(duì)班級(jí)少﹑課程變化小的情況，而辛苦排出來(lái)的課表又常出現(xiàn)這樣或那樣的問(wèn)題。例如，一個(gè)教室在同一時(shí)間分配給了上不同課程的幾個(gè)班級(jí)；一位教師在同一時(shí)間安排了兩門(mén)課等等。一錯(cuò)動(dòng)全局，既耗費(fèi)了時(shí)間又降低了工作效率。

隨著高校辦公軟件的應(yīng)用、校園網(wǎng)的建立，校內(nèi)所屬各單位的許多資料、數(shù)據(jù)都可以通過(guò)校園網(wǎng)傳送。重新設(shè)計(jì)排課系統(tǒng)不僅可以從根本上避免人力、物力資源的極大浪費(fèi)，而且還可以適應(yīng)數(shù)據(jù)動(dòng)態(tài)變化。

2　排課問(wèn)題的數(shù)學(xué)模型

2.1cartesian積

定義：設(shè)A、B為集合，用A中元素為第一元素、B中元素為第二元素構(gòu)成有序?qū)Γ羞@樣的有序?qū)M成的集合叫做A與B的cartesian積。

cartesian積的符號(hào)化為：A×B={|x∈A∧y∈B}。例如，A={a,b},B={0,1,2},則A×B={,,,,,,}。

2.2問(wèn)題的轉(zhuǎn)化

排課系統(tǒng)可歸結(jié)為班級(jí)﹑課程﹑教師﹑教室的關(guān)系問(wèn)題?，F(xiàn)設(shè)有班級(jí)集B,B={b1,b2,…,bm}，課程集C，C={c1,c2,…,cn},教師集T,T={t1,t2,…,tq},教室集R,R={r1,r2,…,rp}。其中，m為班級(jí)數(shù)，n為課程總數(shù)，q為本學(xué)期任課教師的人數(shù)，p為教室數(shù)。顯然，排課問(wèn)題成了4個(gè)集合之間的關(guān)系問(wèn)題，如圖1所示。

圖1　排課關(guān)系

班級(jí)集合和課程集合的關(guān)系如圖2所示。

圖2　班級(jí)與課程關(guān)系

于是，得出班級(jí)與課程結(jié)合后的集合：

B_C=B×C={|bi與cj滿(mǎn)足排課條件}

上式中，i=1,2,…,m;j=1,2,…,n。其中bi與cj的約束條件：

1)班級(jí)人數(shù)在25～35之間；

同理，將班級(jí)課程集與教師集結(jié)合，得

B_C_T=B_C×T={|bi,cj和

tl滿(mǎn)足排課條件}

其中，l=1,2,…,q。約束條件為

最后，將B_C_T集與教室集結(jié)合得到排課所需的集合：

B_C_T_R={(bi,cj,tl,re)|bi,cj,tl和

re和滿(mǎn)足排課條件}

其中，e=1,2,…,p。約束條件為課程是否允許合堂、教室的容量等等。

2.3模型的建立

排課表的過(guò)程是按單元將班級(jí)按順序給出適合的教室和教師。因此，從理論上來(lái)說(shuō)只要給出一門(mén)課和學(xué)習(xí)該門(mén)課的所有班級(jí)與教師的安排就可以排出整個(gè)學(xué)校所有班級(jí)的課程表。而單位課程的安排過(guò)程就是將班級(jí)集、課程集、教師集和教室集的配對(duì)再配上時(shí)間的過(guò)程。

第一步，結(jié)合班級(jí)和課程集合。在集合B中選取具體的班級(jí)組成新的班級(jí)集B′，在集合C中選取與其對(duì)應(yīng)的課程組成新的課程集C′，做B′與C′的二維cartesian積：K1=B′×C′={(bi,cj)|bi與cj滿(mǎn)足排課條件}。K1集合中的每一個(gè)元素都滿(mǎn)足排課條件，稱(chēng)為班級(jí)課程對(duì)。

第二步，把K1與對(duì)應(yīng)的教師結(jié)合，按排課條件生成三維cartesian積：K2={(bi,cj,tl)|bi，cj和tl滿(mǎn)足排課條件}。K2集合中的元素稱(chēng)為班級(jí)課程教師對(duì)。

第三步，把K2與對(duì)應(yīng)教室結(jié)合，按排課條件生成四維cartesian積：K3={(bi,cj,tl,re)|bi,cj,tl和re滿(mǎn)足排課條件}。K3集合中的元素稱(chēng)為班級(jí)課程教師教室對(duì)。這里K3中包含的元素，是排課表時(shí)所需要的數(shù)據(jù)，它同時(shí)也是最后所要生成的課表集合。

2.4算法的描述

根據(jù)B_C集中對(duì)元素(班級(jí)bi，課程cj)的約束條件，首先對(duì)集合B與集合C中滿(mǎn)足條件的元素做cartesian積，然后按系別層次掃描教師集中的元素教師tl，把適合講授課程cj的教師分配給班級(jí)bi，形成一個(gè)新的集合B_C_T。這時(shí)與tl結(jié)合送入B_C_T集合中，并且從B_C集中刪除點(diǎn)對(duì)。這樣B_C集合中的點(diǎn)對(duì)足漸減少，當(dāng)B_C中所有的點(diǎn)對(duì)都分配了教師，B_C集為空，此時(shí)一次層次掃描結(jié)束。同理可對(duì)B_C_T集分配教室得集合B_C_T_R。

最后將B_C_T_R集與上課時(shí)間做Cartison積。設(shè)每周有5個(gè)工作日，每天最多可以安排5個(gè)單元的課程(盡可能排在1～3單元)。當(dāng)B_C_T_R集中的所有元素都安排了上課時(shí)間，則生成最終的課程表。算法對(duì)應(yīng)的流程如圖3所示。在排課的整個(gè)過(guò)程中，始終伴隨著元素的層次掃描和元素從舊集合到新集合的遷移。這樣的遷移保證了所有元素都會(huì)被使用且只使用一次。因此避免了排課過(guò)程中的撞課問(wèn)題。

2.5圖論模型的計(jì)算機(jī)算法

在這里給出匹配問(wèn)題的算法和目前較為流行的指派問(wèn)題的c++源程序，以便為日后的編程工作提供參考。

根據(jù)上述理論,設(shè)G=,V={v1,v2,…,vn},E={e1n,e2n,…,em}，記N(vi)表示與v1相鄰的結(jié)點(diǎn)集，λ(vi)=c表示vi所著顏色為c，得到匹配問(wèn)題的算法如下：

step1：任給初始匹配M；

step 2：若M飽和，則V1結(jié)束,否則轉(zhuǎn)step 3；

step 3：在V1中找一非M飽和點(diǎn)x，置S={x},T=φ；

step 4：若N(S)=T，則停止，否則任選一點(diǎn)y∈N(S)-T；step 5：若y為M飽和點(diǎn)，轉(zhuǎn)step 6，否則作求一條從x到y(tǒng)的M可增廣路P，置M=M⊕P，轉(zhuǎn)step2；

step 6：由于y是M飽和點(diǎn)，故M中有一邊{y,u}，置S=S∪{u}，T=T∪{y}，轉(zhuǎn)step4。

匹配問(wèn)題的算法流程如圖4所示。

3　結(jié)　論

課表的安排是排課問(wèn)題的難點(diǎn)。它不僅要考慮到教室和教師的沖突問(wèn)題，還要考慮到分段上課、單雙周上課的資源合理利用問(wèn)題。針對(duì)這一問(wèn)

圖3　算法流程

圖4　匹配問(wèn)題的算法流程

題，專(zhuān)門(mén)對(duì)原有的圖論和運(yùn)籌中的模型進(jìn)行了改進(jìn)，通過(guò)實(shí)例演示，無(wú)論從資源利用率、學(xué)生上下課轉(zhuǎn)移量，還是排課速度上都取得了滿(mǎn)意的效果。按此算法，軟件一旦開(kāi)發(fā)成功，可同時(shí)解決各高校以課程安排為中心的選課系統(tǒng)、成績(jī)管理、教學(xué)檢查等教務(wù)管理信息化建設(shè)中的種種問(wèn)題。

[1]GoseE,JohnsonbaughR,JostS.Patternrecognitionandimageanalysis[M].Berlin：Springer，2013.

[2]王念橋，姚四改.基于改進(jìn)粒子群優(yōu)化算法的排課問(wèn)題[J].計(jì)算機(jī)應(yīng)用，2013，33(1):207-210.

[3]柯廣利.基于優(yōu)先選擇算法的中職排課系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].常州工學(xué)院學(xué)報(bào),2014,27(1):43-46.

[4]王楊,丁向東,郭敏.基于提高學(xué)生學(xué)習(xí)效率的排課模型[J].科技信息,2014(2):54-55.

[5]王仲華,盧嬌麗.圖論在高校排課問(wèn)題中的應(yīng)用研究[J].太原師范學(xué)院學(xué)報(bào)：自然科學(xué)版,2010,9(1):39-42.

[6]王維宏.高校學(xué)分制教學(xué)管理體制下課表編排探析[J].沈陽(yáng)工程學(xué)院學(xué)報(bào):社會(huì)科學(xué)版,2006,2(4):540-541.

(責(zé)任編輯張凱校對(duì)佟金鍇魏靜敏)

MathematicalModelsforCourseScheduling

CUIYan,WANGQuan,WANGKang,CHEYu-jun

(SchoolofInformationEngineering,ShenyangInstituteofEngineering,Shenyang110136,LiaoningProvince)

Twomathematicmodelsforthecoursesarrangement,whichiseasilyprogrammedbycomputer,wereestablishedwithcartisontheoryandbipartitegraphtheory.Themodelssolvedtheschooltimetableconflictbyhierarchicalscanningthematched4setsofthestudents,courses,teachersandclassrooms.

cartesianproduct;levelscan;edgecoloring;bipartitegraph

2015-12-30

遼寧省自然科學(xué)基金項(xiàng)目(2015020020)；遼寧省社會(huì)科學(xué)規(guī)劃基金項(xiàng)目(L15BGL035)；遼寧省教育廳一般項(xiàng)目(L2014514)；沈陽(yáng)工程學(xué)院博士啟動(dòng)項(xiàng)目(LGBS-1401)；沈陽(yáng)工程學(xué)院2014年大學(xué)生創(chuàng)新項(xiàng)目(201411632068)

崔妍(1982-)，女，遼寧沈陽(yáng)人，講師,博士,主要從事智能計(jì)算方法方面的研究。

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

TP301.6

A

1673-1603(2016)03-0276-03