新高考下考慮時序約束的分班規(guī)劃問題研究

孫 哲, 王 翀, 吳慶華

(華中科技大學 管理學院,湖北 武漢 430074)

0 引言

2014年9月,國務院印發(fā)了《關于深化考試招生制度改革的實施意見》,拉開了新高考改革的序幕[1],之后各省也陸續(xù)發(fā)布了本省市的《普通高考綜合改革實施方案》[2],規(guī)定除語文、數學、外語3個統考科目外,考生可根據興趣特長及報考高校要求從物、化、生、政、歷、地等6門(或7門,浙江多一門通用技術)學科中任選3門參加考試(該3門學科稱為選考學科,剩余3門稱為學考學科),相關成績納入高考成績。將選擇權交給學生后,學生的選課組合從原來的文理2種,變?yōu)?選3的20種(或7選3的35種,及部分省市“3+1+2”模式的12種)。新的高考選科制度,直接導致同一班級學生的選科不盡相同,這必然導致班級存在多種學科選科組合。受教學資源的限制,如果全部按照學生選科種類分班是不現實的[3],即每個班級無法開設所有的選考課程,這必然導致部分學生需要到別的班級進行插班(即走班)上課,從而形成走班制教學。國內走班制度主要有兩大模式:一種是以北京十一學校為代表的全科走班(全走班);另一種是行政班與教學班并存的模式(根據走班程度分為小走班、中走班和大走班)[4,5]。本文主要針對行政班與教學班并存的模式進行討論。

與傳統的班級授課模式不同,學生需在自己所屬行政班不上課的時段到某個教學班上自己所選修的課程。在實際中,走班制教學模式會使排課的約束條件增多,學校教育資源匱乏的現象進一步凸顯,絕大部分高中正面臨“選科難、走班難、排課難、管理難”的困境[6]。對于部分已經實施走班教學的中學,低效的分班規(guī)劃和走班排課方案,不僅造成教學資源的浪費,還會導致教師教學工作量增加、學生學業(yè)負擔加重、教師授課和學生學習效率降低、學校教務安排無法滿足等現象,而良好的分班規(guī)劃方案,可以有效解決這些問題。

對于傳統的排課問題,自20世紀中期以來,國外的學者就陸續(xù)開展了研究,但文獻中研究的大部分排課表問題都是以不同國家和地區(qū)的教育體制為背景,所以研究問題在基本目標、資源限制等方面存在較大差異[7]。同時,對于我國新高考下的分班規(guī)劃問題,尚未發(fā)現英文文獻對該問題進行研究。相比于國外,由于高考改革至今時間較短,國內對新高考走班模式下的排課算法研究也僅有少數幾篇,侯發(fā)毅[8]采用UML的設計思想對新高考模式下的走班教學管理系統進行了研究,分析了選課與走班排課的需求與基本業(yè)務流程,該研究著重對選課信息進行了規(guī)劃。王華鑫[9]整理了高中分層走班教學模式的基本流程,將分層走班排課問題分為分班規(guī)劃與走班排課兩個階段,分班階段使用貪心策略與對偶班制度,排課階段使用爬山算法滿足硬約束,再使用模擬退火算法優(yōu)化軟約束,但是在實際情況下,學生自主選科的結果會保持較大的多樣性,在班級資源的限制下無法使其恰好滿足對偶班制度。

本文分析了分班規(guī)劃問題的特點與困難,提出了行政班分班以及教學班分班規(guī)劃的數學模型,并用CPLEX求解,驗證了模型的有效性。同時提出了一種變鄰域搜索算法,針對教學班分班規(guī)劃問題設計目標函數、鄰域定義以及優(yōu)化方案等,對該問題的大規(guī)模算例進行啟發(fā)式求解,高效計算出優(yōu)質的分班方案,以降低后續(xù)走班排課的難度。

1 分班規(guī)劃問題

分班規(guī)劃問題是一個多目標、多因素、多約束條件的組合規(guī)劃問題,根據學生上課地點是否固定分為行政班分班和教學班分班規(guī)劃問題。為了減少學生走動及便于管理[10],選考學科以外的科目如語文、數學、外語等各項教學活動往往以固定的形式安排在本班上課,只由本班的學生和教師參加,這些固定的班級稱之為行政班。而對于部分選考學科,學生需要脫離其所在行政班到別的班級進行走班上課,這種臨時組建的選考科目班級稱為教學班[11]。

