李 彬，李 楓

（湖南工學(xué)院 數(shù)理學(xué)院，湖南 衡陽421002）

近年來，高校規(guī)模越來越大，課程設(shè)置數(shù)量越來越多，各高校對排課的個性化需求也越來越多，同時教室以及教師等教學(xué)資源又相對有限，排課問題變得越來越復(fù)雜。從20 世紀50 年代開始，國內(nèi)外研究人員開始關(guān)注這一問題，直到現(xiàn)在依然是研究熱點［1-2］。排課問題在運籌學(xué)中又被稱為時間表問題，已經(jīng)被公認為是NP 難題［2］。近年來很多學(xué)者采用了遺傳算法、禁忌搜索、模擬退火、蟻群算法等啟發(fā)式算法來研究排課問題，在取得豐碩成果的同時也存在不少問題，比如收斂速度慢，由于約束條件多導(dǎo)致啟發(fā)式算法經(jīng)過多次迭代后產(chǎn)生不可行解等等一系列問題［3-8］。文獻［9-10］采用了Lingo 軟件來求解排課問題數(shù)學(xué)模型，總體說來模型規(guī)模相對較小，且數(shù)學(xué)模型通用性與可移植性相對較差。本文通過對排課問題的一些常見約束條件進行適當(dāng)轉(zhuǎn)化，建立了0-1 整數(shù)線性規(guī)劃排課模型，采用Lingo 軟件來求解模型。把求解過程當(dāng)成一黑箱，具體的工作交給Lingo 軟件，以此來彌補啟發(fā)式算法的缺陷。

1 問題提出

某校某學(xué)期需要開設(shè)Ni門課程，該校共有Nj教師來承擔(dān)這些課程，涉及到的教學(xué)班級數(shù)量為Nk，教學(xué)任務(wù)如表1 所示。

表1 教學(xué)任務(wù)表

表中第1 列為該校開設(shè)的Ni門課程的編號，第2 列為該門課程所對應(yīng)的授課教師編號，第3 列為該門課程所對應(yīng)的授課班級編號（暫不考慮合班教學(xué)問題，合班教學(xué)問題將在模型拓展部分進行分析）。為簡單起見，現(xiàn)假定每門課程每周只需要安排一次（每周安排多次的問題將在模型拓展部分進行分析），每周共有Nt個時間段可以安排，該校共有Ns間教室可供安排，問應(yīng)該如何合理進行排課？

2 排課問題數(shù)學(xué)模型

2.1 問題分析

合理排課包括很多方面，首先考慮幾個最基本的硬性約束。由于同一名教師可能承擔(dān)了多門課程，同一班級通常開設(shè)了多門課程，排課必須保證教師的時間不沖突，學(xué)生的時間不沖突，教室不沖突，即每間教室在每個時間段都最多只能安排一門課程。根據(jù)這三個約束條件，建立一個最基本的排課模型。

2.2 符號說明

（1）課程編號為i，i=1，2，…，Ni。

（2）教師編號為j，j=1，2，…，Nj。

（3）班級編號為k，k=1，2，…，Nk。

（4）排課時間段為t，t=1，2，…，Nt。

（5）教室編號為s，s=1，2，…，Ns。

（6）教學(xué)任務(wù)三元集合為U。因教學(xué)任務(wù)已指明每門課程對應(yīng)的教師編號、班級編號等信息，可把教學(xué)任務(wù)表中的每行作為一個元素，得到教學(xué)任務(wù)三元集合U=｛（1，4，2），（2，8，6），（3，6，2），（4，4，3），…｝。教學(xué)任務(wù)三元集合中每一個元素都包含了課程編號以及對應(yīng)的教師與班級編號。構(gòu)造教學(xué)任務(wù)三元集合的目的是為了減少排課決策變量數(shù)量，減少無效約束條件的數(shù)量，為模型求解提供便利。

下文中所涉及的排課決策變量前3 個下標(biāo)所成3 元組必須包含于教學(xué)任務(wù)三元集合中，不再重復(fù)說明。

2.3 模型建立

3 模型求解實例

