圖論在高校排課中的應(yīng)用

黎貴云

[摘 要]課程表的編制是高校教務(wù)管理中非常重要與關(guān)鍵的一個(gè)工作。排課問(wèn)題需要在滿足一定的約束情況下，制定出相應(yīng)的課程的時(shí)間安排及地點(diǎn)安排，是一種非常典型的組合優(yōu)化問(wèn)題。本文從某職業(yè)技術(shù)學(xué)院實(shí)際情況出發(fā)，提出了一種比較適合高校教學(xué)實(shí)際課程的比較通用的模型，并且針對(duì)這個(gè)模型給出一種實(shí)用的算法流程，并將這種算法應(yīng)用到某職業(yè)技術(shù)學(xué)院，通過(guò)排課的相關(guān)實(shí)驗(yàn)驗(yàn)證了算法的有效性。

[關(guān)鍵詞]排課 組合優(yōu)化 圖論

中圖分類號(hào)：G423.07 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-914X（2016）10-0205-01

1 概述

隨著計(jì)算機(jī)相關(guān)技術(shù)及網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，職業(yè)技術(shù)學(xué)院的網(wǎng)絡(luò)辦公越來(lái)越受到重視[1]。學(xué)校開展了大量的校園網(wǎng)信息化建設(shè)，但是目前學(xué)校的排課系統(tǒng)相對(duì)比較落后，主要的原因在于由于學(xué)校的規(guī)模大小、約束的復(fù)雜程度不同，而且學(xué)校發(fā)展過(guò)程中存在很多的其他因素等的影響導(dǎo)致[2-3]。在排課的過(guò)程中，一方面要保證學(xué)校學(xué)生、教師與教室之間不能夠產(chǎn)生相應(yīng)的矛盾，同時(shí)還需要滿足學(xué)校目前的各種資源的實(shí)際使用情況的相關(guān)約束。

本文主要是從圖論的角度針對(duì)某職業(yè)技術(shù)學(xué)院的排課進(jìn)行研究與分析。

2 問(wèn)題提出

近些來(lái)年，由于某職業(yè)技術(shù)學(xué)院的招生規(guī)模在不斷的擴(kuò)大，學(xué)生的人數(shù)是在不斷的增加。在學(xué)生人數(shù)不斷增加的情況下，學(xué)校的教師、教室、實(shí)驗(yàn)室的機(jī)房等相關(guān)硬件資源增加相對(duì)來(lái)說(shuō)比較的落后。一些專業(yè)的課程不但沒(méi)有減少而且還在不斷增加，一些專業(yè)課程還在不斷的發(fā)生變化。這些不確定因素一定程度上增加了教務(wù)排課方面的負(fù)擔(dān)。對(duì)于傳統(tǒng)的手工排課來(lái)說(shuō)，過(guò)去的學(xué)生人數(shù)比較少、課程的變化情況比較小，針對(duì)這種情況還會(huì)出現(xiàn)一些問(wèn)題。

通過(guò)采用自動(dòng)化的計(jì)算機(jī)排課系統(tǒng)能夠從根本上解決人力、物力等方面的資源合理利用，還能夠根據(jù)實(shí)際的數(shù)據(jù)變化情況動(dòng)態(tài)產(chǎn)生變化。通過(guò)采用圖論算法能夠解決一些排課方面的問(wèn)題，但是基于圖論算法的排課系統(tǒng)也會(huì)存在一些不足之處。例如一些圖論算法中將教師和班級(jí)作為二部圖來(lái)進(jìn)行計(jì)算，這種模型在實(shí)際的應(yīng)用過(guò)程中忽略了高校教學(xué)中班級(jí)可能不固定的情況，還有一些模型沒(méi)有考慮到學(xué)生的實(shí)際情況，將一門課程的兩次課安排在同一天內(nèi)，直接會(huì)增加學(xué)生的負(fù)擔(dān)。

3 模型建立

在高校的教學(xué)管理過(guò)程中有兩個(gè)比較明顯的特點(diǎn)，第一個(gè)是教學(xué)的班級(jí)是不固定的，第二是學(xué)校每學(xué)期會(huì)開設(shè)一些公共課或者必修課，學(xué)生能夠根據(jù)自己的興趣愛好來(lái)選擇一些課程，基于這兩個(gè)特點(diǎn)，我們能夠把高校的排課轉(zhuǎn)換成圖論理論模型進(jìn)行計(jì)算。

