對(duì)學(xué)分制模式下排課系統(tǒng)的探討

鄒元杰

【摘要】排課問題是一個(gè)多約束、多目標(biāo)的優(yōu)化問題，本文通過對(duì)排課因素和約束條件的深入分析，對(duì)學(xué)分制模式下的排課系統(tǒng)的設(shè)計(jì)提供合理的模型建立。

【關(guān)鍵詞】學(xué)分制模式 排課系統(tǒng)

一、前言

目前高校招生逐年擴(kuò)張，學(xué)生人數(shù)不斷增加，再加上大多數(shù)高校實(shí)行學(xué)分制，課程開設(shè)逐漸向著廣度和深度擴(kuò)展，但學(xué)校的教學(xué)資源及設(shè)備卻得不到及時(shí)補(bǔ)充，這些都給教務(wù)處排課人員造成很大的壓力。單純采用勞動(dòng)強(qiáng)度大、效率低的手工排課，已成為提高教學(xué)管理質(zhì)量的瓶頸。隨著計(jì)算機(jī)在教學(xué)工作中的普及應(yīng)用，利用計(jì)算機(jī)進(jìn)行自動(dòng)排課已經(jīng)成為一個(gè)重要的研究課題。

二、排課因素分析

排課工作是教學(xué)工作順利進(jìn)行的基礎(chǔ)工作，排課問題涉及到的因素也幾乎是全校性的。從排課可能引起的沖突的角度來考慮，排課涉及到的因素如下：

（1）時(shí)間因素。在排課問題中涉及到的時(shí)間因素主要有學(xué)年、學(xué)期、周、天、時(shí)段、節(jié)次等。一般我們按照周課表來上課，從開學(xué)第一周到第N周，高校每學(xué)期上課18周。一周上課天數(shù)M≤7，一般學(xué)校一周上課5天。每天上午下午晚上各分兩個(gè)時(shí)間段（片），每個(gè)時(shí)間段兩節(jié)課。這樣一周有30個(gè)時(shí)間段。

（2）課程因素。課程有課程編號(hào)、課程名稱、課程的周學(xué)時(shí)、課程學(xué)分、課程對(duì)教室類型的要求、所屬學(xué)院等。每門課程可以有指定的老師授課，也可以沒有。課程因素還包括開設(shè)的班級(jí)數(shù)及課程開設(shè)的校區(qū)等。

（3）教室因素。每個(gè)教室都有教室編號(hào)，教室代號(hào)及所屬的教學(xué)區(qū)域。每個(gè)教室都有教室類型，教室類型包括普通教室、多媒體教室、語音教室、實(shí)驗(yàn)室、機(jī)房、體育館等。每個(gè)教室都有一定的容量，教室的容量必須不小于上課的人數(shù)。

（4）教師因素。每個(gè)教師都有自己的編號(hào)及姓名，每個(gè)教師都隸屬于一個(gè)學(xué)院，教師可以對(duì)上課時(shí)間提出自己的特殊要求。同一時(shí)間老師只能上一個(gè)教學(xué)班的課。

（5）班級(jí)因素。本文所涉及的班級(jí)均指的是教學(xué)班（選課班或行政班）。如前面的分析，教務(wù)處下達(dá)的教學(xué)任務(wù)書里規(guī)定了開設(shè)的課程名稱、班別、開設(shè)的校區(qū)等。其中課程名稱，班別，校區(qū)編號(hào)唯一決定一個(gè)選課班。每個(gè)選課班都有一個(gè)的最大選課人數(shù)的限制。

三、排課的約束條件

排課問題中，主要任務(wù)是將班級(jí)、教師、課程安排在一周內(nèi)某一不發(fā)生沖突的時(shí)間和教室，保證課表在時(shí)間的分配上符合一切共性（時(shí)間上不存在沖突）和個(gè)性（不與老師的特殊時(shí)間要求沖突）的要求，在此基礎(chǔ)上，使其安排在各個(gè)目標(biāo)上盡量達(dá)到最優(yōu)。

一張可行的課表首先要滿足排課因素的約束。這里的約束條件主要是避免沖突。只有在滿足全部約束條件和避免所有沖突的基礎(chǔ)上，才能保證整個(gè)教學(xué)計(jì)劃合理正常進(jìn)行。對(duì)教師、班級(jí)、課程、時(shí)間、教室等幾部分資源進(jìn)行最優(yōu)化配置，才能保證排課的順利完成以及充分發(fā)揮各個(gè)資源的優(yōu)勢(shì)以達(dá)到提高管理水平和教學(xué)質(zhì)量的目的。