3.1 中等規(guī)模的問題

取Ni=500，Nj=1 000，Nk=50，Nt=20，Ns=30，利用Matlab 軟件對500 門課程隨機生成教師編號以及對應(yīng)的班級編號，排課時間段取為20 個（每周有5 天可排課，每天有4 個時間段可排課），教室取為30間。在CPU 為AMD A8-5600K 的Win7 系統(tǒng)電腦上，利用Lingo11.0 進行求解，共300 000 變量，約4 000 條約束，大約14 min 得到了可行解。高校院系內(nèi)部的專業(yè)課排課問題規(guī)模與之相當(dāng)，Lingo 可以完成求解。

3.2 更大規(guī)模的問題

當(dāng)把課程數(shù)量、教師數(shù)量、班級數(shù)量、教室數(shù)量分別擴大2 倍再進行求解時，模型規(guī)模已經(jīng)超過Lingo11.0 的內(nèi)存限制，求解失敗，更大規(guī)模問題的求解需要更高性能CPU 以及高版本的Lingo，或者有更好的求解策略。筆者在此提出一種分步排課的策略，例如，可以首先利用Lingo 排定全校各班級的數(shù)學(xué)、計算機、英語等公共課，等這些課程排好后，相關(guān)的排課決策變量就成了常值，模型規(guī)模就大大變小了，再用Lingo 依次對各院系專業(yè)課進行排課。

取Ni=1 000，Nj=200，Nk=100，Nt=20，Ns=70，利用Matlab 軟件對1 000 門課程隨機生成教師編號以及對應(yīng)的班級編號，排課時間段取為20 個，教室取為70 間。分4 次對該問題進行求解，第1 次求解前250 門課程的排課問題；等求解結(jié)束后把相應(yīng)的決策變量的結(jié)果作為約束條件加入模型，然后對前500門課程的排課問題進行求解；如此重復(fù)操作4 次后，就得到了原問題的解。在4 次求解過程中，分別耗時18 min、38 min、70 min、110 min，總計耗時4 h 左右，用時間換空間的策略完成了問題的求解。

4 模型拓展

4.1 教室的容量限制問題

排課過程中，有些教室由于容量限制或其他問題，不適宜把某些課程安排在某些教室，可以在模型中再加入相關(guān)約束條件。例如，教學(xué)任務(wù)編號（3，6，2）不宜安排在8 號教室，則可以加入約束條件?t，x3，6，2，t，8=0。

4.2 課程的排課時間特殊要求

4.3 教師排課時間的特殊要求

某些教師由于公務(wù)原因，某些時段不能排課。例如，教師6 不宜在第4 時間段排課，則加入約束條件?i，k，s，xi，6，k，4，s=0。

4.4 課程每周需要安排多次

4.5 合班教學(xué)問題

很多高校都有合班教學(xué)的現(xiàn)象。假如（2，8，6），（3，6，2）兩教學(xué)任務(wù)中，6 號班級與2 號班級是合班產(chǎn)生的教學(xué)班級，且6 號班級與2 號班級中包含有相同的學(xué)生，那么兩門課程不能安排在同一時間段，

5 小結(jié)

針對排課問題中常見的硬約束、軟約束問題，建立了0-1 整數(shù)線性規(guī)劃模型，模型通用性較強，且非常適合Lingo 軟件編程求解。對中小型規(guī)模問題，可以借助Lingo 方便地進行求解，基本能夠滿足大學(xué)院系內(nèi)部專業(yè)課排課需求。對于更大規(guī)模問題，主要有兩條解決思路：其一可以采用性能更好的電腦、高版本的Lingo 軟件來彌補；其二可以把大問題進行分割、分步驟排課。

本文給出的排課模型中無目標(biāo)函數(shù)，具體應(yīng)用時可根據(jù)學(xué)校的需求加入相關(guān)優(yōu)化目標(biāo)函數(shù)。比如可把排課的分散程度、教師是否連堂等指標(biāo)作為優(yōu)化目標(biāo)等等。超大規(guī)模排課問題以及更多的排課優(yōu)化指標(biāo)問題，值得進一步探索。