張宇瞳，劉 靜，郝星星

西安電子科技大學(xué) 人工智能學(xué)院，西安710071

新高考改革的政策已經(jīng)逐步在全國范圍內(nèi)實施，各個省份推出了適合自己的教學(xué)與考試變革方案。新高考改革的一個特點在于學(xué)生的考試科目不再是從文科與理科考試科目集合中“二選一”，而是根據(jù)自身喜好特長和所在學(xué)校特色以及目標報考大學(xué)專業(yè)要求選擇自己的考試科目組合，通常為“6選3”或“7選3”[1-2]?？荚嚳颇拷M合的變化將帶來教學(xué)組織的變化，核心體現(xiàn)為同一個行政班的學(xué)生可能存在的選課組合增多。通常來說不適合將學(xué)生需要上的所有科目安排在一個行政班內(nèi)開設(shè)，而解決這一問題的常見方案為走班制教學(xué)[1-4]。在走班制教學(xué)中，學(xué)生將根據(jù)選課與分班結(jié)果在自己所屬行政班不上課的時段內(nèi)到某個教學(xué)班上自己所選的選修科目。這一教學(xué)組織模式為教務(wù)排課工作帶來諸多新的挑戰(zhàn)，比如大量教學(xué)班的出現(xiàn)、學(xué)生上課沖突的出現(xiàn)等，這些都是學(xué)生個性化選擇與學(xué)校統(tǒng)籌安排和教學(xué)秩序管理之間新出現(xiàn)的矛盾[2]。

本文主要解決的問題是“新高改”模式下高中走班制排課中如何提高排出的課表對老師教案平齊的滿足程度、課時分布均勻程度以及對同時上課要求的滿足程度。老師教案平齊和課時分布均勻程度是諸多學(xué)校結(jié)合本校老師的教學(xué)經(jīng)驗和學(xué)生學(xué)習(xí)效果總結(jié)出的兩條較為重要的課表質(zhì)量評價指標。因此在走班制教學(xué)過程中這些學(xué)校也希望排出的課表能在這兩條指標上有較高的滿足程度。但不可否認相較于僅有行政班課表的排課任務(wù)，走班排課過程中可行課表的搜索難度提高了，優(yōu)化其他目標的難度也明顯增大。這里所說的可行課表指的是課表中每一門科目課時均滿足預(yù)先設(shè)定的一周課時總量并且不能出現(xiàn)學(xué)生和老師的上課時間沖突。為了最大程度利用上課時間，許多學(xué)校在排課過程中指定了在某個時間段內(nèi)行政班都不上課而只有走班在上課，這樣就得出一種名為“同時上課”的課表要求。在走班制課表排布過程中同時上課規(guī)則不僅是對課表的一項新增要求，通過本文的案例實驗研究也發(fā)現(xiàn)設(shè)置合理的同時上課規(guī)則也有助于優(yōu)化算法盡快排出高質(zhì)量的課表。

為此，提出一種多階段新高考“走班”排課算法，將排課過程劃分為“優(yōu)化教學(xué)班課表課時分配”“優(yōu)化獲得教學(xué)班完整課表”“優(yōu)化行政班課表課時分配”“優(yōu)化獲得行政班完整課表”四個階段。其中兩個課時分配階段是本文提出算法中的核心階段。在對大量學(xué)校的課表進行觀測后發(fā)現(xiàn)一個優(yōu)良的課表首先得是一個課時分布合理的課表。通過對學(xué)校真實排課過程的觀摩，發(fā)現(xiàn)通常來說跨天轉(zhuǎn)移一個班級的某門課程的課時是一個較為困難的過程，通過算法自動生成的課表如果可以避免天之間的課時轉(zhuǎn)移將對后續(xù)人工調(diào)課大有裨益。因此將待優(yōu)化課表中每個班每一科目的天課時分配放在首要位置，設(shè)計了一個多階段的排課算法。在天課時分配優(yōu)化階段可以就教案平齊違反、課時分布不均勻等目標函數(shù)最小化進行課表優(yōu)化。然后在下一階段中，將課表變化的范圍鎖定在一天之內(nèi)，就課時優(yōu)選、行政班可用空閑時段最大等目標進行優(yōu)化，稱這一階段為“天內(nèi)課表優(yōu)化”。整個過程先從單獨排教學(xué)班課表開始，在得到不違反約束條件的教學(xué)班課表之后繼續(xù)分配行政班課時并最終得到完整課表。

在多階段排課算法中，設(shè)計了5個目標函數(shù)：（1）滿足課時均勻的教案平齊；（2）同時上課課時一致；（3）可排出不沖突課表的課時分配；（4）教學(xué)班課時占用壓縮；（5）滿足行政班可用排課時段。前四個目標函數(shù)用于教學(xué)班和行政班的天課時分配優(yōu)化階段，第五個目標函數(shù)用于教學(xué)班的天內(nèi)課表優(yōu)化階段。除此之外還沿用了已有研究中的學(xué)生或老師的課時不出現(xiàn)沖突的約束條件[5-6]用于獲得可行課表以及課時優(yōu)選目標函數(shù)[5，7]用于獲得更為接近實用的課表。提出了一種可以解決約束優(yōu)化問題的改進爬山算法用于天課時分配優(yōu)化階段。針對跨天調(diào)整課時需要調(diào)整多張課表的特點，為該階段使用的爬山算法設(shè)計了無評價均勻分布算子、同時上課修正和轉(zhuǎn)移算子以及不可排課情況下的教學(xué)班課時轉(zhuǎn)移算子。

為了驗證本文提出算法的有效性，選用了三個不同難度和規(guī)模的排課案例。對最終輸出課表各項指標的滿足情況進行了進一步細分觀察。在三個案例上本文提出算法均可以以85%以上的概率排出可行課表，整個過程的計算時間消耗也在可接受范圍內(nèi)。在人工生成案例上的實驗結(jié)果說明了算法可以在教案平齊、課時分布、行政班課時滿足等目標函數(shù)上達到全局最優(yōu)。教學(xué)班課表教案平齊指標滿足較行政班而言更為理想，整體課表的教案平齊滿足與行政班課表的教案平齊滿足呈正相關(guān)。通過進一步實驗還發(fā)現(xiàn)，教學(xué)班同時上課規(guī)則的出現(xiàn)對其他規(guī)則的滿足具有優(yōu)化指導(dǎo)作用。

1 相關(guān)工作與研究動機

自2014年教育部頒布《關(guān)于普通高中學(xué)業(yè)水平考試的實施意見》以來，對高中走班制排課算法的研究逐漸受到關(guān)注[4]。走班制的做法與高校的授課方法較為接近，都要求學(xué)生根據(jù)自己所選課程的安排于指定時間到指定教室上課。二者之間的主要差別在于學(xué)生的選課對排課的影響。通常來說高校排課都是發(fā)生在學(xué)生選課之前，高中走班制排課則是在學(xué)生選課之后，并且有一個根據(jù)學(xué)生高考選考科目的不同劃分所在行政班和教學(xué)班的過程[8]。因此已有的中學(xué)或高校的排課模式均不適用于中學(xué)走班制教學(xué)排課任務(wù)。

