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

關(guān)鍵詞：回溯算法 自動排課 應用軟件

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

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

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

1 排課基本原則

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

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

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

2.1 確定優(yōu)先級

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

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

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

2.2 核心算法流程

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

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

要求1：（9）、（10）是指教室所容納的學生人數(shù)≥班級學生總?cè)藬?shù)。命令如下：

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

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

要求2：自動排課系統(tǒng)不僅是上面12步就可完成的，還需考慮其他情況，減少排課的沖突。如4節(jié)連上的課程無合適教室（或?qū)嵱柺遥┌才?，則可按2節(jié)連上的形式分兩次安排；無需教室的課程，先找下午安排，如下午都已安排了課程，再安排上午上課。

3 數(shù)據(jù)庫的設計

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

4 系統(tǒng)的實現(xiàn)

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

5 結(jié)語

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

參考文獻

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

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

[3]陸峰，李新.自動排課系統(tǒng)算法的設計與實現(xiàn)[J].微機發(fā)展，2005，15（11）：60-63.

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