基于回溯算法制作自動排課系統

摘 要：隨著技工院校的課程改革，編排課程表這項工作變得越來越復雜。如果還采用人工排課的話，不僅費時費力，還容易出現沖突、錯漏等問題。為了有效地解決排課表問題，本文采用回溯算法來解決復雜的排課表問題，先創建優先級，再根據優先級從高到低的進行依次編排課程。最終生成課表。回溯法方便簡單，易于軟件實現。

關鍵詞：回溯算法 自動排課 應用軟件

中圖分類號：G71 文獻標識碼：A 文章編號：1673-9795（2013）09（b）-0133-02

技工院校的課表安排是一項復雜又叫人頭痛的工作，具體表現在以下幾個方面：（1）老師、學生、場地三者要保持協調統一；（2）個別專業實行模塊化教學，即在一定周期內上完一門課，接下來的周期再上另一門課，對授課場地造成極大浪費；（3）同一個老師專業跨度大，同時任教不同專業，甚至跨系部，如公共類課程；（4）招生規模的不穩定性使得教學設備數量無法完全滿足學生需求。

基于以上復雜多變的情況，要想人工調整課表是極困難的。現在已有很多種自動排課系統，但大多不適合技工院校的自動排課系統。其主要原因是：現在一些比較成功的自動排課系統適合中小學的課程安排。技工院校的課程多采用一體化教學模式，卻沒有一個科學的、合理的算法解決這個排課問題。筆者在2012年采用了回溯算法制作了一個自動排課系統，通過遍歷搜索確定優先級，然后將課程進行合理的排列，從而避免發生沖突和矛盾，經過三個學期的運行，該系統的可行性強，易操作，在教學實踐中發揮了重要作用。

1 排課基本原則

如何排出科學、合理和實用的課程表呢？必須從實際出發，筆者根據本校的課程安排實際情況，制定了下列規則：（1）同一教師不能在同一時間節點安排兩個或以上授課任務；（2）同一場地不能在同一時間節點安排兩個或以上授課任務；（3）小班教室或實訓室不能在同一時間節點安排兩名或以上教師授課；（4）教場的工位數要大于等于上課的人數；（5）教室的類型要與課程的類型一致。如，機房課與上機課、舞蹈室與舞蹈課等；（6）盡量安排實訓課4節連上，這符合多數一體化教學的要求；（7）盡量將文化理論課的教學安排在上午，而將實訓課，體育課等課程安排在第3節到第6節之間；（8）盡量避免教師的連續工作，即不能讓一個教師在一天或連續幾天內完成多個教學工作；（9）在某個特定的時間段不要安排教學任務，以便教師和學生都能夠利用這個時間進行一些教學工作以外的活動；（10）可根據特殊要求，對特殊的教師安排特定的時間；（11）避免同一班級的同一門理論課連續出現。

2 基于回溯算法自動排課的核心思想

回溯算法也叫試探法，它是一種系統地搜索問題的解的方法。它的基本思想是：從問題的某一種狀態（初始狀態）出發，搜索從這種狀態出發所能達到的所有“狀態”，當一條路走到“盡頭”的時候（不能再前進），再后退一步或若干步，從另一種可能“狀態”出發，繼續搜索，直到所有的“路徑”（狀態）都試探過。這種不斷“前進”、不斷“回溯”尋找最優解的方法，就稱作“回溯法”。

2.1 確定優先級

回溯算法在很多自動課表系統上應用較多，回溯算法是排課系統尋找最優解的有效算法。根據課程安排的要求先確定優先級，優先級的確定要根據專業課的安排優先于非專業課、參與班級較多的課程優先調度、階段課程周次靠前的優先于周次靠后的、需四節連上的一體化課程優先于兩節連上的課程、對時間有特殊要求的課程先調度、對教室有特殊要求的課程優先調度。根據以上原則，設計了一個優先級函數為：

G（x）=C1×J（x）+C2×W（x）+C3×S（x）+C4×T（x）+C5×L（x）+C6×P（x）