王衛(wèi)紅等人[5]提出了一種改進的遺傳算法解決高中走班制排課問題，以對學(xué)生進行分組的方式劃分出多個教學(xué)班組并以組為單位制定不同課表。李文瓊[9]在其研究中就文獻[5]中的模型和算法進行了進一步的說明和實驗分析。董玉鎖等人[10]同樣使用改進遺傳算法解決走班制排課問題，并且定義了三種排課約束，將這一問題建模為約束優(yōu)化問題。吳小芳[11]在其文章中使用分包策略將所有教學(xué)班的上課時間分在三個時間段并且將學(xué)生根據(jù)選課組合進行分組和分配包，有效地化解了學(xué)生之間的課時沖突問題。陳璐等人[7]使用兩次遺傳算法對走班課程和非走班課程進行了分階段排課。在對一個年級當中的所有班級進行分組后將組內(nèi)相同課程安排在同一時間。Hao等人[6]采用兩階段模擬退火算法解決高中走班制排課問題。在該文中提出的模型兼容了更為自由的學(xué)生分班方式。

排課問題在國際學(xué)術(shù)圈是一個經(jīng)久不衰的研究熱點。近些年先后出現(xiàn)延遲接受爬山方法[12]、整數(shù)規(guī)劃方法[13]、融合迭代搜索和變鄰域搜索（Variable Neighborhood Search，VNS）方法[14]、并行局部搜索方法[15]以及融合列生成和并行元啟發(fā)方法[16]來解決高中排課問題。這些研究當中的問題背景多為傳統(tǒng)的高中排課，涉及數(shù)學(xué)模型不夠貼近實用，目前看來不能直接適配中國的高中走班排課應(yīng)用中，但本文優(yōu)化算法的設(shè)計受到這些優(yōu)化搜索策略的啟發(fā)。

回顧這些已有研究發(fā)現(xiàn)大部分排課方法都是基于遺傳算法或啟發(fā)式方法。這些方法在解決新出現(xiàn)的復(fù)雜優(yōu)化問題上表現(xiàn)出較為出色的適應(yīng)能力。然而各項研究仍處于初步階段，僅對簡單的約束條件和目標函數(shù)進行了數(shù)學(xué)建模。雖然部分排課方法可以將學(xué)生上課時間沖突在建模階段消除，但要求整合自己的分班方式或分組方式[7，11]，弊端在于降低了學(xué)校個性化的操作空間。因此本文選取和文獻[6]相同的學(xué)生選課數(shù)據(jù)即已分班學(xué)生數(shù)據(jù)進行研究，并且就已有研究中少有提及的教案平齊、同時上課滿足、可排出不沖突課表等目標和約束條件進行建模和優(yōu)化。

分組或分階段優(yōu)化方法在課表排布研究中已有應(yīng)用。王祜民和趙致格[17]針對高校排課問題提出分組優(yōu)化方法對難排課程優(yōu)先排課。呂遠方[18]使用分階段方法分別處理高校排課中的時間表排布和教室安排表排布以減輕整體排課決策變量過多的壓力。受上述研究啟發(fā)，本文提出的方法將課程時間表排布分解為天課時分配和天內(nèi)排課兩個階段并且根據(jù)普遍規(guī)律先排難度較大的教學(xué)班課表。

2 高中走班制排課問題的數(shù)學(xué)模型

2.1 課表基本元素

首先給出課表的數(shù)學(xué)表達。定義行政班集合為S_adm，教學(xué)班集合為S_edu。一周中某一上課天表示為d，集合為Day，一天當中的時段數(shù)記為d(slots)，一周時段總數(shù)記為。學(xué)生選課和分班過程以及教室安排過程不在本文的討論范圍內(nèi)。對于排課中的幾個要素：學(xué)生、課程班、老師和時段，本文對其進行如下定義、表示和取值限制。

學(xué)生被指定在若干班級內(nèi)（包括一個行政班和若干教學(xué)班），這些班級開設(shè)的所有科目的所有課時學(xué)生都不能缺席。學(xué)生同一時間不能出現(xiàn)在兩個班級內(nèi)上課是學(xué)生課時不沖突的基本含義。在排課過程中真正起到影響作用的是學(xué)生的選課模式[6]而非具體某個學(xué)生，例如10個來自同一個行政班的學(xué)生選擇了相同的科目并被分配在相同的教學(xué)班當中，則這10個學(xué)生可以用一個模式來替代。

課程班指的是具體某個班級的某一科目，是每個班級的基本構(gòu)成之一。課程班具有所屬班級、科目、層級和課時四個屬性。本文中所屬班級、科目和層級用于區(qū)分不同課程班，當兩個課程班在這三個屬性中有任何不同時即被視為不同的課程班。課程班的課時要求為該班課表一周之內(nèi)安排該科目指定數(shù)目的課時，同一個班級的多個課程班的課時不能重疊。本文的課表優(yōu)化中不需要限定班級或課程分組，當然也支持將分組作為一種目標函數(shù)，即同時上課規(guī)則，融入到優(yōu)化過程當中。關(guān)于同時上課規(guī)則或分組對于排課優(yōu)化的影響將在下文中細致討論。

（1）這里用CClassac表示一個班級a的課程班(a∈S_adm?S_edu)。

（2）所有課程班的集合表示為S_CC。

（3）CClassac(slots,total)表示這個課程班一周應(yīng)開設(shè)的課時數(shù)，是一個大于0的整數(shù)。

（4）CClassac(slots,t,d)表示課表t中這個課程班在d這天開設(shè)的課時數(shù)，是一個非負整數(shù)。

老師被指定帶若干課程班。一個老師可能帶同一個班的多門不同科目。一個老師帶的不同班的同一科目或不同班級的不同科目上課時段有重疊會引起老師的上課時間沖突。

時段是課表的一個自然屬性，也就是通常見到的一張課程表中去除科目后剩下的“格子”。課程班的課時將被安排于這些時段中。對于任意一個班級而言，其各課程班課時總和可能小于一周總上課時段數(shù)，剩余位置由不排課時段或空閑時段表示。對于任意一天，每個班的所有課程班課時相加不能超過這天時段數(shù)。

圖1 學(xué)生選課模式，課程班，老師對應(yīng)關(guān)系

圖1給出了學(xué)生選課模式、課程班、老師之間的對應(yīng)關(guān)系示例。一個學(xué)生選課模式對應(yīng)多個課程班，一個課程班可用包含多個學(xué)生選課模式，每個課程班必須與至少一個學(xué)生選課模式相對應(yīng)；一個老師可以帶若干課程班，一個課程班由且只由一個老師來帶。

2.2 目標函數(shù)

用于課時分配階段的優(yōu)化目標和約束條件有：滿足課時均勻的教案平齊、同時上課課時一致、分配課時可以排出不沖突課表、教學(xué)班課時占用壓縮。用于天內(nèi)課表優(yōu)化階段的優(yōu)化目標和約束條件有：行政班可用排課時段足夠、課時優(yōu)選、上課時間不沖突。上課課時不沖突這一約束條件的測算沿用文獻[6]的方法，本文不再做出說明，這里將課表中存在的課時沖突程度記為Slot sConflict。接下來將詳細介紹其余優(yōu)化目標和約束條件的計算方式以及設(shè)計用意。

2.2.1 滿足課時均勻的教案平齊

