杜衡吉

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

?

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

杜衡吉

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

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

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

1 前言

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

2 排課問(wèn)題的圖論算法

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

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

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

圖1 排課圖

圖2 染色后的排課圖

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

O157. 6

A

1671-1602(2016)22-0214-01