基于回溯算法制作自動(dòng)排課系統(tǒng)

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

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

中圖分類號(hào)：G71 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1673-9795（2013）09（b）-0133-02

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

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

1 排課基本原則

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

2 基于回溯算法自動(dòng)排課的核心思想

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

2.1 確定優(yōu)先級(jí)

回溯算法在很多自動(dòng)課表系統(tǒng)上應(yīng)用較多，回溯算法是排課系統(tǒng)尋找最優(yōu)解的有效算法。根據(jù)課程安排的要求先確定優(yōu)先級(jí)，優(yōu)先級(jí)的確定要根據(jù)專業(yè)課的安排優(yōu)先于非專業(yè)課、參與班級(jí)較多的課程優(yōu)先調(diào)度、階段課程周次靠前的優(yōu)先于周次靠后的、需四節(jié)連上的一體化課程優(yōu)先于兩節(jié)連上的課程、對(duì)時(shí)間有特殊要求的課程先調(diào)度、對(duì)教室有特殊要求的課程優(yōu)先調(diào)度。根據(jù)以上原則，設(shè)計(jì)了一個(gè)優(yōu)先級(jí)函數(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)先級(jí)函數(shù)；J（x）表示課程的級(jí)別；W（x）表示該課程開始于第幾周；S（x）表示該課程的參與班級(jí)數(shù)；T（x）表示教師承擔(dān)課程的任務(wù)量；L（x）表示需特殊安排的教師；P（x）表示教室的級(jí)別；C1，C2，C3，C4為可調(diào)整的參數(shù)，由G（x）可知，課程級(jí)別越高，課程開始周數(shù)越靠前，參與班越多，教師任務(wù)越重，有特殊要求的課程的優(yōu)先級(jí)超高，這樣按優(yōu)先級(jí)進(jìn)行降序排序，優(yōu)先級(jí)高的優(yōu)先處理。函數(shù)說明見表1。

2.2 核心算法流程

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

基本查找思路如下，流程圖如圖1所示：（1）根據(jù)G（X）函數(shù)，創(chuàng)建優(yōu)先級(jí)，并按降序，轉(zhuǎn)向（2）；（2）按照優(yōu)先級(jí)從大到小進(jìn)行排課，如都排完，轉(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）判斷當(dāng)前課節(jié)數(shù)是否大于等于4，如果是將變量N賦值4，轉(zhuǎn)向（8）；否則，轉(zhuǎn)向（7）；（7）將變量N賦值為2，轉(zhuǎn)向（8）；（8）課程是否對(duì)教室有特殊要求，如果是，轉(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）是指教室所容納的學(xué)生人數(shù)≥班級(jí)學(xué)生總?cè)藬?shù)。命令如下：

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

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

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

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

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

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

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

5 結(jié)語

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

參考文獻(xiàn)

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

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

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

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