此目標需考慮兩個因素——課時均勻分布和教案平齊。課時均勻分布要求課程班在每天當中的課時均勻分布。教案平齊要求能夠確保老師所帶同一科目的各課程班保持進度相同，減少一天之內(nèi)需要準備的教案數(shù)量，一定程度上減輕了老師的備課負擔。從課時分配的角度來對教案平齊進行描述，將其與課時均勻分布相結(jié)合，期望實現(xiàn)同時從老師和學(xué)生的角度優(yōu)化課時分布。

在計算課時分布均勻程度之前需要事先確定每個課程班應(yīng)有的課時理想分布，CClassac(slots,ideal)。這是一個長度為一周上課天數(shù)|Day|的非負整數(shù)向量，產(chǎn)生方式是初始化向量的每一位為，然后再為前CClassac(slot s,total)mod|Day|位加1，最終構(gòu)成一個所有元素求和后等于CClassac(slots,total)并且非增序排列的向量，使用如下公式計算課時分布均勻不滿足程度ide：

公式（1）中sortdecrease表示將集合A中的所有元素從大到小排序并構(gòu)成一個一維向量，該公式將各課程班的各天開設(shè)的課時數(shù)與理想分布向量的歐氏距離求平方和作為目標函數(shù)。為兼容課時分布的多樣性，這里特別對課時分布向量進行了排序。

一個老師所帶的課程班可以分為若干個互斥非空集合，使用TeacT(p_g,k)表示教師T的第k“教案組課程班集合”（下文中用“教案組”指代）。同一個教案組的課程班科目和課時相同。教案平齊要求分為周教案平齊（表示為TeacT(p_g,k).r=w）和日教案平齊（表示為TeacT(p_g,k).r=d）兩種模式，老師需要事先指定自己某個教案組要求的教案平齊模式，對于每個成員一周課時數(shù)大于天數(shù)的教案組統(tǒng)一采用日教案平齊方式來優(yōu)化。教案平齊的違反程度vio計算如公式（2）所示：

在公式（2）中，week_synchronism(a,b)表示對課表a而言教案組b的周教案平齊滿足程度。var(a)表示集合a所有元素之間的整數(shù)偏差值，這里需要度量的是教案組各課程班每天課時之間的差異。滿足周教案平齊的課時分布是：可以將一周上課天劃分為若干區(qū)間，每個區(qū)間內(nèi)只有一天上課而且所上課時數(shù)相同；滿足日教案平齊的課時分布是：每天各個課程班具有相同的課時。

滿足課時均勻的教案平齊這個目標為兩個部分的加權(quán)和：

其中，w1為權(quán)重系數(shù)，為一個介于0到1之間的實數(shù)。

2.2.2 同時上課課時一致

在走班制課表排布過程中學(xué)校為避免部分學(xué)生單獨上自習(xí)帶來的管理問題，同時也為了提高教學(xué)時間的利用效率，通常會設(shè)置多個教學(xué)班需要在同一時間開課這一要求[8]，稱這樣的一個教學(xué)班集合為一個同時上課組（第k同時上課組符號表示為：STimek）。一組同時上課的教學(xué)班所涉及的學(xué)生當中不存在任何學(xué)生的選課模式包含超過一個組內(nèi)教學(xué)班。通常也不會有老師帶超過一個以上的班級。一個教學(xué)班只可能屬于一個同時上課組或不屬于任何同時上課組。

從課時分配的角度來看，只有滿足每天課時一致才有可能在日排課過程中構(gòu)成課時對齊。這里將第k同時上課組在d這天的課時不一致表示為SameTime-Inconsistent(t,STimek,d)。計算中首先基于一周課時數(shù)對這個同時上課組成員進行從大到小排序，然后遍歷所有成員，將該成員當天超出其他排在之前的成員的課時的數(shù)目相加。在獲得每個同時上課組在每一天的同時上課違反值后累加獲得同時上課整體違反情況，用如下公式表示：

2.2.3 可排出不沖突課表的課時分配

課表在課時分配階段不考慮是否不存在沖突，但必須考慮是否在下一階段中不可能排出課時不沖突的課表，因此設(shè)計了“可排出不沖突課表的課時分配”約束條件?；凇罢n程班集合占用最少課時量”這一算法可以給出當前課時分配下一天所需時段數(shù)的一個下界，并結(jié)合該天的可用時段數(shù)給出約束違反程度。該約束條件可以涵蓋單個或是多個學(xué)生老師一天課時過多，一周課時不夠用等可能導(dǎo)致不可排課情況。根據(jù)這一約束條件可以提早做出課表調(diào)整避免無意義的后續(xù)優(yōu)化。

這種不可排課現(xiàn)象可以表示為“最大全聯(lián)通子圖中的不可染色情形”。圖論應(yīng)用到排課問題中已有學(xué)者進行過一些研究，王鳳和林杰[19]在高校排課問題研究中，將每個班級的每個課程抽象為圖中待染色節(jié)點，顏色代表了上課時段，通過老師和學(xué)生的授課上課關(guān)系決定哪些課時不能在同一時間開設(shè)。這里用節(jié)點表示課程班，用無向邊表示存在于同一個選課模式或由同一個老師代課。一個全連接子圖是一個成員節(jié)點兩兩之間存在連接的節(jié)點集合，這個集合的存在意味著若這些課程班d這一天的課時相加后大于d(slots)，則這天不存在不沖突的課表。稱這個圖為課程班沖突關(guān)系圖，GCClass_conflics。

課時分配過程可以繼續(xù)細分為教學(xué)班課時分配和獲得教學(xué)班課表后的行政班課時分配兩種情形。在教學(xué)班課時分配過程中不僅需要考慮教學(xué)班范圍內(nèi)的課時過多導(dǎo)致的不可排課，還需要從每個行政班的角度考慮一周當中是否留有足夠的行政班可用空間和每一天是否留有足夠的行政班可用空間。

因為原理基本相同，這里僅給出教學(xué)班課時分配過程中“可排出不沖突課表的課時分配”的違反懲罰計算過程。在分配教學(xué)班課時之前需要確定各行政班的課時需求情況，這一過程獨立于課表優(yōu)化，可以僅根據(jù)課時設(shè)置推測得到。對于行政班x而言，將所有該行政班的課程班課時相加即可得到周最低課時需求，slotsWeekMin(x)；將課時數(shù)大于|Day|/2的課程班的課時數(shù)加和并除以|Day|后再將求得的商向下取整就可以得到行政班x的日最低課時需求slotsDayMin(x)。行政班的可用排課時段數(shù)大于周最低課時需求為可排必須滿足的硬性條件，而日最低課時需求是出于對行政班課時均勻性的照顧，相對來說是一個軟性約束。

“可以排出不沖突課表”的違反程度是以下三個部分的加和的結(jié)果：

公式中slotsDayExc是教學(xué)班課時超出量；slotsWeek-Uns(x)為行政班x的周最低課時不滿足量；slots Day-Uns(x)為行政班x的日最低課時嚴重不足程度。這三組數(shù)據(jù)均由算法1直接或間接計算得到，這里表示為函數(shù)CCl ass_so_min(t,S_CCcurrent,d)。這個算法本質(zhì)上是一個分支限界方法求解0/1規(guī)劃問題。為了提升搜索效率，在算法中采用了堆結(jié)構(gòu)存儲分支，并在分支上界計算的過程中篩除與子圖中任意節(jié)點存在不相連的節(jié)點。

