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

儒曼，武迪，張致遠(yuǎn)

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

0 引言

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

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

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

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

1 課時(shí)分區(qū)處理

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

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

2 優(yōu)先度算法

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

2.1 數(shù)學(xué)模型

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

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

（1）同一時(shí)間一個(gè)學(xué)生不能排兩門課程；

（2）同一時(shí)間一個(gè)教室不能排兩門課程；

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

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

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

定義邏輯變量：

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

圖1 學(xué)生插入過程示意圖

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

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

2.2 數(shù)學(xué)模型

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

圖2 課時(shí)生成算法流圖

圖3 課表生成算法流圖

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

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

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

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

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

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

3 數(shù)值仿真

3.1 算例設(shè)置

本次實(shí)驗(yàn)的目的有兩個(gè)：

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

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

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

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

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

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

3.2 數(shù)學(xué)模型

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

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

圖6 實(shí)例1冗余率擬合曲線

圖7 實(shí)例2冗余率擬合曲線

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

圖8 課時(shí)生成改進(jìn)算法流圖

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

表3 實(shí)例2課時(shí)方案

表4 實(shí)例2教師分配方案

3.3 仿真討論

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

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

4 結(jié)論

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