在高校的教學(xué)過(guò)程中，大學(xué)的課程是以周為計(jì)算，將高校排課問(wèn)題抽象成基本的圖論模型G（V，E）：

（1）其中頂點(diǎn)集用來(lái)表示教師與課程兩部分組成，集合T={T1，T2，T3，…，Tn}用來(lái)表示不同的教師集合，集合C={ C1，C 2，C 3，…，C n }表示課程的集合。

（2）在圖G（V，E）的相關(guān)邊集主要是由上面的兩個(gè)頂點(diǎn)之間的連線組成。比如集合T={T1，T2，T3，…，Tn}中的一位老師教授集合C={ C1，C 2，C 3，…，C n }中的一節(jié)課，那么就將這兩個(gè)頂點(diǎn)用實(shí)線連接起來(lái)?；谶@個(gè)流程，高校排課問(wèn)題就能夠轉(zhuǎn)變成一種偶圖。

利用軟色理論中的相關(guān)邊著色理論來(lái)進(jìn)行時(shí)間段的分配：在圖G（V，E）中可以用例K中不同的顏色來(lái)進(jìn)行邊的軟色處理，一種顏色就對(duì)應(yīng)一個(gè)上課時(shí)間段?；谶@個(gè)流程，就可以得到一張具有K個(gè)授課時(shí)間段的課表信息。在這個(gè)課表信息中，教師、課程不會(huì)發(fā)生相關(guān)的沖突問(wèn)題。比如在圖1中，教師T1每周有三次課C1，C2，C3，教師T2每周有一次課C4，教師T3每周有兩次課C5，C6。

4 算法設(shè)計(jì)

在圖論排課算法中，采用邊軟色的相關(guān)理論，通過(guò)構(gòu)造相應(yīng)的方法，對(duì)滿足相關(guān)沖突與約束的邊進(jìn)行軟色處理，在所有能夠染色的顏色中尋找一種與所有實(shí)線課程的頂點(diǎn)之間的權(quán)重最接近的顏色進(jìn)行軟色即可。最終根據(jù)權(quán)重的顏色集合進(jìn)行排序處理，對(duì)于權(quán)重大的進(jìn)行優(yōu)先排列，最后得到一張課表。

根據(jù)職業(yè)技術(shù)學(xué)院的教學(xué)大綱，畫出相應(yīng)的圖G（V，E）。假設(shè)在圖G（V，E）中目前已經(jīng)有了n條實(shí)線邊，根據(jù)課程的重要程度將其權(quán)重值設(shè)置為；圖中的頂點(diǎn)的最大度設(shè)置為；教室的總的數(shù)量信息設(shè)置為L(zhǎng)個(gè)。按照下面的算法進(jìn)行計(jì)算與排課：

（1）作相應(yīng)的圖G=（C，E），用來(lái)表示相應(yīng)的軟色的實(shí)線邊數(shù)的集合，用E里表示沒(méi)有軟色的實(shí)線邊的集合。取相應(yīng)的整數(shù)m（），構(gòu)造數(shù)據(jù)來(lái)表示m中不同的顏色，另外用來(lái)表示顏色中邊的個(gè)數(shù)。其中在初始化的時(shí)候設(shè)置為0。用表示這些顏色的相應(yīng)的實(shí)線邊的集合，初始化的值還是設(shè)置為。根據(jù)實(shí)際所需要的課程的情況及教室的實(shí)際的數(shù)量信息來(lái)選擇適當(dāng)?shù)膮?shù)L（）信息。

（2）設(shè)置相應(yīng)的構(gòu)造方法為布爾型，主要是用來(lái)表示軟色為k的所有實(shí)線的邊中是否含有與實(shí)線邊e進(jìn)行連接的。如果有邊e那么就不能繼續(xù)進(jìn)行軟色為k，返回false值；如果沒(méi)有那么需要進(jìn)行相應(yīng)的軟色處理k，返回true值。這種方法需要進(jìn)行相應(yīng)的遍歷處理E，時(shí)間復(fù)雜度為。

