基于C/S模式自動排課系統的算法分析

張志順，周 銘，張晴雯，肖海榮

1.嘉應學院醫學院，廣東梅州 514031

2.梅縣氣象局，廣東梅州 514700

基于C/S模式自動排課系統的算法分析

張志順1，周 銘1，張晴雯2，肖海榮1

1.嘉應學院醫學院，廣東梅州 514031

2.梅縣氣象局，廣東梅州 514700

本文根據嘉應學院醫學院教學排課工作的實際需求，從排課問題入手，分析了教室信息數據結構及課程信息數據結構，對排課算法流程進行詳細描述和說明，給出了排課算法流程圖，實現了排課、調課、查詢、統計、打印等基本功能，可大大減少教學排課的手工勞動。

排課；C/S；數據結構；算法

1 排課問題描述

隨著高校教學改革工作的深化進行，教學排課工作的靈活性日益增強，如何對教室、教師、學生以及時間等幾部份資源進行最優組合，是保證整個教學計劃正常進行關鍵。排課是將教師與學生在時間和空間上根據不同的約束條件進行排列組合，在滿足全部約束條件的基礎上，實現教室、教師、學生、時間等資源的最優組合[1]。這里的約束條件主要是：同一時間對同一名教師安排了兩門不同的課程，對于該教師來說課程的安排是沖突的；對于學生也是如此，同一時間給同一教室安排兩門不同的課程，則對于這兩門課程來說，安排的教室是沖突的。

2 數據結構定義

2.1 教室信息數據結構

2.2 課程信息數據結構

3 算法流程描述

第一步：清空上次排課的結果；

第二步：根據條件查詢數據庫得到教室使用信息與待排課程信息，初始化roomlist（教室信息鏈表）和courselist（課程信息鏈表）；

第三步：進行自動排課。自動排課分為：有上課時間的排課與沒有上課時間的排課兩種情況；

第四步：保存排課結果。

對第一步操作的說明：

1）清除數據庫中T_jxTeachImplement表的所有有關的排課信息，包括課程的時間和地點，以及教室的fArranged字段（課室是否被安排）的內容都設為NULL。

2）清除數據庫T_ksClassroomUseInfo表中fArrangeTableId的內容，清除時把fArrangeTableId字段設為NULL。

對第二步操作的說明：

1）從數據庫中查找教室信息與課程信息。教室信息的來源是：根據查詢條件從T_jxClassroomList表中查找出教室信息。課程信息的來源是：根據查詢條件從T_jxTeachImplement表中查找出可供自動排考的課程信息。

2）根據教室信息取得教室的“座位數”、“課室功能代碼”、“序號”作為roomlist的roomkey值，再根據jxClassroomList（教室信息表）中的“序號”從T_ksClassroomUseInfo表中找到“安排項目ID”、“可用周數”、“可用節次”作為roomlist的roomvalue值。

3）根據課程信息找到“總共人數”、“課室功能代碼”、“序號”作為courselist的coursekey值，這里的總共人數是指最大的上限人數據，其中新生的總人數是按照學籍班人數計算，而老生的人數是按照注冊人數來計算[2]。

4）如果每周上課的次數大于1，則生成2個課程鏈節點。對有上課時間的，可根據上課時間找出對應的上課地點，對無上課時間的，則上課時間與上課地點都為空。

對第三步操作的說明：

1）取出courselist中的一個元素，以教室的容納人數來安排課程。如果一門課程無法找到合適的教室，就把它的序號（fId)插入UnarrangeableSet集合中，這可用來統計無法排課的課程。

2）為有上課時間但無上課地點且上課人數大于0的課程安排該門課程的上課時間與上課地點。

3）課程鏈節點值與教室鏈節點值滿足以下條件：課室安排項目相等、課室功能相等、上課時間是否處于教室可用日期、符合單雙周的要求、節次是合適。如果條件成立，則課程結點獲得上課地點。

4）對無上課時間且無上課地點的課程安排該門課程的上課時間與上課地點。

5）對面授周數和上課人數都大于0的課程安排，課程鏈節點值與教室鏈節點值滿足以下條件：課室安排項目相等、課室功能相等、教室的可用周數大于等于課程班所需要的面授周數。如果條件成立，生成安排時間和分裂教室結點。

對第四步操作的說明：

1）把排課中占用的教室時間寫入T_ksClassroomUseInfo表中。

2）把排課結果寫入到（教學計劃實施表）T_jxTeachImplement表中。

4 算法流程圖

4.1 排課系統數據流圖

圖4-1 排課系統數據流圖

4.2 排課算法流圖

圖4-2 排課算法流圖

5 結論

本文所設計的基于c/s（Client／Server，客戶/服務器）模式的教學排課系統，由客戶應用程序Client、服務器管理程序Server和中間件Middleware3個部件組成[3]，以Windows Server 2000/XP為網絡操作系統，以Borland公司的C++ Builder語言開發客戶端軟件，以SQL Server 2000為后臺數據庫，具有交互性強，可靠性高，事務數據處理能力強的特點。教學排課系統全面支持廣域網絡辦公模式，實現了排課、調課、查詢、統計、打印等基本功能，可大大減少教學排課的手工勞動。

[1] 王璐，邱玉輝.基于協商的智能排課系統的研究[J].計算機科學，2006，33(6)：214-217.

[2] 潘以鋒.高校智能排課系統的算法[J].上海師范大學學報：自然科學版，2006，35(5)：31-37.

[3] 部建華，紀玉玲.基于三層c/s結構教務管理系統的開發[J].佳木斯大學學報:自然科學版，2004，22(3)：27-30.

TP393

A

1674-6708（2010）18-0122-02

張志順，講師，工作單位：嘉應學院醫學院，從事計算機技術研究與軟件開發

周銘，職務：教務科長，工作單位：嘉應學院醫學院

張晴雯，助理工程師，工作單位：梅縣氣象局，從事計算機技術研究

肖海榮，高級講師，工作單位：嘉應學院醫學院，從事軟件開發