高校教室排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

摘 要： 本文對在網(wǎng)絡(luò)環(huán)境下計(jì)算機(jī)在排課管理中的應(yīng)用進(jìn)行了研究，實(shí)現(xiàn)了全計(jì)算機(jī)和純網(wǎng)絡(luò)化排課，設(shè)計(jì)了一種高校自動(dòng)排課系統(tǒng)的教室安排算法，對算法中四類不同的教室安排方式結(jié)果的合理性和效率進(jìn)行了詳細(xì)的比較和分析。經(jīng)過對排課問題的研究，利用LINDO for Windows，提出了排課問題的數(shù)學(xué)模型。該模型具有較強(qiáng)的實(shí)用性。

關(guān)鍵詞： 排課系統(tǒng) 輔助功能 教室安排算法 教師安排方式 數(shù)據(jù)庫

一、關(guān)于網(wǎng)絡(luò)環(huán)境下高校教室安排與管理系統(tǒng)

自動(dòng)排課系統(tǒng)是教育信息化的一項(xiàng)重要內(nèi)容。特別是高校自動(dòng)排課系統(tǒng)，由于約束條件繁多、教學(xué)資源要求復(fù)雜，涉及上課時(shí)間、教室、教師、學(xué)生，目前，自動(dòng)排課系統(tǒng)很難達(dá)到由計(jì)算機(jī)自動(dòng)排出課表，需要一定程度的人工輔助完成自動(dòng)排課。通常情況下，自動(dòng)排課系統(tǒng)分為課程的時(shí)間安排子系統(tǒng)和教室安排子系統(tǒng)兩個(gè)部分。課程的時(shí)間安排子系統(tǒng)完成課程的上課時(shí)間安排任務(wù)，教室安排子系統(tǒng)完成課程的教室分配任務(wù)。

本文描述了網(wǎng)絡(luò)環(huán)境下高校教室安排與管理系統(tǒng)（Classroom Allocation and Management System，CAMS）中的教室安排算法。目前，高校教育具有一些新的特點(diǎn)，如招生人數(shù)不斷增加、課程種類繁多、教學(xué)資源緊張、教學(xué)計(jì)劃頻繁變動(dòng)，人工安排容易出現(xiàn)錯(cuò)誤和教室沖突現(xiàn)象。大多數(shù)高校也已經(jīng)廣泛實(shí)行選課制，進(jìn)行網(wǎng)上選課，但是自動(dòng)排課系統(tǒng)的功能仍不完善。CAMS正是為了解決這些問題而提出的，它能為已經(jīng)確定上課時(shí)間的課程合理地分配教室，提高課程安排的靈活性和高效性，實(shí)現(xiàn)自動(dòng)化的教室管理。

同時(shí)，目前很多高校分布多個(gè)校區(qū)，這給自動(dòng)排課系統(tǒng)提出了特殊的要求。本文實(shí)現(xiàn)了一種網(wǎng)絡(luò)環(huán)境下的高校自動(dòng)排課系統(tǒng)中教室安排功能。

二、CAMS中的教室安排算法設(shè)計(jì)

1.CAMS系統(tǒng)總體設(shè)計(jì)

自動(dòng)排課系統(tǒng)由四大模塊構(gòu)成，分別是輸入模塊、排課模塊、查看模塊和打印模塊，自動(dòng)排課系統(tǒng)運(yùn)行體系圖（如圖1所示）。

圖1

（1）輸入模塊

輸入模塊包括輸入教師信息、班級(jí)信息、教室信息、課程信息、制訂開課計(jì)劃、綁定合上班等信息。其中，教師信息寫入數(shù)據(jù)庫的教師信息表中，班級(jí)信息寫入班級(jí)信息表中，教室信息寫入教室信息表中，課程信息寫入課程信息表中，開課計(jì)劃寫入教學(xué)計(jì)劃表中，綁定合上班信息寫入總課程表中。

（2）排課模塊

排課模塊是自動(dòng)排課系統(tǒng)的核心部分，分為自動(dòng)排時(shí)間子模塊和自動(dòng)排教室子模塊。此模塊主要是應(yīng)用一系列規(guī)則、約束條件進(jìn)行排課。

（3）查看模塊

