基于優(yōu)先度與回溯算法的高職院校排課系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

柯紅香

(漳州科技職業(yè)學(xué)院 通識(shí)課程部，福建 漳州363200)

排課管理作為高校教學(xué)管理和實(shí)施的重要工作之一，是維持高校正常教學(xué)秩序的前提，其涉及范圍廣、受限制的條件多，排課時(shí)需考慮上課時(shí)間、教學(xué)場(chǎng)所、教師及學(xué)生等多方面因素[1]。傳統(tǒng)的手工排課方式容易造成排課因素沖突、教學(xué)資源分配不合理、管理效率低等問(wèn)題，影響了教學(xué)工作的正常運(yùn)轉(zhuǎn)，已無(wú)法滿足現(xiàn)有教學(xué)管理的需要[2]。本文針對(duì)某高職學(xué)院人工排課效率低下、自動(dòng)化程度低、用戶滿意度不高的問(wèn)題，在充分研究回溯算法的基礎(chǔ)上，提出了一種基于排課資源優(yōu)先度的回溯算法的排課系統(tǒng)。

1 回溯算法

回溯算法是一種基于深度優(yōu)先的系統(tǒng)性搜索問(wèn)題解的算法，其解決問(wèn)題的一般步驟為：(1)針對(duì)問(wèn)題定義解空間，解空間至少包含一個(gè)(最優(yōu))解；(2)確定搜索的解空間結(jié)構(gòu)；(3)按深度優(yōu)先的策略從根節(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。搜索開(kāi)始時(shí)，根節(jié)點(diǎn)為活節(jié)點(diǎn)，也是當(dāng)前擴(kuò)展節(jié)點(diǎn)，搜索向縱深方向移動(dòng)至下一個(gè)新節(jié)點(diǎn)，這時(shí)新節(jié)點(diǎn)也變成當(dāng)前擴(kuò)展節(jié)點(diǎn)。搜索至新節(jié)點(diǎn)首先判斷是否包含問(wèn)題解，若包含問(wèn)題解，繼續(xù)按深度優(yōu)先的策略搜索該子結(jié)點(diǎn)。若不包含問(wèn)題解，當(dāng)前擴(kuò)展節(jié)點(diǎn)不再縱深移動(dòng)，并標(biāo)記該節(jié)點(diǎn)為死節(jié)點(diǎn)。跳過(guò)該節(jié)點(diǎn)回溯至最近的一個(gè)活節(jié)點(diǎn)，從另一分支進(jìn)行搜索[3]，重復(fù)以上搜索過(guò)程，直至找到所要求的解或遍歷解空間樹(shù)的所有活結(jié)點(diǎn)時(shí)為止。此外，回溯法的搜索過(guò)程可使用剪枝函數(shù)避免無(wú)效的搜索。剪枝函數(shù)包含兩類：約束函數(shù)和限界函數(shù)，可剪去互斥約束條件的路徑和不能得到最優(yōu)解的路徑，從而提高搜索效率。換言之，回溯算法是一種特別適合通過(guò)構(gòu)建約束條件來(lái)提高程序效率的枚舉搜索方法[4]。

回溯算法在排課系統(tǒng)的應(yīng)用廣泛，研究集中在排課算法優(yōu)化，旨在避免排課因素的沖突，使排課結(jié)果可用。但是排課算法卻很難兼顧課表的最優(yōu)化和合理性，特別是合理性很難靠算法實(shí)現(xiàn)[5]。為此，本文通過(guò)參考文獻(xiàn)對(duì)比國(guó)內(nèi)外排課算法基礎(chǔ)上，結(jié)合高職院校具體排課需求，將文獻(xiàn)[6]和文獻(xiàn)[7]基于排課資源優(yōu)先的改進(jìn)后的回溯排課算法應(yīng)用于本系統(tǒng)。對(duì)排課資源——時(shí)間片(Time)、課程(Course)、教室(Room)、班級(jí)(Class)四大因素設(shè)置優(yōu)先度和對(duì)應(yīng)的權(quán)值，建立不同資源優(yōu)先度的聯(lián)系，模擬人工排課經(jīng)驗(yàn)，設(shè)置約束條件盡量避免排課過(guò)程中產(chǎn)生過(guò)多的沖突和引起過(guò)多的回溯，從而提高排課效率和合理性。

2 排課管理系統(tǒng)設(shè)計(jì)

2.1 需求分析

除了維護(hù)功能之外，本系統(tǒng)應(yīng)包括以下主要功能：①教學(xué)基本信息管理，該功能主要有學(xué)年學(xué)期設(shè)置、專業(yè)班級(jí)設(shè)置、教學(xué)場(chǎng)地管理、課程信息、學(xué)生學(xué)籍和教師信息管理；②開(kāi)課計(jì)劃管理，即專業(yè)班級(jí)所開(kāi)設(shè)課程、教師可承擔(dān)課程的增刪改操作；③課表編排功能，該功能是系統(tǒng)的核心功能，應(yīng)能完成班級(jí)課程中任課教師、上課時(shí)間和教室安排三者之間的匹配；④課表查看功能，使有相應(yīng)權(quán)限的用戶可以查詢排課結(jié)果。

2.2 系統(tǒng)功能模塊設(shè)計(jì)

根據(jù)需求分析，系統(tǒng)主要由基本信息管理、開(kāi)課計(jì)劃管理、編排課表、查詢課表和系統(tǒng)維護(hù)五大模塊組成，其功能結(jié)構(gòu)如圖1所示。

圖1 系統(tǒng)功能模塊

2.3 數(shù)據(jù)庫(kù)設(shè)計(jì)

數(shù)據(jù)庫(kù)概念設(shè)計(jì)是通過(guò)系統(tǒng)需求分析反映用戶觀點(diǎn)的數(shù)據(jù)結(jié)構(gòu)化的過(guò)程[8]，其目的在于用符號(hào)的形式正確反映實(shí)際事物及事物與事物間的聯(lián)系。本系統(tǒng)主要涉及教師、課程、教室、學(xué)生四個(gè)實(shí)體，其間的聯(lián)系具體為：教室和課程的安排關(guān)系、教師和課程的授課關(guān)系、學(xué)生和課程的學(xué)習(xí)關(guān)系。主要數(shù)據(jù)表單描述如下：

(1) 教師信息表(Teacher)：用于任課教師信息的增刪改查。教師可以教授一門或多門課程，如表1所示。

表1 教師信息

(2) 學(xué)生信息表(Student)：用于學(xué)生信息的錄入、修改、刪除和查詢。學(xué)生信息包括學(xué)生編號(hào)、姓名、性別、民族、出生年月、入學(xué)年份、所在班級(jí)、身份證等信息。學(xué)生數(shù)據(jù)表單設(shè)計(jì)與教師類似。

(3) 教室信息表(Classroom)：用于存放教室名稱、類型、容量等信息，具體字段如表2所示。

表2 教室信息

(4) 課程信息表(Course)：用于存放全校開(kāi)設(shè)的所有課程信息，包括課程代碼、名稱、類型、學(xué)分和學(xué)時(shí)等屬性，具體字段如表3所示。

表3 課程信息

(5) 排課結(jié)果表(ArrangedResult)：排課結(jié)果表的主鍵是一個(gè)全鍵值，其結(jié)構(gòu)如表4所示。

表4 排課結(jié)果表

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

3.1 自動(dòng)編排課表功能實(shí)現(xiàn)

3.1.1 排課資源優(yōu)先度 利用回溯算法實(shí)現(xiàn)課表編排時(shí)需要計(jì)算排課資源的優(yōu)先度。排課資源優(yōu)先度分為時(shí)間片數(shù)組(TimeArray)、課程數(shù)組(CourseArray)和班級(jí)數(shù)組(ClassArray)。按照課程類型、班級(jí)周課時(shí)數(shù)、是否必須在某個(gè)時(shí)間片上課等屬性，將屬性進(jìn)行線性組合得到一個(gè)權(quán)值，權(quán)值大表示所受的約束條件越多，優(yōu)先排課。排課資源優(yōu)先度的設(shè)置如表5所示。

表5 排課資源優(yōu)先度設(shè)置

3.1.2 課程編排的回溯算法實(shí)現(xiàn) 排課以班級(jí)為單位，按時(shí)間片的優(yōu)先度進(jìn)行遍歷。首先從班級(jí)數(shù)組ClassArray中讀取優(yōu)先級(jí)較高(即權(quán)值較大)的班級(jí)，再讀取班級(jí)對(duì)應(yīng)的CourseArray中的某一門課程，接著從TimeArray中讀取一個(gè)時(shí)間片，并將該時(shí)間片與任課教師上課時(shí)間進(jìn)行校驗(yàn)。若校驗(yàn)通過(guò)，再將時(shí)間片與教室數(shù)組RoomArray可用時(shí)間進(jìn)行校驗(yàn)。若各節(jié)點(diǎn)滿足排課條件，則結(jié)束該門課程編排；否則，回溯至上一節(jié)點(diǎn)尋求另一個(gè)時(shí)間片和教室，直至完成所有課程的編排。若遍歷所有節(jié)點(diǎn)，仍無(wú)法滿足課程資源分配，則提高課程的優(yōu)先度，通過(guò)一定限度的回溯調(diào)整先前課程安排，再為當(dāng)前課程分配其他資源，直到成功為止，其算法流程圖如圖2所示。

圖2基于回溯算法的排課流程圖 圖3課程輔助編排算法流程圖

3.2 課程輔助編排功能實(shí)現(xiàn)

系統(tǒng)還設(shè)計(jì)了輔助編排功能，以解決因客觀條件變動(dòng)導(dǎo)致小部分課程無(wú)法被妥善編排的問(wèn)題。圖3為課程輔助編排的算法流程圖。實(shí)現(xiàn)后的效果如圖4所示。

圖4 課程輔助編排界面

4 結(jié)語(yǔ)

排課問(wèn)題本質(zhì)上一個(gè)組合優(yōu)化問(wèn)題，其復(fù)雜性較高。本文在深入研究回溯算法的基礎(chǔ)上將之應(yīng)用到高職學(xué)院排課系統(tǒng)的開(kāi)發(fā)過(guò)程中。系統(tǒng)采用C#作為開(kāi)發(fā)語(yǔ)言，Windows 7作為開(kāi)發(fā)平臺(tái)，Microsoft SQL Server 2012作為數(shù)據(jù)庫(kù)服務(wù)器，系統(tǒng)部署在Microsoft IIS8應(yīng)用服務(wù)器上。系統(tǒng)經(jīng)測(cè)試后投入使用，效果良好，提高了排課工作的運(yùn)行效率，用戶的滿意度也同時(shí)得到了提高。