面向新高考“3+X”走班制排課的優(yōu)先度算法

儒曼，武迪，張致遠

（1.北京交通大學 電子信息工程學院，北京 100044；2.清華大學 航天航空學院，北京 100084）

0 引言

“新高考”政策下，高中物理、化學、生物、地理、歷史、政治成為選修課，每名學生可任選其中3門作為高考選修課，高考時計入高考總分；其余3門作為會考選修課，只判斷是否合格，而不記入高考總分。在這種情況下，學校勢必要走班管理，即語文、數(shù)學、英語等仍可按照固定班級教學，而選修科目則必須走班教學，以滿足每個學生的選擇。此時，各個學生選課情況不同，需要針對選課情況給出每名學生的“一人一課表”，在學校有限的教學資源下，排課的組合優(yōu)化難度大，傳統(tǒng)的人工排課不再適用，迫切需要一定優(yōu)化策略下的智能排課算法。

一般而言，排課問題是一類NP完全問題，涉及多因素的排列組合優(yōu)化，考慮實際排課需求的約束復雜多變，解空間隨學生人數(shù)的增加而急劇增大。國內外學者應用了多種不同的算法解決排課問題，如遺傳算法[1-2]、蟻群算法[3]、模擬退火算法[4]、整數(shù)規(guī)劃[5]等。這些算法大都應用于傳統(tǒng)的教學模式，即只存在固定班的情況。而在高考改革的新形勢下，需要將走班制納入考量范圍。與傳統(tǒng)的固定班排課不同的是，走班制排課需要制定合理的分班策略。目前采用的分班策略有如下幾種：（1）不走班，縮減原有的20種選課方式，僅挑選出幾種方案供學生選擇。這種策略的優(yōu)點是排課難度降低，但無法滿足學生個性化需求；（2）小走班，如“定兩科走一科”；（3）大走班，即本文所采用的模式：選修課應用走班制，固定課應用傳統(tǒng)排課方式；（4）全走班，即無固定班。相對第三種策略[6-7]，全走班通常需要占用更多的學校教學資源且管理難度更大。

在遺傳算法的基礎上，針對走班制的分班策略，文獻[8]提出了教學班組合的概念，將所有班級分成若干個批次, 每個批次下劃分若干個走班組合以簡化排課過程；文獻[9]從課表時段分配轉為天課時分配，即對每個課程班每天的課時數(shù)目進行決策；文獻[10]采用按選課組合分班，結合遺傳算法解決排課問題。上述方法均假設了一定的人為分班策略，限制了解空間的大小，而且對于教學資源的約束情況考慮較少，在資源緊缺的情況下上述排課算法難以生成排課結果。

本文采用大走班的方式，將選修課時和固定課時分開，著眼于選修課時的排課算法。針對學生的選課情況以及學校的教學資源約束，本文排課算法以優(yōu)先度為指標逐漸構建走班制班級，最終給出一個可行的選修課排課方案。通過設計優(yōu)先度指標自動生成走班制的動態(tài)班級分班結果，無須額外制定分班策略。

1 課時分區(qū)處理

針對新高考“3+X”改革實行的走班制排課，本文將所有教學課時分開處理。第一類是固定課課時區(qū)。所有學生在這些課時中只上語文、數(shù)學、英語、體育、音樂、美術等行政班科目，這一部分與傳統(tǒng)的排課相同，可以用固定課排課方法解決；第二類是選修課課時區(qū)。所有學生在這些課時中只上物理、化學、生物、地理、歷史、政治。此類課時區(qū)又細化為兩類課時區(qū)：1、高考課時區(qū)，即學生選考的科目所在課時；2、會考課時區(qū)，即學生未選考，將參加會考的科目所在課時。換言之，就是所有學生同一時間的上課科目類型相同。

由于課時分區(qū)只是將走班與固定班分開，未改變固定課時總數(shù)，因此課時分區(qū)不會減少固定班排課的節(jié)空間，但這樣的課時分法可以把固定課和選修課分開處理，從而簡化排課過程。本文即針對其中的選修課時區(qū)提出一種能夠得到可行解的算法策略。由于高考課時區(qū)和會考課時區(qū)排課過程相似，以下的數(shù)學模型和算法策略部分只討論高考課時區(qū)排課問題。

2 優(yōu)先度算法

選修課時區(qū)的排課問題是：在有限的教師數(shù)和教室數(shù)的條件下，已知所有學生選課情況，對所有學生的高考課時進行排課并盡可能減少排課失敗人數(shù)。此時，學校的教學資源約束為：選修課各科目教職工人數(shù)，可用于選修課排課的教室總數(shù)及每間教室容量。已知條件為學校的年級課表模板（含課時分區(qū)方案），高考課和會考課每周的課時數(shù)，以及所有學生的6選3情況。

2.1 數(shù)學模型

首先定義高考課課表。每位學生都選擇了三個科目作為選考科目，因此對于同一個學生而言有三類高考課時，對應三門高考課。定義下面的課程矩陣：

