探究排課問題中約束條件的解決方案

李娟

[摘要] 課表編排實(shí)際上就是一個(gè)組合規(guī)劃問題，也就是將時(shí)間、課程、教師、教室和學(xué)生這幾點(diǎn)相結(jié)合的過程。排課過程中的首要問題是解決沖突問題，也就是教師、教室和學(xué)生之間的安排要合理，不能產(chǎn)生沖突，排課算法的優(yōu)劣不僅僅在于它是否滿足了所有的硬約束條件，還要看它是否能滿足盡可能多的軟約束條件。滿足的軟約束條件越多，排課的效果就越好。

[關(guān)鍵詞] 排課；沖突；約束；回溯算法

[DOI] 10.13939/j.cnki.zgsc.2015.24.149

為了避免沖突，我們在排課時(shí)設(shè)定了不同的約束條件，這樣才能保證教學(xué)T作的正常運(yùn)行，例如一個(gè)教學(xué)班在同一時(shí)間內(nèi)只能上一門課，一名教師在同一時(shí)間只能給一個(gè)班上課（合班課除外）。設(shè)計(jì)排課算法的重點(diǎn)是對教師、時(shí)間、教室、課程等資源進(jìn)行組合優(yōu)化，并能夠充分發(fā)揮各種資源的優(yōu)勢來避免沖突的發(fā)生。這樣才能取得最好的排課效果。

在實(shí)際計(jì)算的過程中每個(gè)約束條件都會(huì)被賦予一個(gè)優(yōu)先級別，優(yōu)先級別高的約束條件要首先滿足，然后再考慮優(yōu)先級別低的約束條件。在這里，約束條件被分為三類：強(qiáng)制約束條件、特殊優(yōu)先約束條件和相對約束條件，這三種約束條件的優(yōu)先級別依次降低。

1 強(qiáng)制約束條件

強(qiáng)制約束的條件在時(shí)間上是相同的，即課程安排的時(shí)間單元是相同的。在這里強(qiáng)制約束條件包括三個(gè)方面的內(nèi)容：

第一，教師約束，在同一時(shí)間，同一教師只能安排一門課程。

第二，班級約束，在同一時(shí)間，同一班級只能安排一門課程。

第三，教室約束，在同一時(shí)間，同一教室只能安排一門課程。

2 特殊優(yōu)先約束條件

第一，某一班級或某一教師的上課時(shí)間和地點(diǎn)是國定的。比如設(shè)置某個(gè)教室或?qū)嶒?yàn)室在每周某天上午或下午的某節(jié)課上某門課程或?qū)嶒?yàn)課等等。第二，要預(yù)先設(shè)定某位教師上哪些課程。第三，某些教師是否有特殊的授課安排或其他特殊要求，這些信息都要存放在一個(gè)獨(dú)立的特殊數(shù)據(jù)表中特殊優(yōu)先約束條件的優(yōu)先級別僅次于強(qiáng)制約束條件。3相對約束條件

排課時(shí)強(qiáng)制約束條件是在排課過程中所必須滿足的條件，但不是全部條件，在排課過程中還可能產(chǎn)生一些不確定性的因素，我們稱之為相對約束條件，這些約束條件很難具體把握，不同的學(xué)校和條件下，這些約束條件是不同的，一般我們由一些對學(xué)校情況比較了解的老師來制定，在滿足了這些相對約束條件之后可以在一定程度上提高教師時(shí)間和教室的利用率，從而提高學(xué)校的教學(xué)效率。

排課系統(tǒng)最關(guān)鍵的部分就是處理排課問題的算法問題。本文采用回溯算法來實(shí)現(xiàn)排課，在具體實(shí)現(xiàn)過程中將優(yōu)先級與回溯算法相結(jié)合。

3.1 回溯法的前進(jìn)限制條件

（1） 為了方便老師、學(xué)生，同一班級的不同課程課盡量安排在同一個(gè)教室授課；

（2） 同一班級的同一門課如果周課時(shí)數(shù)超過兩次時(shí)間間隔要盡量長，以免在排課中產(chǎn)生沖突。

（3） 同一教師如果給不同的班級上課，上課時(shí)間要盡量分散，不要太集中，以免影響教學(xué)效果；

（4） 充分利用教室資源，人數(shù)少的班級用容量比較小的教室上課，人數(shù)多的班級用容量大的教室上課，以免資源浪費(fèi)。

3.2 回溯法的回溯條件

首先建立一個(gè)按照一定順序的班級數(shù)組列表名稱為ClassArrav的類，然后根據(jù)不同的順序，再建立一個(gè)科目列表，列表的名稱可以白定義，例如SuhjectArray。再按照不同的順序建立一個(gè)關(guān)于時(shí)間的列表，列表名稱白定義，例如PeriodArray。然后從班級列表中取出每類Clas-sArray。然后再從時(shí)間列表中取出一段時(shí)間，在這里的整個(gè)過程是：先嘗試在檢查最后產(chǎn)生回溯。對于某個(gè)類第n個(gè)課時(shí)：開始從SubjectArray主體中取出插入，選擇科目授課教師進(jìn)行核查，如果檢查成功，位列n+1類，如果不通過，換下一個(gè)科目取代……；若所有科目變化完仍然無法通過驗(yàn)證，則有是一個(gè)錯(cuò)誤的，回到第n-1節(jié)課，進(jìn)行課程的重新選擇和排列。重復(fù)上面的過程。

排課能否成功所排課程在時(shí)間上是否合理的關(guān)鍵在于編排課程的先后順序，這就決定了優(yōu)先級在排課過程中所占的地位。優(yōu)先級的確定直接關(guān)系到排課的結(jié)果，所以對優(yōu)先級的設(shè)置原則做了如下規(guī)定：

（1） 根據(jù)課程的安排，必修課的優(yōu)先級別設(shè)置要高于選修課，公共課的優(yōu)先級別設(shè)置要高于必修課；

（2） 學(xué)校里不同的課程對學(xué)生的認(rèn)知要求不同，課時(shí)數(shù)也不同，總課時(shí)多的課程的優(yōu)先級別高于總課時(shí)數(shù)少的課程：

（3） 學(xué)校里，并不是所有課程都要求學(xué)生學(xué)習(xí)，有的課程學(xué)生可以選擇是否選修該門課程，那么就出現(xiàn)了不同課程上課人數(shù)不同，上課人數(shù)多的課程的優(yōu)先級別高于上課人數(shù)少的課程；

（4） 一個(gè)班級在一個(gè)學(xué)期要求安排若干門課程，但是由于課程的難易程度不同，學(xué)校的要求也就不同，所以不同的課程在一學(xué)期內(nèi)的課時(shí)數(shù)也是不同的，那么一周課時(shí)數(shù)多的課程的優(yōu)先級就要高于一周內(nèi)課時(shí)數(shù)少的課程；這樣才能符合排課的原理，排出的課程才能合理；

（5） 在學(xué)校里，有的課程可能不是在任何時(shí)間都可以上課的，那么對時(shí)間有特殊要求的課程的優(yōu)先級別高于對時(shí)間沒有特殊要求的課程；

（6） 在學(xué)校里，有的課程可能對場地有特殊的要求，例如試驗(yàn)實(shí)訓(xùn)課要求在實(shí)驗(yàn)室會(huì)實(shí)訓(xùn)室上課，那么在授課場地上有特殊要求的課程的優(yōu)先級高于對場地沒有要求的課程；

（7） 有的課程可能還對教師有特殊的要求，那么對教師有特殊要求的課程的優(yōu)先級高于對教師沒有要求的課程的優(yōu)先級別。