孫 哲, 王 翀, 吳慶華

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

0 引言

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

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

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

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

1 分班規(guī)劃問(wèn)題

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

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

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

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

新高考行政班分班規(guī)劃問(wèn)題,可歸納如下,已知學(xué)生的選科組合,該問(wèn)題需要把學(xué)生指派到各班級(jí)中,若該班級(jí)所有學(xué)生都選擇了某科目,則該科目視為固定形式上課,最終每個(gè)班級(jí)以固定形式上課的科目數(shù)量最多,并同時(shí)滿足班級(jí)人數(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:一個(gè)很大的常數(shù)。

決策變量:

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

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

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

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

(1)

約束條件:

(2)

(3)

(4)

(5)

(6)

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

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

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

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

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

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

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

1.4.1 變量與參數(shù)

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

T:所有時(shí)序的集合,一共為3個(gè)時(shí)序;

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

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

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

決策變量:

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

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

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

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

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

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

基于以上符號(hào)說(shuō)明,建立本文的數(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è)計(jì)

2.1 構(gòu)造初始解

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

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

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

2.2 變鄰域搜索算法(VNS)

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

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

2.2.1 移動(dòng)操作與鄰域

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

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

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

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

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

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

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

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

3 算例分析

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

3.1 實(shí)例分析

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

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

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

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

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

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

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

表4 VNS算法結(jié)果

4 結(jié)論

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