下面介紹如何無沖突地將學生有序放入課程表中。課程表需要滿足的硬約束條件如下：

（1）同一時間一個學生不能排兩門課程；

（2）同一時間一個教室不能排兩門課程；

（4）每一課時任一課程學生數(shù)不能超過該教室最大人數(shù)r，即：nij≤r(i=1,2,3;j=1,2,…,m)。

其中本文算法滿足前兩個約束條件。約束（3）為教師約束，它反映了教師資源有限性，為滿足此約束應當盡可能使同一時間科目類別多樣。約束（4）為教室約束，此約束反應了教室空間的有限性，排課時如不能很好地滿足此約束，將增加排課失敗學生的人數(shù)，對后續(xù)排課任務造成障礙。

下面的步驟是向空課表中放置學生。如果無序地放置學生會使算法十分復雜，需要對所有學生進行分類處理，分類的標準是學生選課情況。由于實行走班制的選修課只有六種，因此學生所有的選課情況只有C63=20種。將所有學生先根據(jù)選課情況分為20個集合，再根據(jù)每種情況的學生人數(shù)由大到小對20個集合進行排序。排課時先排人數(shù)多的集合再排人數(shù)少的集合，這樣可以盡可能確保大多數(shù)學生成功排課。對于每個學生來說，需要上的高考課只有三種，分別對應高考課的三類課時。因此對同一個學生來說，可以選擇的方案只有A33=6種。分別對這六種情況進行分析，分析的方法即為計算每種情況的優(yōu)先度，最后將采用優(yōu)先度最高的方案放置學生。放置的方法即為在每個課時查找對應科目的課程，若滿足bi j(r-nij) ＞ 0，則向cij的學生列表中添加此學生。如果沒有找到，新建一個該科目的課程單元并添加。這樣既可以確保同一時間一個學生不排兩門課程，滿足約束（1），又可以確保同一間教室只上一門課，滿足約束（2）。

定義邏輯變量：

其中1表示課時i班級j處的課程科目滿足方案，0表示不滿足方案。學生插入過程如圖1所示。不同顏色代表不同科目，若標1的插入情況表示當前情況，課表每格的數(shù)字代表對應課程的邏輯變量l的邏輯值。則可得出當前情況的科目三個課時組合為A、B、C（如右圖所示），則在課表中對應可插入的位置坐標是：課時1：（1,1）或（1,6），課時2：（2,3）或（2,7），課時3：（3,3）或（3,7）。遍歷所有學生并進行相同操作即可完成課表的生成。

圖1 學生插入過程示意圖

下面確定優(yōu)先度的計算方法。優(yōu)先度是算法的核心，它的定義方法直接決定排課策略的優(yōu)劣。直觀地來看，優(yōu)先度應當與每個課時教室剩余容量有關。因此定義每種方案的剩余量ζ：

由于要盡可能使科目分布均勻，因此教師修正項為負值。因為一般情況下教師資源相對于教室資源更加充裕，所以教師約束要弱于教室約束，因此設定教師約束項加權k在0到1之間，表示其權重小于教室約束。由上式不難看出，在方案給定的情況下，表達式中參數(shù)除k外均為常量。對于不同的初始數(shù)據(jù)，k的值是不同的。需要在算法中不斷改變k的值不斷排課，最終取最優(yōu)解作為最終結果。

2.2 數(shù)學模型

算法除去數(shù)據(jù)輸入和輸出以外共分兩部分，分別是課時生成部分和教師分配部分。課時生成部分算法如圖2所示。其中ε為給定的變化單位，為盡可能減少運算次數(shù)，實際設定變化量ε=-0.01。生成課表時若返回false，則表明該條件下課表生成失敗，立即進入下輪循環(huán)。其中，生成課表的算法策略如圖3所示。

圖2 課時生成算法流圖

圖3 課表生成算法流圖

指定的k值下生成課表后，有可能會出現(xiàn)某些教室學生極少的情況，有時一個教室只有不到10人，形成教室和教師資源浪費[11]。此時應當以停開限度作為標準（學生人數(shù)小于L的課程應當視為停開），令人數(shù)過少的課程停開，然后再嘗試將此課程中的學生添加到其他非停開課程中。即需要完成的操作為：

優(yōu)化過程如圖4所示。A格代表停開課程，B格代表因停開而同時改變學生列表的課程，C格代表插入學生的非停開課程。

圖4 課表優(yōu)化示意圖

優(yōu)化課表的算法策略如圖5所示。

圖5 課表優(yōu)化算法流圖

