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

孫 哲, 王 翀, 吳慶華

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

0 引言

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

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

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

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

1 分班規(guī)劃問題

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

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

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

1.2 行政班分班規(guī)劃數(shù)學(xué)模型

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

1.2.1 變量與參數(shù)

相關(guān)參數(shù):

I:所有學(xué)生的集合;

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

K:所有學(xué)科的集合;

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

Uj:教室j的人數(shù)上界,j∈J;

Lj:教室j的人數(shù)下界,j∈J;

M:一個很大的常數(shù)。

決策變量:

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

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

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

基于以上符號說明,建立本文的數(shù)學(xué)模型如下:

(1)

約束條件:

(2)

(3)

(4)

(5)

(6)

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

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

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

圖1 教學(xué)班分班示例

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

1.4 教學(xué)班分班規(guī)劃數(shù)學(xué)模型

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

1.4.1 變量與參數(shù)

相關(guān)參數(shù):

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

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

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

Ck:學(xué)科k的教師數(shù)量,k∈K。

決策變量:

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

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

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

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

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

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

基于以上符號說明,建立本文的數(shù)學(xué)模型如下:

(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 算法設(shè)計

2.1 構(gòu)造初始解

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

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

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

2.2 變鄰域搜索算法(VNS)

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

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

2.2.1 移動操作與鄰域

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

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

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

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

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

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

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

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

3 算例分析

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

3.1 實例分析

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

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

表2 廣州某中學(xué)高三年級走班方案

3.2 隨機數(shù)據(jù)結(jié)果分析

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

表3 CPLEX求解結(jié)果與VNS算法結(jié)果比較

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

表4 VNS算法結(jié)果

4 結(jié)論

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