算法1課程班集合占用最少課時量

輸入：課表t，當前需要考察的課程班集合S_CCcurrent，天序號d，課時沖突關(guān)系矩陣ConflictMatrix。

輸出：S_CCcurrent在d這天排出不沖突課表所需要的最小課時量。

該算法當中輸入的課時沖突關(guān)系矩陣Conflict-Matrix是一個維度為|S_CC|×|S_CC|的對稱bool方陣，這是一個不隨課表變化的變量，因此在算法表示中沒有列入輸入?yún)?shù)。在生成該矩陣時，矩陣中的每一個元素初始化為0，如果存在一個學(xué)生的選課模式包含A、B兩個課程班或一個老師被分配帶這兩個課程班，則將A課程班對應(yīng)編號的行和B課程班對應(yīng)編號的列所定位的元素值置為1。ConflictMatrix可以直接用作GCClass_conflics的鄰接矩陣，在這個算法中判斷兩個課程班是否存在連接就是通過查詢Conf lictMatrix得到的。堆activeHeap的每個分支將存儲一個長度可變的向量和一個自然數(shù)，以這個自然數(shù)作為成員大小對比的依據(jù)。S[1]表示集合S_CCcurrent中第一個課程班的課時量，∑S[c1]表示集合中與第一個課程班存在直接連接的課程班的課時量之和，∑S表示集合中所有課程班的課時量。從步驟8開始使用的0/1向量C_visit與最大堆activeHeap所存儲的分支向量結(jié)構(gòu)相同，所有標記為1的節(jié)點構(gòu)成的子集可以被視為一個全連接子圖。C_visit的長度表示當前分支順序訪問到的節(jié)點，“位置在C_visit的長度之后”表示當前分支沒有訪問到的節(jié)點所處的位置，對于C_visit沒有訪問到的節(jié)點，如果與所有已經(jīng)訪問到節(jié)點中被標記為1的節(jié)點都有直接連接，則可以確保將這個新節(jié)點添加到子圖中后依舊保持其全連接性，這些節(jié)點所對應(yīng)的課程班才有可能被添加。每一個分支的上界為當前分支已經(jīng)標記為1的課程班和沒有訪問到的課程班中可能被添加的課程班的課時總和。在這里選擇使用的上界計算方法可以在降低上界的同時不會產(chǎn)生很高的計算消耗。如果在C_visit中沒有包含任何1，則在計算上界的過程中需要將所有沒有訪問到的課程班的課時都加起來。

基于這個算法繼續(xù)使用如下公式計算上文中提到的三個部分：

公式（6）將所有教學(xué)班的課程班納入考察范圍，e(k)表示一個階躍函數(shù)，若實數(shù)k大于0則函數(shù)取值k否則函數(shù)取值0。有任何一天教學(xué)班無法排出不沖突課表都將帶來懲罰。

公式（7）中將與行政班x有關(guān)聯(lián)的教學(xué)班的課程班納入考察范圍，{C Classac|related(x)}表示x行政班的學(xué)生選課模式所包含的教學(xué)班的所有課程班集合。α是一個預(yù)先設(shè)置的松弛變量，可以看作一周當中相關(guān)教學(xué)班占用課時累計超出量的容忍上限，過多的課時超出將帶來懲罰。為提高兼容性，公式（7）的計算中允許出現(xiàn)一些天的少量課時超出。

公式（8）中將每一天相關(guān)教學(xué)班最小占用課時的數(shù)量進行了累積，再加上行政班x的周最低課時需求后如果超出一周總時段數(shù)則將帶來懲罰。

在這個約束的計算過程中，得到的產(chǎn)物不只是可以作用于課表評價的“可以排出不沖突課表”的違反程度值(Unable)，每個行政班每天是否得到了足夠的空閑時段還將用于引導(dǎo)下面將要介紹的調(diào)整算子定向發(fā)揮作用，即計算slotsDayUns(x)的過程中相關(guān)教學(xué)班每天超出的課時占用量。用slotsDayOver(x,d)>0表示x行政班d天有課時不夠。

2.2.4 教學(xué)班課時占用壓縮

這是一個非必須的目標函數(shù)，需要結(jié)合排課任務(wù)來選擇配置。在教學(xué)班同時上課規(guī)則覆蓋大部分教學(xué)班時不需要添加此規(guī)則，但對于沒有設(shè)置教學(xué)班同時上課規(guī)則或規(guī)則覆蓋面較小的任務(wù)而言，教學(xué)班課表排課過程中的肆意分布可能導(dǎo)致在后期行政班排課過程中可用時段過少，這一狀況對于開設(shè)重點科目的行政班而言并不理想。在某些整體課時安排非常緊湊的任務(wù)當中，可能出現(xiàn)教學(xué)班占用過多課時直接導(dǎo)致行政班無法排課這一狀況，此時需要用這個目標函數(shù)來引導(dǎo)盡量壓縮教學(xué)班占用的時段。教學(xué)班課時占用壓縮目標函數(shù)和上面提到的周最低課時不滿足量計算部分相似。但這里使用的不是階躍函數(shù)而是分段函數(shù)，具體公式如下：

2.2.5 滿足行政班可用排課時段

由于先于行政班排出的課表，排教學(xué)班課表的過程不受行政班課時的直接影響。教學(xué)班排課過程中課時不沖突這單一約束很容易滿足，但不加限制的排課將減少接下來的行政班排課的可用時段甚至直接導(dǎo)致無法排課。得到教學(xué)班的完整課表后，從一個行政班的角度進行限制，其相關(guān)教學(xué)班占用時段都不能安排行政班課時，這可以從根本上保障學(xué)生上課不沖突。行政班獲得的可用時段即可從所有時段中去除這些班級不排課時段得到。

承接上面的“可排出不沖突課表的課時分配”約束條件和“教學(xué)班課時占用壓縮”目標函數(shù)設(shè)計了“行政班可用排課時段足夠”這一約束條件和目標函數(shù)，來提升行政班排課質(zhì)量。排除所有相關(guān)教學(xué)班有課的時段后即可得到每天和一周行政班可用時段數(shù)，從一天可用時段數(shù)的角度來評測是目標函數(shù)，從一周可用時段數(shù)的角度來評測是約束條件。每天的排課空間偶有不足可以接受，因此設(shè)置了最小化日時段不滿足量，但一周可用時段數(shù)必須滿足下限，即周時段不滿足量必須為0。

2.2.6 課時優(yōu)選

該目標函數(shù)在排課算法中廣為使用[5，7]，評測方式可簡單描述為不同科目有不同的時段選擇偏好，如高考必考科目傾向于選擇上午前幾節(jié)這一時段，而體育等科目選擇上午最后一節(jié)會有更好效果等。這一目標函數(shù)的細節(jié)在本文中不再贅述，僅給出如下測算公式：