可按照班級(jí)、教室、系、教師和總課程表查看各科課程表。

（4）打印模塊

可按班級(jí)、教室、系、教師和總課程表打印課程表。

2.CAMS中的教室安排算法設(shè)計(jì)

教室安排算法是CAMS的核心，算法設(shè)計(jì)的優(yōu)劣影響教室安排結(jié)果的合理性和系統(tǒng)運(yùn)行效率的高低。

（1）CAMS中教室安排算法的設(shè)計(jì)圖（圖2）

圖2

（2）CAMS中教室安排算法描述

①對課程信息表分類

（1）算法中四類教室安排方式

根據(jù)選課人數(shù)和教室容量的排序方式，算法中存在四類不同的教室安排方式，如表1所示四類教室安排方式。

表1 算法中四類教室安排方式

第Ⅰ類安排方式先安排選課人數(shù)少的課程，從待安排課程的教室集合中搜索第一個(gè)符合要求的教室。第Ⅱ類安排方式先安排選課人數(shù)多的課程，同樣從待安排課程的教室集合中搜索到第一個(gè)滿足條件的教室。兩類安排方式的教室集合中按教室容量升序排列。第Ⅲ類安排方式先安排選課人數(shù)少的課程，從待安排課程的教室集合中搜索第一個(gè)不滿足條件的教室，將前一個(gè)教室安排到該課程。第Ⅳ類安排方式先安排選課人數(shù)多的教室，搜索方法和第Ⅰ類，第Ⅱ類相同。兩類安排方式的教室集合中按教室容量降序排列。

（2）四類安排方式的合理性比較和效率分析

表（2）中的數(shù)據(jù)是根據(jù)某高校中一學(xué)院2006—2007年下學(xué)期課表安排所選出的數(shù)據(jù)。

①課程上課時(shí)間沖突不明顯情況下合理性和效率分析

第Ⅰ、Ⅱ兩類教室安排方式合理性比較理想，安排過程中需要比較的次數(shù)多，算法效率低；第Ⅳ類教室安排方式結(jié)果中容易出現(xiàn)選課人數(shù)少的課程安排到大容量教室，造成教室資源浪費(fèi)，需要比較的次數(shù)多，合理性和算法效率都不理想。

②課程上課時(shí)間相互沖突情況下合理性比較和效率分析

對Ⅰ、Ⅱ兩類教室安排方式比較和分析。從合理性角度分析，對已安排課程，第Ⅰ類安排結(jié)果中教室平均利用率為64.1%，第Ⅱ類安排結(jié)果中教室平均利用率為75.1%（如表2教室利用率），第Ⅱ類合理性優(yōu)于第Ⅰ類；對于未安排課程，第Ⅰ類安排結(jié)果中未安排課程選課人數(shù)多，人工安排困難，而第Ⅱ類教室安排方式的結(jié)果中未安排課程選課人數(shù)相對較少，容易人工安排，第Ⅱ類優(yōu)于第Ⅰ類；第Ⅱ類教室安排方式缺點(diǎn)是容易出現(xiàn)選課人數(shù)少的課程安排到大容量教室的現(xiàn)象（如表2安排結(jié)果）。從算法效率角度（比較次數(shù)）分析，兩類安排方式比較次數(shù)相差較少（如表2比較次數(shù)），都需要比較22次，算法效率相同。

表2 課程上課時(shí)間相互沖突下四類安排方式結(jié)果比較和效果分析

第Ⅰ、Ⅲ兩類教室安排方式比較和分析。從合理性角度分析，兩類安排方式的教室利用率均為64.1%（如表2教室利用率），利用率低；未安排教室的課程選課人數(shù)多，合理性較差。從算法效率角度（比較次數(shù)）分析，第Ⅰ類需要比較22次，第Ⅲ類需要比較21次，比較次數(shù)增多（如表2比較次數(shù)），算法效率降低，第Ⅲ類安排方式優(yōu)于第Ⅰ類。

