基于優先度與回溯算法的高職院校排課系統設計與實現

柯紅香

(漳州科技職業學院 通識課程部，福建 漳州363200)

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

1 回溯算法

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

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

2 排課管理系統設計

2.1 需求分析

除了維護功能之外，本系統應包括以下主要功能：①教學基本信息管理，該功能主要有學年學期設置、專業班級設置、教學場地管理、課程信息、學生學籍和教師信息管理；②開課計劃管理，即專業班級所開設課程、教師可承擔課程的增刪改操作；③課表編排功能，該功能是系統的核心功能，應能完成班級課程中任課教師、上課時間和教室安排三者之間的匹配；④課表查看功能，使有相應權限的用戶可以查詢排課結果。

2.2 系統功能模塊設計

根據需求分析，系統主要由基本信息管理、開課計劃管理、編排課表、查詢課表和系統維護五大模塊組成，其功能結構如圖1所示。

圖1 系統功能模塊

2.3 數據庫設計

數據庫概念設計是通過系統需求分析反映用戶觀點的數據結構化的過程[8]，其目的在于用符號的形式正確反映實際事物及事物與事物間的聯系。本系統主要涉及教師、課程、教室、學生四個實體，其間的聯系具體為：教室和課程的安排關系、教師和課程的授課關系、學生和課程的學習關系。主要數據表單描述如下：

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

表1 教師信息

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

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

表2 教室信息

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

表3 課程信息

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

表4 排課結果表

3 系統實現

3.1 自動編排課表功能實現

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

表5 排課資源優先度設置

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

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

3.2 課程輔助編排功能實現

系統還設計了輔助編排功能，以解決因客觀條件變動導致小部分課程無法被妥善編排的問題。圖3為課程輔助編排的算法流程圖。實現后的效果如圖4所示。

圖4 課程輔助編排界面

4 結語

排課問題本質上一個組合優化問題，其復雜性較高。本文在深入研究回溯算法的基礎上將之應用到高職學院排課系統的開發過程中。系統采用C#作為開發語言，Windows 7作為開發平臺，Microsoft SQL Server 2012作為數據庫服務器，系統部署在Microsoft IIS8應用服務器上。系統經測試后投入使用，效果良好，提高了排課工作的運行效率，用戶的滿意度也同時得到了提高。