公式中cc(slots,t)為課表t中課程班cc所有課時所使用的時段，如果該課程班在課表中沒有課時則為空集。score(cc,loc)為cc課程班在loc這個時段位置處的偏好得分，取值范圍為{0，1，2}，分別表示不推薦使用、一般和推薦使用。為了和其他目標函數(shù)以最小化為目的相一致，這里取用3減去得分值作為時段選擇不合適程度的度量。importantcc表示課程班cc的重要程度，通常與對應(yīng)科目相關(guān)，也可細分到具體課程班。該目標函數(shù)將會遍歷所有課程班的所有在課表中的課時。

3 課表（解）的表示與優(yōu)化算子

在優(yōu)化中仍然采用傳統(tǒng)二維課表集的形式來記錄中間解。這樣可以保持每個課程班的課時數(shù)不會在優(yōu)化操作中變化，同一班級多個課程班之間課時不重疊，并且一天的課時總數(shù)不會超過時段數(shù)。

在天課時分配階段決策變量用CClassac(slots,t,d)即可表示。具體課時出現(xiàn)的時段是否為優(yōu)選時段以及是否與其他班級的課表在這一時段處存在沖突都不會影響當前優(yōu)化。這也意味著一張課表內(nèi)同一天的兩個時段互換內(nèi)容不會引起目標函數(shù)變化。在課時分配階段設(shè)計了如下三個算子：無評價均勻分布算子、同時上課修正和轉(zhuǎn)移算子、不可排課情況下的教學(xué)班課時轉(zhuǎn)移算子。

在天內(nèi)課表優(yōu)化階段則必須要基于課表結(jié)構(gòu)來表示。如前文所述這一階段將不進行天之間的課時交換，因此部分優(yōu)化操作、目標函數(shù)和約束違反的計算可以分天獨立進行。此外還對課表初始化和課時交換做了修改以確保在課表變化過程中同時上課的滿足程度不變。

3.1 無評價均勻分布算子

設(shè)計該算子的目的在于平衡每天課時，不需要對課表進行目標函數(shù)計算就可以直接得到盡可能滿足課時理想分布的課表。由于在這一步當中不考慮由同一個老師授課或同一個學(xué)生上課引起的課表之間相互關(guān)聯(lián)，每個班的課表調(diào)整可以獨立進行。采用的基本策略是將課表中所有應(yīng)當取出的課時全部取出后再依次放回到同科目課時最少并且有空閑時段的天。

以一個行政班的一個課程班為例，首先取出所有超過1課時的天當中除第一個課時之外的其他課時。若理想分布中不是每天都有課，則再以10%的概率取出一天當中所有剩余課時。所有課程班完成課時取出后重新置入剛才取出的所有課時。在放置每個課時之前，需要先統(tǒng)計出該班每天可以放置課程的空閑時段的數(shù)量availd。對于一個取出的課程班課時t，計算d天的課時放置壓力Pd(t)，壓力越大的天越不應(yīng)該被選擇，下面的計算公式中countd(t)代表d天課表中與t同科目的已有的課時數(shù)量。

這里的壓力值可能為負數(shù)，為方便用輪盤賭方式選擇放置到哪一天，采用歸一化方法將壓力值取負數(shù)并映射到0到1區(qū)間內(nèi)，然后將每個映射值除以映射后所有值的和作為選擇概率。從壓力值的計算公式中可以看出，對于該天已存在課時的情況，會有較大的壓力進而避免選擇該天。如果每天都已經(jīng)分布了相同課時則這些存在的課時不會影響選擇。

該算子可能破壞原本已經(jīng)滿足課時理想分布的科目的課時分布，屬于一種比較大范圍的變化，因此不能頻繁使用，否則將影響算法的收斂性。但作為一種解的初始化操作是一種不錯的選擇，因為其運用了均勻分布這一啟發(fā)信息節(jié)省大量的目標函數(shù)值計算，同時又具有隨機性。由于沒有考慮到班與班之間的關(guān)聯(lián)，而導(dǎo)致無法對老師教案平齊進行優(yōu)化，因此還需要目標函數(shù)的引導(dǎo)和其他算子的精細調(diào)整才能實現(xiàn)教案平齊。

3.2 “同時上課修正算子”和“同時上課聯(lián)動轉(zhuǎn)移算子”

設(shè)計這兩個算子用于提升和保障教學(xué)班的課時分配階段中對同時上課規(guī)則的滿足。在修正算子中依然使用集中取出后再有序放回的策略。在取出課時的過程中對于滿足同時上課一致性的教學(xué)班集合不取出課時，而對于超出上限的成員教學(xué)班取出課時至其上限。雖然這將引起當天課時變化，但可以觀察到對任意成員而言當前課表所確定的課時上限是不會改變的，因此課時取出時的順序?qū)Y(jié)果沒有影響。放回過程則不然，必須從課時最多的成員到課時最少的成員逐個放回。在滿足放置一個課時后不超過課時上限且有空閑時段的天當中隨機挑選一天放置課時。如果無法找到這樣的位置則隨機挑選一個空閑時段放置。該修正算子將依次作用于每一條同時上課規(guī)則。

同時上課聯(lián)動轉(zhuǎn)移算子的作用范圍要相對較小，需要事先選定調(diào)整哪一組同時上課然后通過課時轉(zhuǎn)移實現(xiàn)對調(diào)兩天的課時數(shù)這一目的。該算子發(fā)揮作用需要同時上課規(guī)則內(nèi)滿足下列兩個條件中至少一條：（1）成員之間理想課時分布不一致；（2）理想課時分布中存在若干天不上課。根據(jù)規(guī)則中每個教學(xué)班在選定的兩天的課時差D，檢查課時相對較少的一天內(nèi)是否有足夠的空閑時段。如果有則將最先遇到的D課時轉(zhuǎn)移到課時較少的一天中，否則不進行轉(zhuǎn)移。聯(lián)動轉(zhuǎn)移算子的設(shè)計初衷是在不改變?nèi)魏慰颇康姆植祭硐氤潭惹闆r下，通過改換多課時或無課時的天來改變同時上課的整體分布，使得教學(xué)班的課時分布更為平均以及從行政班角度來觀察時占用課時更少，這一情況對應(yīng)于多個同時上課組之間允許（或必須）存在課時重疊。

3.3 不可排課情況下的教學(xué)班課時轉(zhuǎn)移算子

結(jié)合約束條件計算的結(jié)果slotsDayOver(x,d)，對行政班某天的缺少可用空閑時段這一情況，該算子將套用同時上課聯(lián)動轉(zhuǎn)移來針對性解決。算子輸入某一天D存在行政班缺少可用空閑時段，然后遍歷每一條同時上課規(guī)則，如果有其他天C比D這一天占用的課時數(shù)要少，則交換這一條同時上課規(guī)則C，D兩天的課時實現(xiàn)減少D天安排的課時數(shù)，這里推薦選擇占用的課時最少的一天作為C。鑒于一個行政班的相關(guān)教學(xué)班可能存在于多個同時上課組內(nèi)，不繼續(xù)細化針對單個行政班或同時上課規(guī)則進行處理，而是交給目標函數(shù)來引導(dǎo)優(yōu)化。D這天當中上課的教學(xué)班如果沒有被同時上課規(guī)則覆蓋到，則需要采用與上文中“無評價均勻分布算子”類似的方法來變換課表。集中從這一天中取出所有課時后，再放到其他天的空閑時段當中，如果該課程班的課時理想分布需要每天都有課時則為該天保留所需的最小課時，通常為1課時。

