基于圖論算法的高校排課系統(tǒng)分析

杜衡吉

(曲靖師范學(xué)院信息工程學(xué)院，云南 曲靖 655011)

?

基于圖論算法的高校排課系統(tǒng)分析

杜衡吉

(曲靖師范學(xué)院信息工程學(xué)院，云南 曲靖 655011)

高校學(xué)生人數(shù)以及課程設(shè)置眾多，排課工作十分繁重。隨著時代的發(fā)展，各種教育信息化的應(yīng)用逐漸規(guī)?；咝Ｐ?wù)系統(tǒng)、辦公自動化系統(tǒng)以及網(wǎng)上排課系統(tǒng)等也得到快速的發(fā)展。在進行排課系統(tǒng)設(shè)計的時候，可以采用不同的算法。本文以圖論算法為例，分析相應(yīng)的高校排課系統(tǒng)設(shè)計方法。

圖論算法；高校；排課系統(tǒng)

1 前言

高校的教育教學(xué)工作中，排課是一個必不可少的重要環(huán)節(jié)。從本質(zhì)角度進行分析，排課的實質(zhì)在于對學(xué)校所設(shè)置的各種課程進行合理的安排，進行一組適當(dāng)?shù)慕虒W(xué)時間與空間安排，以保證整個教學(xué)活動可以按照一定的秩序和計劃順利開展。但是，在實際的排課過程中，存在十分復(fù)雜的情況，需要對課程分布情況和時間分配情況以及教師、教室等情況予以綜合性的考慮和安排，受到多方面條件的約束。

2 排課問題的圖論算法

在對排課問題進行研究的時候，可以選擇使用不同的算法，包括遺傳算法和退火算法以及圖論算法等。其中，遺傳算法和退火算法存在一定的應(yīng)用局限性。而圖論算法則可以對一定的問題進行轉(zhuǎn)化，將其轉(zhuǎn)化為圖論問題。之后，利用圖論的基本算法進行解決，達到解決實際問題的目的。在排課過程中，受到高校日常教學(xué)情況的影響，相應(yīng)的不同元素存在太多的組合可能性，十分復(fù)雜。此時，可嘗試?yán)脠D論算法進行解決。首先，對模型進行合理的簡化，將其簡化為兩個子模型，之后，對上述兩個優(yōu)化過程進行轉(zhuǎn)化，將其轉(zhuǎn)化為圖論問題予以解決。按照圖論算法相關(guān)定理，對模型予以初步優(yōu)化。之后，以圖論的完美對集理論為基礎(chǔ)，結(jié)合教學(xué)效果對排課模型圖中的一些邊賦了權(quán)值，選出權(quán)值最大加權(quán)圖，最終得出最優(yōu)的排課方案。

3 基于圖論算法的高校排課系統(tǒng)分析

3.1 初始模型的建立。采用圖論算法解決排課問題的第一步是將其先轉(zhuǎn)化為二分圖邊染色問題?，F(xiàn)在假設(shè)一共有5個班級，需要由 4 位老師進行授課。對于班級和教師之間的對應(yīng)關(guān)系，可以利用圖1的二分圖予以表示。在實際的 教學(xué)過程中，同一時間內(nèi)，一名教師只能給其中的一個班級授課，而同一時間內(nèi)一個班級不能由兩名老師授課，則可以獲得圖2 的著色方案。

圖1 排課圖

圖2 染色后的排課圖

3.2 排課模型的優(yōu)化。按照上文的分析，在進行排課的時候，如果單純使用邊著色理論，只能確保從時間角度教師與班級不發(fā)生沖突。無法保證可以滿足教學(xué)方面的需求。另外，在進行排課的時候還要考慮到一些特殊情況。這樣一開，便需要對排課的效果進行優(yōu)化設(shè)計。構(gòu)建的權(quán)值函數(shù)如下：

ω(tici)=ω1(tici)+ω2(tici)+……+ωn(tici)

在具體模型分析的時候，可以結(jié)合實際情況，通過權(quán)值函數(shù)對圖中的每條邊都進行相應(yīng)的賦值。最終的最優(yōu)排課安排計劃，即為所有加權(quán)圖中權(quán)值最大的圖。

3.3 排課管理系統(tǒng)的設(shè)計。為了更好的解決高校排課表問題，設(shè)計開發(fā)一個簡易排課管理系統(tǒng)。通過該系統(tǒng)，可以生成一定的排課安排，很好的滿足日常教學(xué)的需求。整個系統(tǒng)包含多個不同的功能模塊，通過不同的模塊，可以實現(xiàn)排課管理和課表查詢等，排課管理系統(tǒng)功能模塊設(shè)計示意圖如圖 3所示。

圖3 排課管理系統(tǒng)功能模塊設(shè)計示意圖

在系統(tǒng)中進行數(shù)據(jù)交換的時候，底層數(shù)據(jù)庫為Excel。在進行排課之前，首先對涉及到的班級和教師進行匯總，輸入Excel中，之后，使用一定的函數(shù)，對MATLAB與Excel進行數(shù)據(jù)交換。并利用一定的函數(shù)對邊著色問題予以解決，實現(xiàn)對課時的合理安排。

3.4 排課系統(tǒng)的應(yīng)用效果。手工排課一向是學(xué)校教務(wù)工作中最令人頭疼的事，非常費時費神，而且由于人工操作時多多少少會有些失誤。而通過對設(shè)計的排課系統(tǒng)予以實際應(yīng)用，網(wǎng)上選課及計算機排課子系統(tǒng)將按行政班教學(xué)和按選課形成的教學(xué)班教學(xué)兩種模式融合，自然過渡，面向教學(xué)管理鏈實行教學(xué)資源的動態(tài)管理，以排課為中心，將教學(xué)任務(wù)安排、排課、選課、考試安排、教室調(diào)配、任課教師管理、學(xué)籍管理等統(tǒng)一在一個管理鏈上，在教學(xué)資源管理調(diào)配和統(tǒng)計分析等方面充分融合。系統(tǒng)還可以提供自動和交互兩種排課方式，提供兩類學(xué)生上課視圖、教師上課視圖和教室使用視圖，課程安排情況一目了然，操作直觀、簡單、便捷。教室調(diào)配子系統(tǒng)與排課系統(tǒng)聯(lián)動，進行借用管理、查詢和分析統(tǒng)計，生成全校教室使用情況匯總表。考試安排子系統(tǒng)根據(jù)學(xué)生選課結(jié)果安排考試時間和教室，保證每名學(xué)生考試時間不沖突。經(jīng)過一段時間的應(yīng)用，獲得了理想的應(yīng)用效果，排課效果良好，課程安排秩序井然。

4 結(jié)束語

總之，高校在進行排課的時候，需要充分考慮不同的約束條件。同時，要注意遵循科學(xué)性以及技術(shù)性原則。合理的利用圖論算法，設(shè)計符合學(xué)校實際情況的排課系統(tǒng)。從而更好的進行排課優(yōu)化設(shè)計，避免各種沖突的出現(xiàn)，保證教學(xué)活動的順利開展。

杜衡吉(1976.3-)，男，漢族，江蘇邳州人，講師，碩士，主要從事計算數(shù)學(xué)及計算機應(yīng)用研究。

O157. 6

A

1671-1602(2016)22-0214-01