根據(jù)是否必須滿足，我們可以將約束條件分為硬約束和軟約束。硬約束是指教師、班級(jí)、教室、校區(qū)在時(shí)空概念上發(fā)生了不可能發(fā)生的事情，也就是發(fā)生了沖突。它是在排課過程中需要滿足的最基本的約束條件，是排課時(shí)必須遵循的原則，否則將會(huì)導(dǎo)致排課結(jié)果無意義。軟約束則是指排課過程中若滿足則更佳，不能滿足也不影響教學(xué)的開展的約束條件。它能夠使課表更加合理，更加具有人性化、，它影響排課結(jié)果的好壞。

通常，排課方案的標(biāo)準(zhǔn)有多個(gè)，以下是按照一般高校校情制定的約束條件。

（1）硬性約束條件：①同一時(shí)間同一班級(jí)只能上一門課；②同一時(shí)間同一教室只能上一門課；③同一時(shí)間同一教師只能上一門課；④教室的容量必須不小于或等于實(shí)際上課的人數(shù)；⑤所分配的教室類型必須與課程所要求的教室類型一致；⑥課程必須安排在教學(xué)任務(wù)書所規(guī)定的校區(qū)。

（2）軟性約束條件：①每個(gè)時(shí)間段安排的課程數(shù)盡量均勻；② 一周的課表中每個(gè)上課時(shí)間都有一定的優(yōu)度，盡量將課程安排在優(yōu)度高的時(shí)間段；③一門課程的多次上課的時(shí)間盡量間隔并分布均勻；④教室容量適中，以充分利用教室；

四、排課系統(tǒng)中的算法設(shè)計(jì)

（一）教室調(diào)度算法

教室信息表用來記錄教室編號(hào)、類型、容量。為了使教室資源得到最好的利用，在排課之前，先利用排序函數(shù)對(duì)教室信息表按教室容量進(jìn)行升序排序。在為課程分配教室時(shí)，從教室信息表的第一條記錄開始檢索，從小到大依次匹配，匹配成功則返回該教室編號(hào)。這樣可以減少教室的浪費(fèi)，除非沒有小教室，只有大教室。教室調(diào)度算法具體描述如下：①初始化i=0，countfalse=0（記錄失敗次數(shù)）；②判斷i是否小于該校區(qū)教室的總數(shù)，若不小于則結(jié)束，沒有找到要求的教室，提示錯(cuò)誤；③判斷第i個(gè)教室的教室類型、容量是否符合要求，若不符合，轉(zhuǎn)⑥；④判斷countfalse是否小于50，若小于，判斷當(dāng)前時(shí)間下，該教室是否可用；若可用，轉(zhuǎn)⑤；否則重新產(chǎn)生一個(gè)可用的時(shí)間（該時(shí)間老師沒有安排課程），countfalse=countfalse+1，轉(zhuǎn)④；⑤判斷教室已占用的時(shí)間段數(shù)目是否小于20，若小于，則教室i在該時(shí)間段被分配且重置countfalse=0；否則轉(zhuǎn)⑥；⑥i=i+1，轉(zhuǎn)②。

該算法可以有效避免一次判斷時(shí)，某時(shí)間段一個(gè)教室不可用則該教室不可用的判斷，在嘗試50次后如果該教室仍不可用，則我們可以認(rèn)為該教室基本上在每個(gè)時(shí)間段都被安排了課，則選擇下一個(gè)教室。同時(shí)，一個(gè)教室可用，但是這個(gè)教室在30個(gè)時(shí)間段中已經(jīng)安排了20或更多個(gè)時(shí)間段，則說明該教室已經(jīng)負(fù)荷很重，若再給這個(gè)教室安排課程，很容易出現(xiàn)教室利用的沖突。為了避免這種情況的發(fā)生，如果某教室被安排的時(shí)間段超過20，則我們不再為該教室安排課程。

（二）沖突檢測(cè)算法

在初始化課表時(shí)，產(chǎn)生的每一個(gè)課表均是滿足所有硬性約束的可行課表。但是在進(jìn)行交叉操作室，我們交換交叉點(diǎn)處兩個(gè)課程的上課時(shí)間，其他不變。這樣可能造成同一時(shí)間同一教師只能上一門課的約束。所以這里的沖突檢測(cè)函數(shù)只要檢測(cè)同一時(shí)間同一教師是否只上一門課。

①初始化i=0；②判斷i是否小于課程總數(shù)，是則結(jié)束，沒有沖突；③初始化j=i+1；④判斷j是否小于課程總數(shù)，若不小于，則轉(zhuǎn)⑧；⑤比較課程i與課程j的教師是否相同，相同則轉(zhuǎn)⑦；⑥j=j+1，轉(zhuǎn)④；⑦判斷課程i與課程j的時(shí)間片是否有相同的，有則結(jié)束，返回沖突；⑧i=i+1，轉(zhuǎn)②。