3.4 天內(nèi)課表優(yōu)化階段課表初始化和課時交換操作

天內(nèi)課表優(yōu)化階段不是本文的核心討論過程，本文也沒有做出主要貢獻，因此只對以下幾點與文獻[6]中使用的課表變換（生成鄰域）算子的差別進行說明。這一階段課時交換只發(fā)生在一天之內(nèi)的兩個課時之間，鄰域選擇必須限制在一天范圍內(nèi)的若干時段中。在教學(xué)班課表確定后，行政班課表當中將對有任何相關(guān)教學(xué)班上課的時段賦予特殊標記，這些位置不可置入任何課時，同時也不能參與到任何課時交換操作中。也就是說將成為“不再被視為空閑”的時段。

教學(xué)班的同時上課將由課表初始化和聯(lián)動交換策略保障。具體來說就是在初始化課表的過程中就參考同時上課規(guī)則，逐課時將組內(nèi)成員同步放置在相同時段，如果分配課時不同則對放置部分課時后仍有剩余的成員繼續(xù)同步放置操作。在課時交換中采用的聯(lián)動交換策略要求對選定的兩個時段內(nèi)同時上課規(guī)則涉及到的若干課表同時進行交換，進而從根本上保障任何課時交換操作都不會引起同時上課的滿足程度發(fā)生變化，于是也就沒有必要對此設(shè)計目標函數(shù)進行同時上課滿足程度測算了。

4 算法流程

4.1 目標函數(shù)和約束條件選擇

基于天課時分配的多階段新高考“走班”排課算法是4個階段順序進行的。每一階段都是一個優(yōu)化過程，輸入的初始課表為前一階段優(yōu)化得到的課表。最后一階段的輸出課表是最終的算法輸出課表。

第一階段優(yōu)化教學(xué)班課表課時分配，操作的決策變量為全體教學(xué)班課表，此時行政班課表為空，評價行政班課表的目標函數(shù)值和約束違反值全部記為0。目標函數(shù)和約束條件分別為：

這一階段考慮因素包含教學(xué)班課表每天的課時分布質(zhì)量，同時上課規(guī)則滿足，行政班可用空間最大化，以及不出現(xiàn)已知潛在不可排課因素。由于行政班課表尚未確定，這一階段只能通過目標函數(shù)來為未來行政班排課創(chuàng)造盡量寬松的空間。

第二階段優(yōu)化獲得教學(xué)班完整課表，操作的決策變量為全體教學(xué)班課表，采用文獻[6]中已有的模擬退火算法，同時改用上文提到的課表變換算子。目標函數(shù)和約束條件分別為：

該階段課表優(yōu)化的核心考慮因素是：（1）通過約束條件確保教學(xué)班之間不出現(xiàn)學(xué)生和老師課時沖突；（2）通過約束條件確保行政班一周排課空間足夠；（3）通過目標函數(shù)降低行政班排課難度，這其中要求每一天的教學(xué)班的課表可以為相關(guān)行政班保留足夠的可排課時段；（4）通過目標函數(shù)進一步優(yōu)化課程的時段選擇的合理性。這樣設(shè)置的依據(jù)在于該階段將完全確定教學(xué)班課表，行政班可用時段也將確定。這一階段輸出滿足約束條件的課表則說明可以繼續(xù)接下來的排課。

第三階段優(yōu)化行政班課表課時分配，操作的決策變量為全體行政班課表，教學(xué)班課表存在且不能改變。算法流程和優(yōu)化教學(xué)班課表課時分配相近，目標函數(shù)和約束條件分別為：

由于規(guī)則當中沒有涉及行政班的同時上課規(guī)則，這里與第一階段有不同。行政班課表排布過程可以充分利用可排課時段，因此不需要也不存在占用課時壓縮。這一階段僅保留了對行政班課時分布的優(yōu)化這一核心目標，核心難點在于因為教學(xué)班課表已經(jīng)存在導(dǎo)致可用時段不如第一階段豐富。

最終階段優(yōu)化獲得行政班完整課表，操作的決策變量為全體行政班課表，同優(yōu)化獲得教學(xué)班完整課表步驟相同。目標函數(shù)和約束條件分別為：

這一階段中課表已經(jīng)基本定型，僅需要天內(nèi)課表微調(diào)操作，因此所需要考慮的核心是不出現(xiàn)沖突。課時優(yōu)選依舊為深度優(yōu)化所需要考慮的目標。

可以將第一、三階段視為第二、四階段的前置優(yōu)化過程，所考慮的因素都為通過課時分布即可評價質(zhì)量或估計輸出課表對規(guī)則滿足程度以及課表可排性的目標函數(shù)和約束條件。這里將規(guī)則滿足的高壓力和復(fù)雜的跨天調(diào)整以及更大的課表調(diào)整自由度相結(jié)合，集中精力攻克走班排課除課時沖突外的難點。

4.2 一種適用于優(yōu)化教學(xué)班課表課時分配的爬山算法

第一階段優(yōu)化教學(xué)班課表課時分配是整個算法的核心部分，為此提出了一種改進的爬山算法來解決這一約束優(yōu)化問題。該算法借鑒了孟凡超等[20]用混合遺傳模擬退火算法解決軟件優(yōu)化配置問題的經(jīng)驗，融合了VNS機制提升爬山算法的搜索更優(yōu)解的能力。

啟發(fā)式算法看重的兩個重要能力在于向局部最優(yōu)收斂的能力和跳出局部最優(yōu)能力[21-22]，并不要求搜索最終停留在全局最優(yōu)處，而是通過記錄算法中找到的最優(yōu)解實現(xiàn)全局收斂。相較于簡單的爬山算法，VNS允許在相對較差解的附近進行有限代價的搜索以期望找到另一個局部最優(yōu)的解，因此添加VNS機制彌補了爬山算法易于陷入局部最優(yōu)的缺陷。在優(yōu)化算法運行初期，隨機產(chǎn)生的初始解很大概率處于一個目標函數(shù)較劣的局部最優(yōu)附近，因此借助VNS機制跳出該區(qū)域，使得當前最優(yōu)解向更優(yōu)的區(qū)域內(nèi)收斂。在向局部最優(yōu)收斂的過程中，采取的策略是遇到目標函數(shù)更優(yōu)的解或過于差的解時就終止VNS，并以當前最優(yōu)解為起點重新開始VNS，這種設(shè)計提升了收斂速度。在算法后期，已經(jīng)接近或達到較大范圍內(nèi)最優(yōu)解的情況下，VNS機制將主要保留向更遠區(qū)域探索的能力，從而提升輸出結(jié)果收斂到全局最優(yōu)的概率。

算法2給出了這個算法的偽代碼描述。

算法2優(yōu)化教學(xué)班課表課時分配的爬山算法

輸入：各教學(xué)班的各科目的課時安排；老師帶班情況以及教案分組；教學(xué)班同時上課規(guī)則；各行政班學(xué)生的選課模式；各行政班各科目的課時安排；總迭代次數(shù)total_iteration。

輸出：教學(xué)班課表。

