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

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

2、了算法的有效性。 </p><p>　　[關(guān)鍵詞]排課 組合優(yōu)化 圖論 </p><p>　　中圖分類號：G423.07 文獻標(biāo)識碼：A 文章編號：1009-914X（2016）10-0205-01 </p><p><b>　　1 概述 </b></p><p>　　隨著計算機相關(guān)技術(shù)及網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，職業(yè)技術(shù)學(xué)院

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

4、課進行研究與分析。 </p><p><b>　　2 問題提出 </b></p><p>　　近些來年，由于某職業(yè)技術(shù)學(xué)院的招生規(guī)模在不斷的擴大，學(xué)生的人數(shù)是在不斷的增加。在學(xué)生人數(shù)不斷增加的情況下，學(xué)校的教師、教室、實驗室的機房等相關(guān)硬件資源增加相對來說比較的落后。一些專業(yè)的課程不但沒有減少而且還在不斷增加，一些專業(yè)課程還在不斷的發(fā)生變化。這些不確定因素一定程度上增

5、加了教務(wù)排課方面的負擔(dān)。對于傳統(tǒng)的手工排課來說，過去的學(xué)生人數(shù)比較少、課程的變化情況比較小，針對這種情況還會出現(xiàn)一些問題。 </p><p>　　通過采用自動化的計算機排課系統(tǒng)能夠從根本上解決人力、物力等方面的資源合理利用，還能夠根據(jù)實際的數(shù)據(jù)變化情況動態(tài)產(chǎn)生變化。通過采用圖論算法能夠解決一些排課方面的問題，但是基于圖論算法的排課系統(tǒng)也會存在一些不足之處。例如一些圖論算法中將教師和班級作為二部圖來進行計算，這種模

6、型在實際的應(yīng)用過程中忽略了高校教學(xué)中班級可能不固定的情況，還有一些模型沒有考慮到學(xué)生的實際情況，將一門課程的兩次課安排在同一天內(nèi)，直接會增加學(xué)生的負擔(dān)。 </p><p><b>　　3 模型建立 </b></p><p>　　在高校的教學(xué)管理過程中有兩個比較明顯的特點，第一個是教學(xué)的班級是不固定的，第二是學(xué)校每學(xué)期會開設(shè)一些公共課或者必修課，學(xué)生能夠根據(jù)自己的興趣愛

7、好來選擇一些課程，基于這兩個特點，我們能夠把高校的排課轉(zhuǎn)換成圖論理論模型進行計算。 </p><p>　　在高校的教學(xué)過程中，大學(xué)的課程是以周為計算，將高校排課問題抽象成基本的圖論模型G（V，E）： </p><p>　　（1）其中頂點集用來表示教師與課程兩部分組成，集合T={T1，T2，T3，…，Tn}用來表示不同的教師集合，集合C={ C1，C 2，C 3，…，C n }表示課程的集合

8、。 </p><p>　　（2）在圖G（V，E）的相關(guān)邊集主要是由上面的兩個頂點之間的連線組成。比如集合T={T1，T2，T3，…，Tn}中的一位老師教授集合C={ C1，C 2，C 3，…，C n }中的一節(jié)課，那么就將這兩個頂點用實線連接起來。基于這個流程，高校排課問題就能夠轉(zhuǎn)變成一種偶圖。 </p><p>　　利用軟色理論中的相關(guān)邊著色理論來進行時間段的分配：在圖G（V，E）中可以

9、用例K中不同的顏色來進行邊的軟色處理，一種顏色就對應(yīng)一個上課時間段?；谶@個流程，就可以得到一張具有K個授課時間段的課表信息。在這個課表信息中，教師、課程不會發(fā)生相關(guān)的沖突問題。比如在圖1中，教師T1每周有三次課C1，C2，C3，教師T2每周有一次課C4，教師T3每周有兩次課C5，C6。 </p><p><b>　　4 算法設(shè)計 </b></p><p>　　在圖論

10、排課算法中，采用邊軟色的相關(guān)理論，通過構(gòu)造相應(yīng)的方法，對滿足相關(guān)沖突與約束的邊進行軟色處理，在所有能夠染色的顏色中尋找一種與所有實線課程的頂點之間的權(quán)重最接近的顏色進行軟色即可。最終根據(jù)權(quán)重的顏色集合進行排序處理，對于權(quán)重大的進行優(yōu)先排列，最后得到一張課表。 </p><p>　　根據(jù)職業(yè)技術(shù)學(xué)院的教學(xué)大綱，畫出相應(yīng)的圖G（V，E）。假設(shè)在圖G（V，E）中目前已經(jīng)有了n條實線邊，根據(jù)課程的重要程度將其權(quán)重值設(shè)置為