優(yōu)化后未排入的學生記為排課失敗學生。判斷課表優(yōu)劣的指標為排課失敗人數(shù)，人數(shù)越少課表越好。由于課表優(yōu)化時有可能產生新的停開課程，因此也應將停開課數(shù)作為評價標準，停開課數(shù)越少的課表越好。評價時首先比較兩課表排課失敗人數(shù)，如排課失敗人數(shù)相同，比較停開課數(shù)。將上述算法策略分別運用于高考和會考情形，就可以分別獲得高考和會考課時方案及相應的排課失敗學生列表。教師的分配部分如下：首先，由于已滿足教師約束，即tj≥si j(i=1,2,3;j=1,2,3,4,5,6)，因此一定能成功分配教師。但如果分配時不加策略，將導致教師上課數(shù)不均勻，即同一時間只有某幾科的教師在上課的情況。為確保教師上課數(shù)分配均勻，在隨機分配教師后，在每一個選修科目的教師中查找上課數(shù)最多和最少的教師，將上課數(shù)多的教師的課還給上課數(shù)少的教師。重復上述操作，直至最多和最少相差小于等于1。分別在高考和會考的情況下完成上述操作，即可得到一個教師分配均勻的方案。

3 數(shù)值仿真

3.1 算例設置

本次實驗的目的有兩個：

（1）檢驗算法可行性，依據(jù)實例數(shù)據(jù)給出排課方案。

（2）找到合適的停開限度設置策略并改進算法，并得到較優(yōu)解。

本次實驗采用某校某年級真實選課數(shù)據(jù)，包括1451名學生，選修教師43人，32間教室，每間教室容量55人。其中學生選課結果統(tǒng)計和每科教師人數(shù)如表1所示，此處只列出選擇指定高考課的學生人數(shù)。

表1 實例1原始數(shù)據(jù)表

為證明本系統(tǒng)能夠在學生人數(shù)較少時獲得可行解。本實驗對真實數(shù)據(jù)進行精簡獲得另一份測試數(shù)據(jù)。測試數(shù)據(jù)包括248名學生，選修教師18人，9間教室，每間教室容量45人。其中學生選課結果統(tǒng)計和每科教師人數(shù)如表2所示。

表2 實例2原始數(shù)據(jù)表

3.2 數(shù)學模型

首先，實例1在min≤ 19、實例2在min≤ 25時會考、高考均無排課失敗學生，且滿足所有約束。其次，在沒有排課失敗學生的前提下，評判最終課表優(yōu)劣的標準為教室資源利用率。為方便繪圖，以冗余率作為標準。教室資源冗余率η定義如下：

本次仿真設定的優(yōu)化次數(shù)為1次，改變停開課程限度直至高考或會考課表出現(xiàn)排課失敗學生。以冗余率為因變量，得到散點圖。用最小二乘法擬合曲線如圖6、圖7所示。

圖6 實例1冗余率擬合曲線

圖7 實例2冗余率擬合曲線

分析實例1或實例2的冗余率擬合曲線可知，在不出現(xiàn)排課失敗學生的前提下，停開限度越高冗余率越低，排課效果越好，這與直觀判斷相符。為獲得本算法下的較優(yōu)解，改進圖1所示算法如圖8所示。改進的部分是在不出現(xiàn)排課失敗的前提下不斷提高停開限度，取停開限度最高的方案作為最終解。

圖8 課時生成改進算法流圖

依照上圖方法可以無須設置停開課程限度，直接獲得該算法策略下的較優(yōu)解。運行程序得到的部分結果如表3、表4所示。

表3 實例2課時方案

表4 實例2教師分配方案

3.3 仿真討論

算法策略能夠成功完成兩組實例下的高考和會考排課任務，驗證了算法的有效性；并且分析得到停開課限度與教室資源利用率之間的關系，從而改進算法以獲得較優(yōu)解。

在獲得高考和會考的三類課時并分配教師完畢后，在高考和會考課時區(qū)中分別依照時間順序周期地填充課時，填充的輪數(shù)為一個高考或會考科目一周內的總課時數(shù)。這樣處理的好處是無論課時區(qū)在時間順序上的羅列情況如何，都能夠保證同一個教師不會在上完一個班的課后再給此班級上課，實現(xiàn)了教案對齊的實際需求，并盡可能保證了每個科目課時均勻。選修課時區(qū)的規(guī)劃可以依照學校的具體需求設計，但應保證不在相應教師的非排課時間之內。此部分內容與本文算法無關，不再贅述。

4 結論

本文給出了一種走班制下選修課排課的優(yōu)化度排課算法，并通過數(shù)值算理驗證了該算法的有效性。為直接得到算法策略下的較優(yōu)解，算例還驗證了停開限度對教室資源利用率的影響，實現(xiàn)更加智能的排課過程。本文算法的優(yōu)點在于1、滿足學生的選課需求，完成走班制下的排課任務。2、算法運行時間短，實現(xiàn)簡單。但此算法也存在缺點1、固定班教學與走班教學分立，不能做到同一時間既有走班也有固定班。2、教室空間資源存在冗余。此外，本文沒有討論分層教學（不同水平的學生在不同的班）、合班課程（兩個班級在一個教室同時上課）、教師水平區(qū)分（不同教學水平的教師分派不同的教學任務）等更深層次的排課需求，后續(xù)還應解決諸如此類學校排課的個性化問題。