第Ⅱ、Ⅳ兩類教室安排方式比較和分析。從合理性角度分析，對于平均利用率，第Ⅱ類安排方式結(jié)果中教室平均利用率未75.1%，第Ⅳ類教室平均利用率為72.7%，平均利用率相當(dāng)；對于每個(gè)教室利用率，第Ⅱ類教室利用率波動(dòng)范圍大，第Ⅳ類波動(dòng)較小，第Ⅳ類合理性優(yōu)于第Ⅱ類。從算效率角度（比較次數(shù)）分析，第Ⅳ類比較25次，第Ⅱ類比較22次，比較次數(shù)增多（如表2比較次數(shù)），算法效率降低，第Ⅱ類優(yōu)于第Ⅳ類。

從合理性角度分析，第Ⅳ類教室平均利用率高，每個(gè)教室利用率穩(wěn)定，合理性較好；第Ⅰ、Ⅲ兩類合理性最差；第Ⅱ類教室平均利用率高，缺點(diǎn)表現(xiàn)為選課人數(shù)少的課程容易安排到大容量教室，每個(gè)教室利用率波動(dòng)范圍大，合理性劣于第Ⅳ類。從算法效率角度分析，第Ⅰ類算法效率高；第Ⅳ類效率較低[14][15]。

（3）CAMS中教室安排算法的安排方式選擇

通常情況下，選擇第Ⅰ類或第Ⅱ類作為教室安排方式比較理想；第Ⅲ類教室安排方式比較次數(shù)多，算法效率低；第Ⅳ類教室安排方式容易造成教室資源沖突和浪費(fèi)。

CAMS中針對實(shí)際選課數(shù)據(jù)和教室資源數(shù)據(jù)情況，選擇第Ⅱ類作為教室安排方式，安排結(jié)果中未安排課程的選課人數(shù)少，人工安排和處理容易實(shí)現(xiàn)。

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

（1）程序的設(shè)計(jì)及實(shí)現(xiàn)

由于CAMS系統(tǒng)還存在一些缺陷，因此，需要建立一個(gè)算法，才能使這個(gè)系統(tǒng)更加完善。首先，給出運(yùn)用LINDO軟件編寫所需要的一些數(shù)據(jù)。本程序的編寫是根據(jù)線性規(guī)劃的數(shù)學(xué)模型進(jìn)行編寫的。

表三 待排的課程

表四 待排的教室

應(yīng)用LINDO軟件，對已經(jīng)安排好上課時(shí)間的課程進(jìn)行教室安排，其主要因素有2個(gè)，即教室容量RONG和上課人數(shù)R。其目標(biāo)函數(shù)是使該時(shí)刻教室的利用率達(dá)到最優(yōu)。這就類似于線形規(guī)劃中的指派問題。下表是一些數(shù)據(jù)準(zhǔn)備：

其中，x1～x81是按照以行為順序定義的變量。

上表字體加粗部分即為教室達(dá)到最佳利用率的高校排課。

5.結(jié)論

自動(dòng)排課系統(tǒng)一直是高校教務(wù)管理中難以解決的問題，涉及整數(shù)規(guī)劃、圖論、分支定界技術(shù)及模擬退化法等方法和技術(shù)，國內(nèi)外很多研究人員仍在從事這方面的研究工作。

本文設(shè)計(jì)和實(shí)現(xiàn)了網(wǎng)絡(luò)環(huán)境下高校自動(dòng)排課系統(tǒng)中的教室安排算法，對算法中四種不同類型教室安排方式的合理性和運(yùn)行效率進(jìn)行了比較和分析。CAMS已經(jīng)在某些高校的教學(xué)實(shí)踐中發(fā)揮了重要的作用。

由于高校信息化沒有統(tǒng)一的標(biāo)準(zhǔn)，每個(gè)高校的實(shí)際情況存在較大差異，因此CAMS在其他高校中的推廣需要開發(fā)一個(gè)簡單的接口。

本系統(tǒng)實(shí)現(xiàn)了對課程的自動(dòng)編排，具有很高的實(shí)用價(jià)值，若對計(jì)算機(jī)自動(dòng)排課的結(jié)果不滿意，則可進(jìn)行手工調(diào)整，并可按照系、班級(jí)、教師和教室打印課程表。自動(dòng)排課系統(tǒng)配合了學(xué)校教學(xué)體制改革的進(jìn)程，更新了教務(wù)管理者的傳統(tǒng)理念，促進(jìn)了教務(wù)管理信息化的發(fā)展。