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

1.嘉應(yīng)學(xué)院醫(yī)學(xué)院，廣東梅州 514031

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

基于C/S模式自動(dòng)排課系統(tǒng)的算法分析

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

1.嘉應(yīng)學(xué)院醫(yī)學(xué)院，廣東梅州 514031

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

本文根據(jù)嘉應(yīng)學(xué)院醫(yī)學(xué)院教學(xué)排課工作的實(shí)際需求，從排課問題入手，分析了教室信息數(shù)據(jù)結(jié)構(gòu)及課程信息數(shù)據(jù)結(jié)構(gòu)，對(duì)排課算法流程進(jìn)行詳細(xì)描述和說明，給出了排課算法流程圖，實(shí)現(xiàn)了排課、調(diào)課、查詢、統(tǒng)計(jì)、打印等基本功能，可大大減少教學(xué)排課的手工勞動(dòng)。

排課；C/S；數(shù)據(jù)結(jié)構(gòu)；算法

1 排課問題描述

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

2 數(shù)據(jù)結(jié)構(gòu)定義

2.1 教室信息數(shù)據(jù)結(jié)構(gòu)

2.2 課程信息數(shù)據(jù)結(jié)構(gòu)

3 算法流程描述

第一步：清空上次排課的結(jié)果；

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

第三步：進(jìn)行自動(dòng)排課。自動(dòng)排課分為：有上課時(shí)間的排課與沒有上課時(shí)間的排課兩種情況；

第四步：保存排課結(jié)果。

對(duì)第一步操作的說明：

1）清除數(shù)據(jù)庫(kù)中T_jxTeachImplement表的所有有關(guān)的排課信息，包括課程的時(shí)間和地點(diǎn)，以及教室的fArranged字段（課室是否被安排）的內(nèi)容都設(shè)為NULL。

2）清除數(shù)據(jù)庫(kù)T_ksClassroomUseInfo表中fArrangeTableId的內(nèi)容，清除時(shí)把fArrangeTableId字段設(shè)為NULL。

對(duì)第二步操作的說明：

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

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

3）根據(jù)課程信息找到“總共人數(shù)”、“課室功能代碼”、“序號(hào)”作為courselist的coursekey值，這里的總共人數(shù)是指最大的上限人數(shù)據(jù)，其中新生的總?cè)藬?shù)是按照學(xué)籍班人數(shù)計(jì)算，而老生的人數(shù)是按照注冊(cè)人數(shù)來計(jì)算[2]。

4）如果每周上課的次數(shù)大于1，則生成2個(gè)課程鏈節(jié)點(diǎn)。對(duì)有上課時(shí)間的，可根據(jù)上課時(shí)間找出對(duì)應(yīng)的上課地點(diǎn)，對(duì)無(wú)上課時(shí)間的，則上課時(shí)間與上課地點(diǎn)都為空。

對(duì)第三步操作的說明：

1）取出courselist中的一個(gè)元素，以教室的容納人數(shù)來安排課程。如果一門課程無(wú)法找到合適的教室，就把它的序號(hào)（fId)插入U(xiǎn)narrangeableSet集合中，這可用來統(tǒng)計(jì)無(wú)法排課的課程。

2）為有上課時(shí)間但無(wú)上課地點(diǎn)且上課人數(shù)大于0的課程安排該門課程的上課時(shí)間與上課地點(diǎn)。

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

4）對(duì)無(wú)上課時(shí)間且無(wú)上課地點(diǎn)的課程安排該門課程的上課時(shí)間與上課地點(diǎn)。

5）對(duì)面授周數(shù)和上課人數(shù)都大于0的課程安排，課程鏈節(jié)點(diǎn)值與教室鏈節(jié)點(diǎn)值滿足以下條件：課室安排項(xiàng)目相等、課室功能相等、教室的可用周數(shù)大于等于課程班所需要的面授周數(shù)。如果條件成立，生成安排時(shí)間和分裂教室結(jié)點(diǎn)。

對(duì)第四步操作的說明：

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

2）把排課結(jié)果寫入到（教學(xué)計(jì)劃實(shí)施表）T_jxTeachImplement表中。

4 算法流程圖

4.1 排課系統(tǒng)數(shù)據(jù)流圖

圖4-1 排課系統(tǒng)數(shù)據(jù)流圖

4.2 排課算法流圖

圖4-2 排課算法流圖

5 結(jié)論

本文所設(shè)計(jì)的基于c/s（Client／Server，客戶/服務(wù)器）模式的教學(xué)排課系統(tǒng)，由客戶應(yīng)用程序Client、服務(wù)器管理程序Server和中間件Middleware3個(gè)部件組成[3]，以Windows Server 2000/XP為網(wǎng)絡(luò)操作系統(tǒng)，以Borland公司的C++ Builder語(yǔ)言開發(fā)客戶端軟件，以SQL Server 2000為后臺(tái)數(shù)據(jù)庫(kù)，具有交互性強(qiáng)，可靠性高，事務(wù)數(shù)據(jù)處理能力強(qiáng)的特點(diǎn)。教學(xué)排課系統(tǒng)全面支持廣域網(wǎng)絡(luò)辦公模式，實(shí)現(xiàn)了排課、調(diào)課、查詢、統(tǒng)計(jì)、打印等基本功能，可大大減少教學(xué)排課的手工勞動(dòng)。

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

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

[3] 部建華，紀(jì)玉玲.基于三層c/s結(jié)構(gòu)教務(wù)管理系統(tǒng)的開發(fā)[J].佳木斯大學(xué)學(xué)報(bào):自然科學(xué)版，2004，22(3)：27-30.

TP393

A

1674-6708（2010）18-0122-02

張志順，講師，工作單位：嘉應(yīng)學(xué)院醫(yī)學(xué)院，從事計(jì)算機(jī)技術(shù)研究與軟件開發(fā)

周銘，職務(wù)：教務(wù)科長(zhǎng)，工作單位：嘉應(yīng)學(xué)院醫(yī)學(xué)院

張晴雯，助理工程師，工作單位：梅縣氣象局，從事計(jì)算機(jī)技術(shù)研究

肖海榮，高級(jí)講師，工作單位：嘉應(yīng)學(xué)院醫(yī)學(xué)院，從事軟件開發(fā)