1.1 行政班分班規(guī)劃問題分析

為了減少學生走動,便于班級管理,在進行教學班劃分之前,會盡量將選課一致或者相近的學生編排到同一行政班級。在實際中,行政班劃分一般有以下幾種形式:優(yōu)先三科成班、定二走一、定一走二等[12]。隨著班級選科組合相同的學生越多,教學班劃分的難度也會降低,所以學校需要根據自身的資源情況來確定行政班分班模式。本文給出該問題的一般數學模型。

1.2 行政班分班規(guī)劃數學模型

新高考行政班分班規(guī)劃問題,可歸納如下,已知學生的選科組合,該問題需要把學生指派到各班級中,若該班級所有學生都選擇了某科目,則該科目視為固定形式上課,最終每個班級以固定形式上課的科目數量最多,并同時滿足班級人數上下界約束。

1.2.1 變量與參數

相關參數:

I:所有學生的集合;

J:所有教室的集合,包括行政班教室J*和額外教室J′,J=J*∪J′;

K:所有學科的集合;

Sik:若學生i選擇了學科k,則Sik=1,否則Sik=0,i∈I,k∈K;

Uj:教室j的人數上界,j∈J;

Lj:教室j的人數下界,j∈J;

M:一個很大的常數。

決策變量:

xij∈{0,1}:若學生i被分配到班級j,則xij=1,否則xij=0,i∈I,j∈J*;

yjk∈{0,1}:若班級j固定開設學科k,則yjk=1,否則yjk=0,j∈J*,k∈K。

1.2.2 數學模型

基于以上符號說明,建立本文的數學模型如下:

(1)

約束條件:

(2)

(3)

(4)

(5)

(6)

目標函數(1)為行政班分班規(guī)劃的最優(yōu)目標,即最大化班級所固定的學科數。式(2)表示每個學生只能被分配至一個行政班;式(3)表示每個班級的學生數量必須滿足教室容量約束;式(4)代表每個行政班最多固定3門學科(每個學生的選科組合相同);式(5)和式(6)確保固定某門學科時,班級內選擇該學科的人數必須等于班級總人數。

1.3 教學班分班規(guī)劃問題分析

教學班分班規(guī)劃是一個考慮時序約束的分班規(guī)劃問題。我們觀察到,為了最大程度利用上課時間,學校會指定某個時間段只有教學班上課,這樣就得出一種名為“同時上課”的課表要求[13],而教學班分班規(guī)劃就是在資源限制的條件下分出滿足學生選課需求的教學班,教學班分布在不同時間段同時上課。為了每個行政班總課時數平衡,其最佳開課選擇是每個班開設3門選考科目以及3門學考科目(非走班科目一致)。為了滿足“同時上課”的需求,該問題需要考慮時序約束,規(guī)定這3門選考科目(選考課和學考課原理相同,本文以選考課為例進行討論)必須分別屬于3個不同且互不相交的課程組(實踐中稱為選考時序組)。每個時序組需要為每一位學生分配一個教學班級,并使得最終該生的3個教學班級與其所選3門學科一致,若教學班教室與學生所在行政班教室不一致,則視為走班。最終,每個選考時序組都包含全體學生,每個學生在3個組中都只屬于一個和其選考科目相一致的教學班,如圖1所示。對于同一時序組的選考教學班級,只要保證統一時間上課,便可以避免學生在選考課上課時間上的沖突,如圖2所示。需要注意的是,為了減少學生走動,應盡量將學生分配至其所在行政班開設的選考教學班。同時,若學校有多余的教室資源,允許借助額外教室設置教學班。最后,對于不存在相互插班的選考教學班(整班),可以不受“同時上課”的約束而脫離其所在選考時序組,這樣可以減少對任課教師數量的依賴。

圖1 教學班分班示例

