對學分制模式下排課系統的探討

鄒元杰

【摘要】排課問題是一個多約束、多目標的優化問題，本文通過對排課因素和約束條件的深入分析，對學分制模式下的排課系統的設計提供合理的模型建立。

【關鍵詞】學分制模式 排課系統

一、前言

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

二、排課因素分析

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

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

（2）課程因素。課程有課程編號、課程名稱、課程的周學時、課程學分、課程對教室類型的要求、所屬學院等。每門課程可以有指定的老師授課，也可以沒有。課程因素還包括開設的班級數及課程開設的校區等。

（3）教室因素。每個教室都有教室編號，教室代號及所屬的教學區域。每個教室都有教室類型，教室類型包括普通教室、多媒體教室、語音教室、實驗室、機房、體育館等。每個教室都有一定的容量，教室的容量必須不小于上課的人數。

（4）教師因素。每個教師都有自己的編號及姓名，每個教師都隸屬于一個學院，教師可以對上課時間提出自己的特殊要求。同一時間老師只能上一個教學班的課。

（5）班級因素。本文所涉及的班級均指的是教學班（選課班或行政班）。如前面的分析，教務處下達的教學任務書里規定了開設的課程名稱、班別、開設的校區等。其中課程名稱，班別，校區編號唯一決定一個選課班。每個選課班都有一個的最大選課人數的限制。

三、排課的約束條件

排課問題中，主要任務是將班級、教師、課程安排在一周內某一不發生沖突的時間和教室，保證課表在時間的分配上符合一切共性（時間上不存在沖突）和個性（不與老師的特殊時間要求沖突）的要求，在此基礎上，使其安排在各個目標上盡量達到最優。

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

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

通常，排課方案的標準有多個，以下是按照一般高校校情制定的約束條件。

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

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

四、排課系統中的算法設計

（一）教室調度算法

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

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

（二）沖突檢測算法

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

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