圖論在教師排課管理中應用

李芳

【摘要】學校的排課管理作為教務系統中最為極為重要的一個環節之一，如若排課不恰當會造成多種沖突情況發生，如實驗教室的使用發生沖突、上課時間上的沖突以及教師授課的沖突，然而這些問題都會一定程度上對教學效率造成不利影響。通過圖論的相關理論能夠有效的避免這些沖突的產生，從而確保學生能夠正常上課，保障學習效率。

【關鍵詞】圖論教法 ?教師排課管理 ?應用分析

【中圖分類號】G715 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文獻標識碼】A ? ? ?【文章編號】2095-3089（2016）11-0154-01

一、引言

課表的安排管理問題是學校教學中時間以及地點安排問題，這一問題的解決需要學校的相關教務管理人員花費較大強度的腦力與長時間的安排，是教務系統的核心工作。學生的課表安排需要結合許多因素，如：教室、班級以及上課時間等。因為要將多種因素結合考慮，所以通常情況下相關負責人員只能夠手工安排課表。而這種方式在信息技術不斷普及的狀態下，效率顯得十分低下。文章從圖論的角度來對課表問題進行分析，提出最佳排課模型以滿足實際需要。

二、排課的由來

排課是學校教學管理中十分重要而又具有較大難度的一項任務，它指的是給學校設立的老師教學課程的安排提供合適的時間，進而讓各個老師的教學時間不會發生沖突，讓老師的教學工作順利開展。在老師的排課管理中，其中主要工作就是合理安排各項資源，例如：教學地點、學科以及時間等方面。通常情況下，是以一個循環周期的方法來適當的調配，讓各項資源不會沖突。換種說法，排課是為了讓老師與學生的時間以及上課地點進行統一。所以，課表則是排課工作的最終體現，課表算法是為了合理的安排老師與學生時間以及上課地點的統一。

三、傳統排課模型算法的不足

為防止老師與學生時間以及上課地點發生沖突，則出現了排課算法。現今大部分的排課算法都是模擬手動排課的操作方法，利用計算機進行編排，老師的排課先按以往的編排習慣來調配老師與學生的時間以及上課地點，等到有問題出現時再進行相應的調控，但新的調整又有較大可能引發新的問題出現，這就無法很好的解決問題，并且沒有效率。除此之外，這類算法還無法確保預算出的結論較優。

四、圖論在教師排課管理中的應用

在編排課表的過程中，其主要目的是合理的安排老師與學生時間以及上課地點的統一。在這當中，有過多的可能性。因此可以把模型劃分為兩部分來考慮：一是老師與學生時間上的安排，二是老師與學生上課地點的安排，在進行這兩種安排的過程中都可以運用圖論方法來運作解決。

1.教師排課管理中時間的安排

教師排課管理中時間的安排其實質是指讓教師在指定的時間內去給某個班級上課。在這當中，需要滿足以下幾個要求：首先，在同一個時間范圍內教師只可以給一個班級上課;其次，不同班級在同一時間也只能有一個老師教課。運用圖論方法來解決這一問題，如：有N個老師，分別是X1....XN，另外有M個班級，分別是Y1....YN，其中某個老師要教某個班級就要將這兩者用線連接起來，若是一個星期之內某個老師給某個班級上了兩次課，則用兩條線相連，依次增加。使用二部圖Z表示，讓Z=（W，X，Y），其中W指的是連接老師與班級之間的線。具體如圖一所示：

圖一

眾所周知，同一個頂點的邊是相鄰邊。對每條邊用不同顏色上色，一種顏色指代一段時間，拿大學為例，大學課程一般為兩課時一節課，一天四節，一星期五天，因此在教師排課管理中邊色數應為二十，指代的是二十段時間，一樣的顏色指代的是一個時間段是由于相同時間當中每個老師只可以去一個班級教課，不同班級在同一時間也只能有一個老師教課。相鄰邊指代的是老師或學生是相同的，不能安排在同一時間段內上課，這就要求相鄰邊不可以使用相同顏色標明。

2.教師排課管理中上課地點的安排

教師排課管理中上課地點的安排其實質是讓某個班級在一個時間段內到指定的上課地點上課，在這當中，需要滿足以下幾個要求：首先，在同一個時間范圍內教師只可以給一個班級上課;其次，不同班級在同一時間也只能有一個老師教課。最后，要保證班級的總人數要比教師的容納量小，確保學生有位置坐。但又不能讓教師太大，否則會影響上課效果。運用圖論方法來解決這一問題，如：在指定的時間段內，有五個班級X1至X5要安排不同教師上課，這時剛好又有五個教室Y1至Y5可以用，兩者之間的關系如圖二：

圖二

根據不同教室的使用來賦值，設立的權限可以從以下數據看出：

W

5 5 5 2 1

2 4 4 1 2

0 2 1 0 0

0 0 3 3 3

1 4 4 1 2

其中這些數據中一個數表示的是不同班級分配到不同教室的適合程度，數字越大表示適合程度越高，就可以先行考慮。不過不管如此，到最后都要確保五個班級都要有適合的教室上課。

五、結語

將本文所述的兩類方法結合，就能構建一張完整的課表，這樣就能保證老師與學生時間以及上課地點能夠保證同步。其中運用的實際方法就是圖論法，圖論運用至教師排課管理中，有助于解決以往排課過程中的困難，打破傳統排課方法的局限性，進而防止老師與學生的上課時間發生沖撞，提高教學效率。

參考文獻：

[1]吳丈虎，王建德.圖論的算法與程序設計[J].北京：清華大學出版社，2013.06.（05）：39-43.

[2]王鳳，林杰.高校排課問題的圖論模型及算法[J].計算機工程與應用，2014.11.（13）：373-375.

[3]程泉，朱大銘.用圖的著色方法求解考試時間安排問題[J].計算機應用，2015.04.（21）：117-119.