教學班分班規(guī)劃問題的硬約束規(guī)則如下:H1:開班人數不能高于教室容量的上限,也不能低于教室容量的下限;H2:所使用的教室不能多于行政班教室和額外教室的總和;H3:每個時序下課程的數量不能超過任課教師的數量;H4:教室必須開設學校指定的某一教室需要開設的課程。軟約束規(guī)則如下:S1:走班的學生人數應盡可能少;S2:混班的數量應盡可能少。硬約束主要考慮了分班方案的可行性,需要開設的教學班級必須滿足人數上下界、教室數量以及教師數量等,硬約束直接決定了教學計劃能否順利執(zhí)行。需要注意的一點是,開班人數不能高于教室容量的上限這是必然的,但現實中往往會因為某一科選擇人數過少而無法成班,但其實這種情況學校也是允許成班的,所以在建模的過程中,會將不能低于教室容量下限這一硬約束作為目標函數來考慮,以此來評判低于下限的程度。而軟約束的設定主要考慮教學管理的難易程度,更少的人員走動,既可以降低管理難度,還可以提高后續(xù)課表調整的靈活性。所以在設計數學模型和算法時應同時考慮這兩種約束。

1.4 教學班分班規(guī)劃數學模型

考慮時序約束的教學班分班問題,可以歸納總結如下,給定3個時序組,對于每個班級,需要確定每個時序組內所開設的課程,行政班必須開設3門課程,額外班級可以不開設課程;對于每位學生,需指定3個對應科目的教學班,指定的3個班級分布在3個不同時序組。問題的目標是使得走班上課的人數盡可能少以及班級人數盡可能合理,同時滿足教學班人數上界、任課教師數量、教室數量、必開學科等約束條件。

1.4.1 變量與參數

相關參數:

T:所有時序的集合,一共為3個時序;

Bij:若學生i的行政班級為班級j,則Bij=1,否則Bij=0,i∈I,j∈J*;

Hjk:若班級j必須開設學科k,則Hjk=1,否則Hjk=0,j∈J*,k∈K;

Ck:學科k的教師數量,k∈K。

決策變量:

xjtk∈{0,1}:教室j在時序t開設學科k,則xjtk=1,否則xjtk=0,j∈J,t∈T,k∈K;

yitj∈{0,1}:學生i在時序t走班至教室j,則yitj=1,否則yitj=0,i∈I,t∈T,j∈J;

zitk∈{0,1}:學生i在時序t上學科k,則zitk=1,否則zitk=0,i∈I,t∈T,k∈K;

pit∈{0,1}:學生i在時序t需要走班,則pit=1,否則pit=0,i∈I,t∈T;

djt∈N+(N+表示正整數):表示教室j在時序t人數不足的程度,djt取0表示教室j在時序t不開設課程或者滿足最少開課人數。

1.4.2 數學模型

基于以上符號說明,建立本文的數學模型如下:

(7)

(8)

約束條件:

(9)

(10)

(11)

(12)

(13)

(14)

(15)

xjtk+yitj-1≤zitk,?i∈I,?t∈T,?j∈J,?k∈K

(16)

yjtk+zitj-1≤xitk,?i∈I,?t∈T,?j∈J,?k∈K

(17)

pit≥yitj-Bij,?i∈I,?t∈T,?j∈J

(18)

(19)

(20)

2 算法設計

2.1 構造初始解

本文中的可行解由兩部分組成:(1)xjtk表示每個班級在每個時序所開設的課程,若j是行政班,則只需考慮需要開設哪一門課程,若j是額外教室,則還需考慮是否開設課程;(2)決策變量yitj和zitk用來描述每個學生在每個時序走班的教室以及所上的課程。本文采用隨機貪婪的思想來構建初始解,具體步驟如下:

步驟1確定xjtk,先根據參數設置的班級必開學科放置課程,再隨機選取直至每個班級3個時序都分配了不重復的學科,隨后通過爬山算法優(yōu)化3個時序內的學科分布,使得每個學科盡可能均勻地分布在3個時序。