其中G（x）表示優先級函數；J（x）表示課程的級別；W（x）表示該課程開始于第幾周；S（x）表示該課程的參與班級數；T（x）表示教師承擔課程的任務量；L（x）表示需特殊安排的教師；P（x）表示教室的級別；C1，C2，C3，C4為可調整的參數，由G（x）可知，課程級別越高，課程開始周數越靠前，參與班越多，教師任務越重，有特殊要求的課程的優先級超高，這樣按優先級進行降序排序，優先級高的優先處理。函數說明見表1。

2.2 核心算法流程

確定好優先級數據后，就可按回溯算法進行排課表了。在排課表過程中，首先從課程數據表中取出優先級別高的課程，再從教室信息表中查找合適的教室，然后添加數據到課程表中，并將總課節數減2或減4。如遇到固定時間的課程，領導的課程應先安排。同時還要考慮教室的利用率，即上課人數與教室資源的比值，比值越大越好，最大值為1。

基本查找思路如下，流程圖如圖1所示：（1）根據G（X）函數，創建優先級，并按降序，轉向（2）；（2）按照優先級從大到小進行排課，如都排完，轉向（12）；否則，轉向（3）；（3）取出需要安排的課程數據，并將課節數賦給變量S，轉向（4）；（4）根據課程性質判斷是否為專業課，如果是，轉向（5）；否則，并轉向（7）；（5）判斷是否是一體化課程，如果是，轉向（6），否則，轉向（7）；（6）判斷當前課節數是否大于等于4，如果是將變量N賦值4，轉向（8）；否則，轉向（7）；（7）將變量N賦值為2，轉向（8）；（8）課程是否對教室有特殊要求，如果是，轉向（9）；否則，轉向（10）；（9）安排特殊教室，轉向（11）；（10）安排普通教室，轉向（11）；（11）S=S-N，判斷S是否等于0，如果是，轉向（2）；否則，轉向（4）；（12）所有課程安排結束。

要求1：（9）、（10）是指教室所容納的學生人數≥班級學生總人數。命令如下：

Select@studentSum=班級人數from班級信息表where班級編號in（select班級編號form課程信息表where課程編號=@courseID）/*@courseID為當前課程編號*/

Select教室編號from教室信息表where 容納人數>=@studentSum

要求2：自動排課系統不僅是上面12步就可完成的，還需考慮其他情況，減少排課的沖突。如4節連上的課程無合適教室（或實訓室）安排，則可按2節連上的形式分兩次安排；無需教室的課程，先找下午安排，如下午都已安排了課程，再安排上午上課。

3 數據庫的設計

數據庫的設計根據內容的需求而定，主要包含5個信息表，分別為：課程信息表、課程安排表、教師信息表、班級信息表、教室信息表。對于數據表的設計及主要字段如表2。

4 系統的實現

該系統已在我校計算機教學部進行了初步測試，效果良好。使用為Visual C#和SQL2005實現。為應對不可預料的突發情況或教師個人特殊情況的出現，系統中還加入了手動排課功能，對課程表進行局部調整。系統運行情況截圖如圖2所示。

5 結語

自動排課系統采用了回溯算法，極大地減少了沖突死鎖的概率，從而減少了人工干預的次數與時間，提高了排課效率。但全自動排課還有不如人意的地方，比如當教室比較緊張時，會出現個別課程安排不合理，需手動調整等情況，我將繼續研究，改進算法，制作出更完善的排課系統。

參考文獻

[1]彭復明.基于矩陣優化的機房自動排課算法[J].中國制造業信息化，2009（11）：52-54.

[2]王幫海，李振坤.基于貪婪算法的自動排課表系統的研究與實現[J].計算機工程與設計，2008，29（18）：4843-4846.

[3]陸峰，李新.自動排課系統算法的設計與實現[J].微機發展，2005，15（11）：60-63.

[4]張健.基于圖論的高校排課系統實現[J].重慶師范大學學報，2005（1）：35-38.