多約束條件下高校排課系統(tǒng)的算法研究

2008-12-31 00:00:00陳興剛孟祥婧李靜宋劍

電腦知識(shí)與技術(shù) 2008年27期

摘要：高校排課問題是典型的組合優(yōu)化和NP-難問題。目前由于高校的擴(kuò)招和合并趨勢(shì)，高校的規(guī)模越來越大，辦學(xué)資源日趨緊張，針對(duì)教師和學(xué)生在上課時(shí)間、上課地點(diǎn)等問題的安排上所受到的約束條件也越來越多的現(xiàn)實(shí)，該文擬采用擬人策略對(duì)排課資源和約束條件進(jìn)行分析，然后重點(diǎn)探討在排課中常用的遺傳算法。

關(guān)鍵詞：排課；NP；多約束條件；遺傳算法

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)27-1958-02

Research on the Algorithms of the Course Scheduling System for College under the Multi-constrained Conditions

CHEN Xing-gang， MENG Xiang-jing， LI Jing， SONG Jian

(Electronic Science and Information Technology Institute， Guizhou University， Guiyang 550025 China)

Abstract：College course arrangement is a typical combinatorial optimization and NP-hard problem. As the current College Enrollment Expansion and consolidation trend， increasing the size of colleges and universities， the growing tension school resources， for teachers and students during school hours， school locations and other issues on the arrangements being bound by the conditions of a growing number of reality， This paper will adopt strategies to be one of the course arrangement of resources and constraints analysis， and then focus on the course arrangement commonly used in genetic algorithm.

Key words：course scheduling; NP; multi-constrained conditions; GA

排課是高校教學(xué)管理中的一項(xiàng)重要而且難度和復(fù)雜度都極高的基本工作。特別是近年來，隨著我國高校的擴(kuò)招和合并，學(xué)校的教學(xué)資源（如教室、實(shí)驗(yàn)室、語音室等）愈顯緊張；同時(shí)，在學(xué)分制的制度下，課程的類別越分越多，有公共必修課、公共選修課、專業(yè)基礎(chǔ)課、專業(yè)必修課、專業(yè)選修課等等；再者，上課的教師也會(huì)有一些特殊情況需要考慮。這樣一來，排課人員在排課時(shí)倍感棘手，以至于開學(xué)后因排課問題還會(huì)影響到教學(xué)的正常進(jìn)行。

目前，國內(nèi)的許多高校都引進(jìn)了不同智能化程度的排課軟件，然而，其應(yīng)用的效果都有些不盡如人意，雖然耗費(fèi)了教務(wù)處工作人員大量的時(shí)間和精力，但遺留下的問題還是很多。

下面我們基于人工排課的宏觀指導(dǎo)思想，列出約束限制條件，采用遺傳算法，進(jìn)行多輪次掃描計(jì)算，以改變目前的排課系統(tǒng)沖突多、調(diào)整應(yīng)變能力弱，排課時(shí)間長的問題，從而求得合理性解。

1 排課時(shí)所受的約束限制條件

高校排課問題，它要求將課程、教師、班級(jí)安排在一個(gè)有限的時(shí)間和空間當(dāng)中去，要求避免沖突且盡量滿足一些其它條件，這實(shí)際上是五個(gè)相互制約的因素的組合優(yōu)化問題。1975年，美國S.Even等人證明了高校排課問題也是一個(gè)NP(Non-deterministic Polynomial)難問題，即多項(xiàng)式復(fù)雜程度的非確定性問題，即找不到多項(xiàng)式時(shí)間求解算法。具體到高校排課系統(tǒng)的算法上，五個(gè)相互制約的因素它們所受到的約束限制條件有：

1) 不能在同一時(shí)間給同一位教師安排多個(gè)班級(jí)課程(合班除外) 或同時(shí)講授多門課程。

2) 不能在同一時(shí)間給同一個(gè)教室安排多個(gè)班級(jí)上課(合班除外) 或多位教師授課。

3) 不能在同一時(shí)間給同一個(gè)班級(jí)安排多門課程或同時(shí)在不同的教室上課。

4) 不能在安排教室時(shí)使教室容納人數(shù)小于上課學(xué)生人數(shù)。

5) 對(duì)于需要特殊場(chǎng)所的課程，如體育課、實(shí)驗(yàn)課、語音教室等，應(yīng)安排相應(yīng)地點(diǎn)或?qū)嶒?yàn)室上課。

以上是高校排課時(shí)必須滿足的條件，否則無法進(jìn)行正常教學(xué)。在能夠進(jìn)行正常教學(xué)的情況下我們還應(yīng)考慮到教學(xué)效果，學(xué)生學(xué)習(xí)效率，教師、學(xué)生的便利等其他因素，因此，還要考慮一些盡量去實(shí)現(xiàn)的約束條件，這包括：

1) 一門課程的幾次課在一周之內(nèi)應(yīng)間隔排列。

2) 上課人數(shù)盡量接近教室容量。

3) 排課時(shí)可注意文科類課程和理科類課程交叉安排，避免使學(xué)生產(chǎn)生倦怠感，有利于提高學(xué)習(xí)效率。

4) 體育課最好不要安排在一天中的第1-2節(jié)，并且在體育課后最好不要再安排其它課程，保證教學(xué)效果。

5) 同一班級(jí)連續(xù)兩次講課之間更換教室盡可能少；同一課程的不同講次盡量不換教室。