步驟2初始化學生3個時序內的上課順序(zitk),通過貪心策略計算學生選課組合與每個班級開課組合的匹配度進行分配,如班級開課組合順序為物、化、生,學生選課的也為物、化、生,則匹配度為3(完全匹配),優(yōu)先將該學生分配至該班級的三個時序。若最大匹配度為2,則還需在不匹配的時序內隨機選擇一個學科匹配的新班級,以此類推,確定yitj。

2.2 變鄰域搜索算法(VNS)

變鄰域搜索(Variable Neighborhood Search,VNS),由MLADENOVIC和HANSEN[14]提出,本文設置了四個鄰域對初始解進行局部搜索。從隨機構造初始解開始,通過四個鄰域的迭代搜索,并在每一輪搜索完成后保留當前最優(yōu)解(中間解)進行優(yōu)化,通過多次重啟的方式,代替VNS常用的擾動,更新當前最優(yōu)解。最終,通過Itermax次搜索得到最優(yōu)解(最終解)后,進一步優(yōu)化以更精確地計算約束滿足情況,算法偽代碼如下。

表1 多次重啟的變鄰域搜索算法步驟

2.2.1 移動操作與鄰域

為了有效搜索解空間,本文提出了4個鄰域操作:N1(FlipClass),N2(SwapTwoClass),N3(ExchangeClass)以及N4(ExchangeCombination)。每次迭代以遍鄰域的方式從當前鄰域選擇最佳移動,并保留為當前解S′,若當前解f(S′)

N1(FlipClass):將任一班級j在時序t的科目k1,更換成學科k2。以圖1為例,高二(1)班在時序1開設物理,變更為開設生物。

N2(SwapTwoClass):交換同一時序t中的任意兩個班級j1和j2所開設的學科k1和k2。以圖1為例,時序1中高二(1)班開設物理,高二(2)班開設政治,交換后,時序1中高二(1)班開設政治,高二(2)班開設物理。

N3(ExchangeClass):交換任一班級j在時序t1和t2內的學科k1和k2,并交換該班級作為行政班所包含學生的上課順序。以圖1為例,高二(2)班開設學科為政、化、物,交換時序1、2后為化、政、物,同時學生上課方案也一同交換,高二(2)班共有兩種組合的學生,上課順序為政、化、物和政、生、物,交換后為化、政、物以及生、政、物。

N4(ExchangeCombination):交換任一班級j某一選科組合的學生在時序t1和t2的上課順序。以圖1為例,高二(6)班存在兩種選科組合的學生,上課順序分別為生、歷、地及生、歷、政,交換時序2和時序3中的上課順序,則變?yōu)樯⒌亍v和生、政、歷。

值得注意的是,每一次鄰域操作主要針對xitk和zitk設計,并根據變換過的xjtk和zitk更新yitj,再計算該操作導致的目標函數懲罰值的變化。同時,我們僅考慮班級開設學科和不同選課組合上課順序的變化,并不以單個學生為單位,大大縮小了鄰域空間,提高了搜索效率。

2.2.2 對中間解及最終解的優(yōu)化

搜索得到的中間解需要進行優(yōu)化,目標是改善違反人數下界約束的程度。在不改變班級開設學科的前提下,以單個學生為單位(鄰域搜索中以選課組合為單位進行搜索),交換單個學生的上課順序或改變單個學生在每一時序上課的班級,平衡班級人數。完成全部搜索得到最終解后,繼續(xù)調整單個學生,需要考慮的目標有使各教學班人數盡量平均,檢查并調整是否有本班開設了對應科目學生卻走班至其他教室上課的情況。

3 算例分析

本文通過數值算例來說明問題性質及VNS算法的表現。其中采用C++編寫VNS算法,所有試驗均在Intel Core i5-8400 @ 2.8GHz 64位計算機上進行。由于國內現有對新高考分班規(guī)劃問題的研究較少,無法找到現有的基準數據,因此本文使用廣州某中學高三年級的數據進行實例分析,同時為了實驗完整性,還使用了一組隨機生成的數據來測試算法的性能與效果。

3.1 實例分析

實例數據來自廣州某中學高三年級的走班需求調研。該高中可選學科為6門,學生以“3+1+2”的模式進行選科,即物理和歷史必須2選1,再從余下4門中任選2門。該年級一共588名學生,分為12個行政班,物、化、生、政、歷、地任課教師的數量分別為5,4,5,2,2,3名,另外還擁有2個額外教室,每間教室最多容納學生58人,最小成班人數為35人。按照學生的選課結果,已經以定二走一的模式完成行政班分班。