在步驟1中放置教學(xué)班的課時在課表中的任意位置，保障課表是一個課時完整的初始解。步驟2通過執(zhí)行一次無評價均勻分布算子和同時上課修正算子提升了初始解的質(zhì)量。步驟4使用兩個課表變量保留優(yōu)化過程中間產(chǎn)生的歷史最優(yōu)解和臨時最優(yōu)解，歷史最優(yōu)解保障了算法的全局收斂性，這一做法借鑒了遺傳算法當中廣為使用的精英保留策略；而臨時最優(yōu)解提供了一定的局部搜索能力和探索解空間中其他區(qū)域的機會。步驟5設(shè)定了部分控制算法運行的參數(shù)，包括主循環(huán)次數(shù)和局部搜索嘗試次數(shù)。

步驟8起到一個策略選擇器的作用，這里采用隨機策略選擇的方式，因策略之間存在的差異，三種策略的選擇概率比為1∶2∶7。策略1使用的變換是對原有解較大范圍的變動，因此過多的使用將導(dǎo)致收斂速度變慢；策略2利用了約束條件計算中獲得的啟發(fā)信息，針對解決可能存在的約束條件不滿足并可以就這一情況的具體位置進行解的變化。在初期尋找滿足約束條件的解過程中發(fā)揮核心作用，若當前解已經(jīng)滿足約束條件，策略2等同于策略1。策略3是一種解的微調(diào)操作。對于有同時上課規(guī)則指導(dǎo)的排課任務(wù)而言，多課表的聯(lián)動調(diào)整將有利于避免打亂原本的同時上課課時分配一致性。對于沒有同時上課規(guī)則的排課任務(wù)而言，該策略重點通過單教學(xué)班的隨機跨天課時調(diào)整來壓縮教學(xué)班課時的占用，這一步有可能帶來目標函數(shù)中其他指標的惡化，所以只能重復(fù)執(zhí)行很少次。

步驟28僅僅測算當前解的約束違反程度，在當前解不滿足約束條件的情況下不測算其目標函數(shù)值，以減少不必要的計算消耗。步驟30保留了尋找滿足約束條件的解的能力，以應(yīng)對滿足約束條件的解比較難以尋找的排課任務(wù)。步驟33至35和步驟46至48的設(shè)計初衷是在當前解的目標函數(shù)值與歷史最優(yōu)解的目標函數(shù)值差距不太大的情況下保留其通過上述變化算子繼續(xù)探索的機會。臨時最優(yōu)解在此充當局部尋優(yōu)搜索起點，指導(dǎo)當前解向更優(yōu)解變化，若多次嘗試均未超越歷史最優(yōu)，則從歷史最優(yōu)解重新出發(fā)重新探索，這期間如有產(chǎn)生不滿足約束條件的解也可以回到臨時最優(yōu)解重新搜索。整個算法在尋找第一個滿足約束條件解的過程中采用貪心的策略，并在獲得滿足約束條件的解之后采用對違反約束條件零容忍的態(tài)度進行優(yōu)化，以期達到快速穩(wěn)定的找到滿足約束條件解的目的。針對滿足約束條件的解，在尋優(yōu)過程中采用適當寬松的策略允許在非最優(yōu)解附近進行局部搜索。

5 數(shù)值實驗

5.1 實驗數(shù)據(jù)與性能評測方式

本文選取了一個人工生成的排課案例和兩個改編自真實學(xué)校的排課案例來測試該算法的性能。評測采取若干次獨立運行后統(tǒng)計輸出課表的各項指標的均值和方差來體現(xiàn)課表質(zhì)量以及穩(wěn)定性，這些指標包括教案平齊、課時分布均勻、教學(xué)班同時上課、行政班天可用時段以及課時優(yōu)選。優(yōu)化算法的計算用時也一并給出。穩(wěn)定性除了目標函數(shù)值的方差外，成功排出滿足約束條件的課表次數(shù)占總實驗次數(shù)的比例（成功率）也將同步給出。

人工生成的案例包含4個行政班和10個教學(xué)班。課表中總共出現(xiàn)11門科目、30個選課模式、18位老師，該數(shù)據(jù)不包含同時上課規(guī)則。一周上課時段為6天，每天9課時。

兩個真實案例為對某高中的排課案例進行適當修改后得到的。其中中等規(guī)模案例包括8個行政班和15個教學(xué)班。課表中總共出現(xiàn)11門科目、359位學(xué)生（共20個選課模式）、28位老師、三條同時上課規(guī)則。一周上課時段為5天，每天8課時。大規(guī)模案例包括20個行政班，45個教學(xué)班。課表中總共出現(xiàn)14門科目、854位學(xué)生（共95個選課模式）、70位老師、7條同時上課規(guī)則。一周上課時段為6天，每天9課時。

評價課表質(zhì)量將在完整獲得課表后進行，也就是對一個真實課表進行評判。指標采用上文中給出的計算公式進行度量。若通過計算發(fā)現(xiàn)，優(yōu)化得到的教學(xué)班課表無法再排出不存在學(xué)生沖突的行政班課表，或教學(xué)班本身存在學(xué)生或老師課時沖突，則終止后續(xù)優(yōu)化并記為排出課表不滿足約束條件，同時將不再排行政班課程。行政班課表中存在課時沖突同樣也將被視為排出課表不滿足約束條件。所有呈現(xiàn)在圖表中的目標函數(shù)值和計算用時的測算均基于滿足約束條件的課表來測算。

5.2 優(yōu)化算法相關(guān)參數(shù)設(shè)定與實驗平臺配置

在教學(xué)班課時分配階段：總迭代次數(shù)為500，滿足課時均勻的教案平齊中的權(quán)重w1=5/6，行政班的日最低課時嚴重不足程度α等于；在行政班課時分配階段：總迭代次數(shù)為100，其余參數(shù)與教學(xué)班課時分配階段一致；在天內(nèi)課表優(yōu)化階段中使用的模擬退火算法[6]初始溫度為2.5，停止溫度為1，降溫速度參數(shù)為0.99，較差解接受控制參數(shù)為0.5，相同溫度下內(nèi)循環(huán)次數(shù)為200。

仿真實驗使用C++實現(xiàn)，集成開發(fā)環(huán)境為Visualstudio 2019。算法運行計算機配備如下：操作系統(tǒng)，Windows 10專業(yè)版64位；處理器，英特爾Core i7-7700 3.60 GHz四核；內(nèi)存，16 GB DDR4 2 400 MHz。全部實驗采用單線程進行。

5.3 實驗結(jié)果分析

表1中給出了本文提出的算法在三組數(shù)據(jù)集上的運行結(jié)果數(shù)值統(tǒng)計。該表格中的每一組實驗數(shù)據(jù)中成功率是基于200次獨立重復(fù)實驗得到的，其他指標統(tǒng)計是基于這200次實驗中成功排出的所有課表中隨機選取100張課表得到的。針對每個數(shù)據(jù)集表格中依次給出平均優(yōu)化運行時間、教案平齊不滿足程度、課時分布均勻性不滿足程度、教學(xué)班同時上課不滿足程度、行政班每天可用的排課時段的緊缺程度、課時優(yōu)選不滿足程度的平均值、最優(yōu)值、方差，這些指標都是越小越好的。人工生成案例中沒有設(shè)計同時上課規(guī)則因此這一項為空。為研究同時上課規(guī)則的有無對課表優(yōu)化的影響，也在刪去同時上課規(guī)則后的真實案例上進行了實驗，結(jié)果也包含在表1中。