11、；圖中的頂點的最大度設(shè)置為；教室的總的數(shù)量信息設(shè)置為L個。按照下面的算法進行計算與排課： </p><p>　　（1）作相應(yīng)的圖G=（C，E），用來表示相應(yīng)的軟色的實線邊數(shù)的集合，用E里表示沒有軟色的實線邊的集合。取相應(yīng)的整數(shù)m（），構(gòu)造數(shù)據(jù)來表示m中不同的顏色，另外用來表示顏色中邊的個數(shù)。其中在初始化的時候設(shè)置為0。用表示這些顏色的相應(yīng)的實線邊的集合，初始化的值還是設(shè)置為。根據(jù)實際所需要的課程的情況及教室的實際

12、的數(shù)量信息來選擇適當(dāng)?shù)膮?shù)L（）信息。 </p><p>　?。?）設(shè)置相應(yīng)的構(gòu)造方法為布爾型，主要是用來表示軟色為k的所有實線的邊中是否含有與實線邊e進行連接的。如果有邊e那么就不能繼續(xù)進行軟色為k，返回false值；如果沒有那么需要進行相應(yīng)的軟色處理k，返回true值。這種方法需要進行相應(yīng)的遍歷處理E，時間復(fù)雜度為。 </p><p>　　（3）對于在E中實線的相應(yīng)的實線邊e，如果發(fā)生

13、，那么就需要遍歷相應(yīng)的顏色值，調(diào)用方法，找出其中返回值為true的所有的顏色集合K，在所有的能夠軟色顏色中找到一種與實線的邊e的所有課程的頂點的權(quán)重最為接近的顏色，將這條實線邊e軟色為。同時，在這個算法過程中運行，，，，。通過這個步驟來遍歷所有的集合E中的實線邊，并且對這些實線邊的遍歷的顏色值，時間上的復(fù)雜度為。如果在遍歷的過程中沒有找到合適的顏色來進行軟色，那么就不會有合適的返回值true，就表示沒有找到合適的顏色值對這條邊進行軟色，

14、那么就需要選取另外的整數(shù)m，重新返回到（1）。如果在選取一定的數(shù)目信息之后，仍然沒有合適的顏色，那么就需要退出這個程序。 </p><p>　　（4）如果發(fā)生，那么需要計算返回軟色的結(jié)果E，，。否則就需要返回到步驟（3）中繼續(xù)進行計算。 </p><p><b>　　5 系統(tǒng)實現(xiàn) </b></p><p>　　采用目前留下的編程技術(shù)JSP語言實

15、現(xiàn)某職業(yè)學(xué)院的高校排課系統(tǒng)的相關(guān)開發(fā)。用戶操作起來比較方便，界面比較友好，功能完善性比較好，對系統(tǒng)的支持性要求很低。根據(jù)輸入或者采集的初始數(shù)據(jù)信息使用上面的圖論排序算法進行高校排課，排課生成的課程表可以按照班級、教師、教室、時間等多種關(guān)鍵字進行查詢。 </p><p>　　根據(jù)開發(fā)的這個系統(tǒng)，能夠?qū)⒙殬I(yè)技術(shù)學(xué)院2015、2016級的四個學(xué)期的課程進行重新的排列，生成新的課表。通過將新生成的課表與原來已經(jīng)排好的課表

16、之間進行比較。比較的對象包括同一種課程上課之間的間隔信息、學(xué)生主要課程每周上課的天數(shù)、學(xué)生平均每天的上課的節(jié)數(shù)安排以及相關(guān)的課程之間的沖突等。通過相應(yīng)的測試能夠發(fā)現(xiàn)，在這個系統(tǒng)中同一種課程上課之間的間隔信息、學(xué)生主要課程每周上課的天數(shù)、學(xué)生平均每天的上課的節(jié)數(shù)安排以及相關(guān)的課程之間的沖突能夠得到很大的改變，相比于以前的系統(tǒng)具有很大的優(yōu)化。 </p><p><b>　　6 結(jié)論 </b>&l

17、t;/p><p>　　綜合來講，利用先進的計算機技術(shù)進行排課是未來發(fā)展的趨勢，本文主要是針對高校的排課中出現(xiàn)的主要問題進行深入的分析與研究，提出了一種比較適合高校教學(xué)實際課程的比較通用的模型，并且針對這個模型給出一種實用的算法流程，并將這種算法應(yīng)用到某職業(yè)技術(shù)學(xué)院。 </p><p><b>　　參考文獻 </b></p><p>　　[1] 于宙