由于問題規(guī)模較大,無法通過CPLEX求解,所以利用變鄰域算法得出具體的走班方案,如表2所示,其中“課程”表示該時序各個班所開設教學班的課程,“人數”表示該時序參加該教學班的學生人數,“混班”表示該教學班的學生組成來自除本班外的班級數,0表示整班上課。整班上課的教學班可以不參與走班,所上課程作為行政課程處理進行排課。整班上課的教學班越多,排課的難度越小。所有教學班滿足人數上下限,總計非整班數量為9。該方案在滿足硬約束的同時,保證了班級人數在合理區(qū)間內,且整班數量足夠多,對應學科教師的任課安排將更加靈活,每個教學班混班數量不超過3個班級,降低了學校走班教學管理的難度,且原有的12個教室完全可以滿足上課要求。

表2 廣州某中學高三年級走班方案

3.2 隨機數據結果分析

本文還以實際算例為基礎,隨機構造了一組數據,學生規(guī)模從45到900不等,測試算法在不同問題規(guī)模與資源限制情況下的表現。表3展示了VNS和CPLEX求解器之間的結果比較,該求解器用于解決第2節(jié)中介紹的線性規(guī)劃公式。Opt表示通過CPLEX求解得到的最優(yōu)值。VNS表示通過VNS算法對算例進行10次計算得到的最優(yōu)值。CPU表示CPLEX和VNS的計算時間。GAP表示VNS算法與最優(yōu)解之間的差距。列2-列4表示問題的規(guī)模大小。從表3得出,前10組的數據CPLEX可以在1h之內計算出結果,而第11組的數據雖然在學生規(guī)模上相同,但由于多了2個班級以及1個額外班,CPLEX卻花費了20倍的時間才求得最優(yōu)解,這也說明了教室數量的多少對解空間影響很大。對于VNS算法來說,從計算結果來看與精確解結果相近,且基本能在1s內得到結果,這在實際應用中有很大的優(yōu)勢。

表3 CPLEX求解結果與VNS算法結果比較

為了進一步驗證本文算法的優(yōu)越性,對余下算例進行求解。表4展示的是VNS在較大規(guī)模算例上的結果。目標值是該算法對算例進行10次求解,得到的最優(yōu)解。目標值的計算方式為Distlb×5+Moves,其中Distlb是該結果中教學班開班人數下界未滿足的人次,Moves是該結果中學生需要進行走班的總人次。從表4可以看到,VNS平均可以在0.1s左右就獲得結果。當算例規(guī)模較小時,由于已有的行政班教室資源較少,無法滿足學生多樣的選課需求,可能會出現硬約束無法滿足的情況,所以就會優(yōu)先犧牲軟約束來滿足硬約束,這就導致了需要更多的額外教室,且走班人數的比例會更多,以及教學班的開班人數下限難以滿足。但隨著學生數量以及班級數量的增加,學校有了充足的教室資源后,幾乎不需要額外教室開設教學班,且走班人數的比例也明顯下降,教學班的開班人數基本可以滿足上下限。

表4 VNS算法結果

4 結論

本文介紹了新高考下分班問題的研究背景,簡述了分班問題的類型、難點及重要性。從中總結了行政班分班問題,并給出了基礎數學模型。又重點介紹了考慮時序約束的教學班分班規(guī)劃問題,首次提出了以開班人數最合理以及走班人數最少為目標函數的整數線性規(guī)劃模型。該模型充分考慮了教學班分班的特點,例如學校的教室資源、教師資源等。然后利用CPLEX在小規(guī)模算例上進行求解,驗證了模型的有效性。并設計VNS算法求解教學班分班問題。該算法在小規(guī)模算例上與CPLEX求得的最優(yōu)解差距較小,在大算例上均能在短時間內獲得優(yōu)質解。未來可以考慮分層模式下以及基于師生最佳匹配的分班規(guī)劃和走班排課問題研究。