從表1中可以看出，本文設(shè)計的優(yōu)化算法可以以較高的成功率求得滿足約束條件的課表，大規(guī)模問題平均運行時間在10 min左右，屬于可以接受的范圍。有無同時上課規(guī)則對各項指標均有影響，其中中等規(guī)模真實案例中教案平齊、課時分布均勻受影響較大，無同時上課規(guī)則的案例相關(guān)指標有明顯提升。大規(guī)模真實案例中成功率、運行時間、行政班天可用時段也表現(xiàn)出受影響明顯。同時上課規(guī)則的有無還對部分目標數(shù)次運行所能達到的極值存在影響，例如中規(guī)模真實案例中的教案平齊和兩個真實案例下的行政班天可用時段。

表1 運行結(jié)果數(shù)值統(tǒng)計

通過大量重復(fù)實驗和改變目標函數(shù)權(quán)重以及人工微調(diào)課表方式，對這三組案例在教案平齊和課時均勻分布這兩個目標上的極限最優(yōu)值進行了探索。人工生成案例在教案平齊違反上可以降低到0；大規(guī)模案例中教案平齊違反可以降低到82，課時分布不均勻可以降低到0。由此可見該算法在人工生成案例上尋找不違反教案平齊的課表的能力有待提升，在其他指標方面隨機多次運行可以十分接近指標的極值。課時優(yōu)選這一目標的優(yōu)化不是本文的重點，因此沒有對這個評價指標進行分析。本文推測，大規(guī)模案例實驗中若干評測指標未能降低到0主要是因為問題規(guī)模過大，需要消耗更多的計算代價，同時規(guī)則設(shè)置可能存在不合理之處，使得規(guī)則之間存在矛盾關(guān)系導(dǎo)致課表整體質(zhì)量不佳。

繼續(xù)對實驗中產(chǎn)生的課表進行分析，拆分出教學(xué)班和行政班測算在分課表上的教案平齊不滿足程度。在大規(guī)模真實案例和人工生成案例這兩組數(shù)據(jù)的實驗中生成的課表這一指標表現(xiàn)不夠理想，因此對這些課表進行了觀測，大規(guī)模真實案例采用的課表來自有同時上課規(guī)則的案例。首先以完整課表的教案平齊不滿足程度對產(chǎn)生的所有課表進行排序，然后依次取10%的課表對其教學(xué)班的教案平齊不滿足程度以及行政班的教案平齊不滿足程度求平均值，其結(jié)果如圖2（a）所示。從圖中可以看出對教案平齊違反程度貢獻最大的是行政班的教案平齊違反，而且其增長直接帶來整體課表的教案平齊違反程度提升。教學(xué)班的教案平齊違反較少，且變化不明顯。使用本文提出的算法可以獲得較為理想的教學(xué)班課表，但行政班課表質(zhì)量還有待提升。

同時還分別以行政班課表和教學(xué)班課表的教案平齊不滿足程度排序課表后畫出相似折線圖，圖2（b）和圖2（c）。圖示結(jié)果表明教學(xué)班課表的教案平齊違反程度對整體課表教案平齊不滿足貢獻有限。圖3是對人工生成案例下生成的課表觀測的結(jié)果，相關(guān)結(jié)論與大規(guī)模真實案例一致。

圖2 教案平齊滿足與位次分組的關(guān)系（大規(guī)模）

圖3 教案平齊滿足與位次分組的關(guān)系（人工生成）

前面實驗初步表明同時上課規(guī)則的有無對中等規(guī)模真實案例的課表優(yōu)化結(jié)果有影響。為進一步觀察教學(xué)班同時上課規(guī)則部分缺失情況下課表優(yōu)化結(jié)果的差別，選擇受影響最為明顯的中規(guī)模真實案例進行下面的實驗。首先隨機刪除部分教學(xué)班同時上課規(guī)則生成12組新的同時上課規(guī)則。具體做法是從原有同時上課規(guī)則中分別整班隨機刪除20%、40%和60%的教學(xué)班，每一次隨機產(chǎn)生4套不同的規(guī)則形成獨立測試案例，這樣獲得了除同時上課規(guī)則不同外其余數(shù)據(jù)和規(guī)則完全相同的12組測試數(shù)據(jù)。沒有選擇從規(guī)則中刪除80%的教學(xué)班，原因在于將出現(xiàn)多條規(guī)則只包含一個教學(xué)班這種無效同時上課規(guī)則的情形，這一情況下排課任務(wù)無異于沒有同時上課規(guī)則。每一組數(shù)據(jù)下進行30次獨立重復(fù)實驗，得到課表在教案平齊、課時分布均勻、行政班天可用時段、課時優(yōu)選這四個目標上的表現(xiàn)如表2～4所示。在這一實驗當中教案平齊、課時分布均勻、行政班天可用時段基本符合指標隨同時上課涵蓋教學(xué)班的數(shù)目減少而變差的預(yù)期。不同隨機案例表現(xiàn)出不同的平均結(jié)果，說明相同涵蓋范圍的同時上課規(guī)則本身還存在對課表優(yōu)化引導(dǎo)的差別。觀察不同同時上課規(guī)則對應(yīng)的最優(yōu)結(jié)果，發(fā)現(xiàn)規(guī)則差別對其影響較小，并且這一現(xiàn)象在大規(guī)模真實案例有無同時上課規(guī)則的兩組實驗結(jié)果中也可以觀察到。

表2 刪除20%同時上課規(guī)則后課表質(zhì)量的統(tǒng)計結(jié)果

表3 刪除40%同時上課規(guī)則后課表質(zhì)量的統(tǒng)計結(jié)果

表4 刪除60%同時上課規(guī)則后課表質(zhì)量的統(tǒng)計結(jié)果

6 結(jié)束語

本文針對“新高改”政策下的高中走班制教學(xué)排課問題進行了研究，設(shè)計了一套基于天課時分配的多階段課表優(yōu)化算法。從每天課時分配的角度對課時分布均勻程度、授課老師教案平齊滿足、分配課時可以排出不沖突課表等目標函數(shù)和約束條件進行了數(shù)學(xué)建模。還在三組測試數(shù)據(jù)上驗證了所提出算法的性能。實驗結(jié)果表明該算法在可以接受的時間內(nèi)以較大概率得到課時不沖突課表。除大規(guī)模真實案例對教案平齊滿足程度優(yōu)化不理想外，其他參數(shù)指標均可得到較理想的優(yōu)化。進一步觀測發(fā)現(xiàn)，教案平齊違反主要來自于行政班課表，同時上課規(guī)則的有無和對教學(xué)班的覆蓋完整程度影響到對其他目標的優(yōu)化。因此建議在排課之前充分準備教學(xué)班的同時上課規(guī)則。

排課是一個復(fù)雜并且需求多樣的優(yōu)化問題，需要根據(jù)排課任務(wù)所包含的數(shù)據(jù)規(guī)模以及難點配置算法參數(shù)和選用算子。未來還將進一步改進算法適配問題的能力，并探索走班排課問題復(fù)雜程度的分析方法。期望能在排課之前估計最終課表質(zhì)量的上限和指出規(guī)則設(shè)置的不合理之處，供用戶調(diào)整排課方案。