基于圖論算法的高校排課系統分析

杜衡吉

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

?

基于圖論算法的高校排課系統分析

杜衡吉

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

高校學生人數以及課程設置眾多，排課工作十分繁重。隨著時代的發展，各種教育信息化的應用逐漸規模化，高校校務系統、辦公自動化系統以及網上排課系統等也得到快速的發展。在進行排課系統設計的時候，可以采用不同的算法。本文以圖論算法為例，分析相應的高校排課系統設計方法。

圖論算法；高校；排課系統

1 前言

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

2 排課問題的圖論算法

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

3 基于圖論算法的高校排課系統分析

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

圖1 排課圖

圖2 染色后的排課圖

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

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

在具體模型分析的時候，可以結合實際情況，通過權值函數對圖中的每條邊都進行相應的賦值。最終的最優排課安排計劃，即為所有加權圖中權值最大的圖。

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

圖3 排課管理系統功能模塊設計示意圖

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

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

4 結束語

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

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

O157. 6

A

1671-1602(2016)22-0214-01