（3）對(duì)于在E中實(shí)線的相應(yīng)的實(shí)線邊e，如果發(fā)生，那么就需要遍歷相應(yīng)的顏色值，調(diào)用方法，找出其中返回值為true的所有的顏色集合K，在所有的能夠軟色顏色中找到一種與實(shí)線的邊e的所有課程的頂點(diǎn)的權(quán)重最為接近的顏色，將這條實(shí)線邊e軟色為。同時(shí)，在這個(gè)算法過(guò)程中運(yùn)行，，，，。通過(guò)這個(gè)步驟來(lái)遍歷所有的集合E中的實(shí)線邊，并且對(duì)這些實(shí)線邊的遍歷的顏色值，時(shí)間上的復(fù)雜度為。如果在遍歷的過(guò)程中沒(méi)有找到合適的顏色來(lái)進(jìn)行軟色，那么就不會(huì)有合適的返回值true，就表示沒(méi)有找到合適的顏色值對(duì)這條邊進(jìn)行軟色，那么就需要選取另外的整數(shù)m，重新返回到（1）。如果在選取一定的數(shù)目信息之后，仍然沒(méi)有合適的顏色，那么就需要退出這個(gè)程序。

（4）如果發(fā)生，那么需要計(jì)算返回軟色的結(jié)果E，，。否則就需要返回到步驟（3）中繼續(xù)進(jìn)行計(jì)算。

5 系統(tǒng)實(shí)現(xiàn)

采用目前留下的編程技術(shù)JSP語(yǔ)言實(shí)現(xiàn)某職業(yè)學(xué)院的高校排課系統(tǒng)的相關(guān)開發(fā)。用戶操作起來(lái)比較方便，界面比較友好，功能完善性比較好，對(duì)系統(tǒng)的支持性要求很低。根據(jù)輸入或者采集的初始數(shù)據(jù)信息使用上面的圖論排序算法進(jìn)行高校排課，排課生成的課程表可以按照班級(jí)、教師、教室、時(shí)間等多種關(guān)鍵字進(jìn)行查詢。

根據(jù)開發(fā)的這個(gè)系統(tǒng)，能夠?qū)⒙殬I(yè)技術(shù)學(xué)院2015、2016級(jí)的四個(gè)學(xué)期的課程進(jìn)行重新的排列，生成新的課表。通過(guò)將新生成的課表與原來(lái)已經(jīng)排好的課表之間進(jìn)行比較。比較的對(duì)象包括同一種課程上課之間的間隔信息、學(xué)生主要課程每周上課的天數(shù)、學(xué)生平均每天的上課的節(jié)數(shù)安排以及相關(guān)的課程之間的沖突等。通過(guò)相應(yīng)的測(cè)試能夠發(fā)現(xiàn)，在這個(gè)系統(tǒng)中同一種課程上課之間的間隔信息、學(xué)生主要課程每周上課的天數(shù)、學(xué)生平均每天的上課的節(jié)數(shù)安排以及相關(guān)的課程之間的沖突能夠得到很大的改變，相比于以前的系統(tǒng)具有很大的優(yōu)化。

6 結(jié)論

綜合來(lái)講，利用先進(jìn)的計(jì)算機(jī)技術(shù)進(jìn)行排課是未來(lái)發(fā)展的趨勢(shì)，本文主要是針對(duì)高校的排課中出現(xiàn)的主要問(wèn)題進(jìn)行深入的分析與研究，提出了一種比較適合高校教學(xué)實(shí)際課程的比較通用的模型，并且針對(duì)這個(gè)模型給出一種實(shí)用的算法流程，并將這種算法應(yīng)用到某職業(yè)技術(shù)學(xué)院。

參考文獻(xiàn)

[1] 于宙.基于遺傳與模擬退火算法相結(jié)合的排課系統(tǒng)研究[D].大連理工大學(xué)，2014.

[2] 江蕭，弋改珍，袁嵐清.遺傳算法在排課系統(tǒng)中的應(yīng)用與設(shè)計(jì)研究[J].電腦知識(shí)與技術(shù)，2014（5）：1032-1035.