6) 不要在一天中給教師或?qū)W生安排太多課程，最好不要連續(xù)上課超過 6 節(jié)，有利于提高教學(xué)效果和學(xué)習(xí)效率。

2 排課問題描述

在排課問題中，我們的基本任務(wù)是將班級(jí)、教室、課程、教師安排在一周內(nèi)且不發(fā)生時(shí)間沖突[2]。據(jù)此，對(duì)這五個(gè)相互制約的因素我們給出如下的描述：

學(xué)校有R間教室，C個(gè)班，S門課程，T位教師，P個(gè)時(shí)間段。

1) 教室集合R（R1，R2，…，Rr），每間教室分別可容納（X1，X2，…，Xy）人；

2) 班級(jí)集合C（C1，C2，…，Cc），每個(gè)班級(jí)分別有（K1，K2，…，Kc）人，其中有x個(gè)班級(jí)上合班課；

3) 課程集合S（S1，S2，…，Ss），每門課對(duì)應(yīng)Ci個(gè)班，1位教師，（1≤Ci

4) 教師集合T（T1，T2，…，Tt），每位教師對(duì)應(yīng)Sm門課，Cc個(gè)班，（1≤Sm

5) 時(shí)間集合P(P1，P2，…，Pp)，假設(shè)一周上五天課，每天分為五個(gè)教學(xué)單元，每個(gè)單元為2個(gè)課時(shí)，即上午2個(gè)，下午2個(gè)，晚上1個(gè)，則時(shí)間集合包含25個(gè)時(shí)間段。如11代表周一第一個(gè)教學(xué)單元，即周一1、2節(jié)，12代表周一第二個(gè)教學(xué)單元，即周一3、4節(jié)，以此類推，這些時(shí)間段構(gòu)成一個(gè)時(shí)間集合P(11，12，13，…，55)。

3 算法研究

從20世紀(jì)50年代以來，國際上就有人著手研究應(yīng)用計(jì)算機(jī)進(jìn)行排課的問題。國外的研究表明，解決大規(guī)模的排課問題單純依靠數(shù)學(xué)方法是行不通的，進(jìn)入20世紀(jì)90年代以后，國外對(duì)排課問題的研究仍然十分活躍。國外目前較多采用著色算法、數(shù)學(xué)方法、模擬退火技術(shù)、禁忌算法、局部優(yōu)化算法和遺傳算法等。

3.1 遺傳算法

遺傳算法(Genetic Algorithm，GA)是一種有效的解決最優(yōu)化問題的方法或計(jì)算模型。遺傳算法的研究歷史比較短，它出現(xiàn)在20世紀(jì)六、七十年代，主要是由美國Michigan大學(xué)教授John Holland與其同事、學(xué)生們通過對(duì)生物進(jìn)化過程進(jìn)行模擬，研究形成的一個(gè)較完整的理論和一種全新的概率優(yōu)化方法。John Holland提出這一算法的最初目的是研究自然系統(tǒng)的自適應(yīng)行為，并用于設(shè)計(jì)具有自適應(yīng)功能的軟件系統(tǒng)。隨后經(jīng)過20余年的發(fā)展，計(jì)算智能化己經(jīng)作為人工智能研究的一個(gè)重要方向，以及后來的人工生命研究興起，使遺傳算法受到廣泛的關(guān)注。目前，遺傳算法作為具有系統(tǒng)優(yōu)化、適應(yīng)和學(xué)習(xí)的高性能計(jì)算和建模方法的研究漸趨成熟。

GA算法具有下述特點(diǎn)：

1) GA是對(duì)問題參數(shù)的編碼組進(jìn)行進(jìn)貨，而不是直接對(duì)參數(shù)本身。

2) GA的搜索是從問題解的編碼組開始搜索，而不是從單個(gè)解開始。

3) GA使用目標(biāo)函數(shù)值（適應(yīng)度）這一信息進(jìn)行搜索，而不需導(dǎo)數(shù)等其他信息。

4) GA算法使用的選擇、交叉、變異這三個(gè)算子都是隨機(jī)操作，而不是確定規(guī)則。

3.2 算法描述

利用遺傳算法解最優(yōu)化問題，首先應(yīng)對(duì)可行域中的點(diǎn)進(jìn)行編碼（一般采用二進(jìn)制編碼），然后在可行域中隨機(jī)挑選一些編碼組作為進(jìn)化起點(diǎn)的第一代編碼組，并計(jì)算每個(gè)解的目標(biāo)函數(shù)值，也就是編碼的適應(yīng)度。接著就像自然界中一樣，利用選擇機(jī)制從編碼組中隨機(jī)挑選編碼作為繁殖過程前的編碼樣本。選擇機(jī)制應(yīng)保證適應(yīng)度較高的解能夠保留較多的樣本；而適應(yīng)度較低的解則保留較少的樣本，甚至被淘汰。在接下去的繁殖過程中，遺傳算法提供了交叉和變異兩種算子對(duì)挑選后的樣本進(jìn)行交換。交叉算子交換隨機(jī)挑選的兩個(gè)編碼的某些位，變異算子則直接對(duì)一個(gè)編碼中的隨機(jī)挑選的某一位進(jìn)行反轉(zhuǎn)。這樣通過選擇和繁殖就產(chǎn)生了下一代編碼組。重復(fù)上述選擇和繁殖過程，直到結(jié)束條件得到滿足為止。進(jìn)化過程最后一代中的最優(yōu)解就是用遺傳算法解最優(yōu)化問題時(shí)所得到的最終結(jié)果。