• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    天課時分配下的多階段新高考走班制排課算法

    2021-06-11 10:17:22張宇瞳郝星星
    計算機工程與應用 2021年11期
    關鍵詞:規(guī)則優(yōu)化

    張宇瞳,劉 靜,郝星星

    西安電子科技大學 人工智能學院,西安710071

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

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

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

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

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

    1 相關工作與研究動機

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

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

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

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

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

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

    2.1 課表基本元素

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

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

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

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

    (2)所有課程班的集合表示為S_CC。

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

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

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

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

    圖1 學生選課模式,課程班,老師對應關系

    圖1給出了學生選課模式、課程班、老師之間的對應關系示例。一個學生選課模式對應多個課程班,一個課程班可用包含多個學生選課模式,每個課程班必須與至少一個學生選課模式相對應;一個老師可以帶若干課程班,一個課程班由且只由一個老師來帶。

    2.2 目標函數(shù)

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

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

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

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

    公式(1)中sortdecrease表示將集合A中的所有元素從大到小排序并構成一個一維向量,該公式將各課程班的各天開設的課時數(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ū)間內只有一天上課而且所上課時數(shù)相同;滿足日教案平齊的課時分布是:每天各個課程班具有相同的課時。

    滿足課時均勻的教案平齊這個目標為兩個部分的加權和:

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

    2.2.2 同時上課課時一致

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

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

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

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

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

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

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

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

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

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

    輸入:課表t,當前需要考察的課程班集合S_CCcurrent,天序號d,課時沖突關系矩陣ConflictMatrix。

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

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

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

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

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

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

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

    2.2.4 教學班課時占用壓縮

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

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

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

    承接上面的“可排出不沖突課表的課時分配”約束條件和“教學班課時占用壓縮”目標函數(shù)設計了“行政班可用排課時段足夠”這一約束條件和目標函數(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的重要程度,通常與對應科目相關,也可細分到具體課程班。該目標函數(shù)將會遍歷所有課程班的所有在課表中的課時。

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

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

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

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

    3.1 無評價均勻分布算子

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

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

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

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

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

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

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

    3.3 不可排課情況下的教學班課時轉移算子

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

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

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

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

    4 算法流程

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

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

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

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

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

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

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

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

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

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

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

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

    第一階段優(yōu)化教學班課表課時分配是整個算法的核心部分,為此提出了一種改進的爬山算法來解決這一約束優(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ū)域內收斂。在向局部最優(yōu)收斂的過程中,采取的策略是遇到目標函數(shù)更優(yōu)的解或過于差的解時就終止VNS,并以當前最優(yōu)解為起點重新開始VNS,這種設計提升了收斂速度。在算法后期,已經(jīng)接近或達到較大范圍內最優(yōu)解的情況下,VNS機制將主要保留向更遠區(qū)域探索的能力,從而提升輸出結果收斂到全局最優(yōu)的概率。

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

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

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

    輸出:教學班課表。

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

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

    步驟28僅僅測算當前解的約束違反程度,在當前解不滿足約束條件的情況下不測算其目標函數(shù)值,以減少不必要的計算消耗。步驟30保留了尋找滿足約束條件的解的能力,以應對滿足約束條件的解比較難以尋找的排課任務。步驟33至35和步驟46至48的設計初衷是在當前解的目標函數(shù)值與歷史最優(yōu)解的目標函數(shù)值差距不太大的情況下保留其通過上述變化算子繼續(xù)探索的機會。臨時最優(yōu)解在此充當局部尋優(yōu)搜索起點,指導當前解向更優(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ù)與性能評測方式

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

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

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

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

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

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

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

    5.3 實驗結果分析

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

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

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

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

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

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

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

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

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

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

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

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

    6 結束語

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

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

    猜你喜歡
    規(guī)則優(yōu)化
    超限高層建筑結構設計與優(yōu)化思考
    撐竿跳規(guī)則的制定
    民用建筑防煙排煙設計優(yōu)化探討
    關于優(yōu)化消防安全告知承諾的一些思考
    數(shù)獨的規(guī)則和演變
    一道優(yōu)化題的幾何解法
    由“形”啟“數(shù)”優(yōu)化運算——以2021年解析幾何高考題為例
    規(guī)則的正確打開方式
    幸福(2018年33期)2018-12-05 05:22:42
    讓規(guī)則不規(guī)則
    Coco薇(2017年11期)2018-01-03 20:59:57
    TPP反腐敗規(guī)則對我國的啟示
    国产精品精品国产色婷婷| 欧美另类亚洲清纯唯美| 高清在线国产一区| 可以在线观看毛片的网站| 搡老熟女国产l中国老女人| 国产高清视频在线播放一区| 男人舔女人下体高潮全视频| 国产一区二区三区在线臀色熟女| 性色avwww在线观看| 亚洲avbb在线观看| 黄色一级大片看看| 久久精品91蜜桃| 亚洲精品亚洲一区二区| 嫩草影院精品99| 国产精品一区www在线观看 | 久久人人爽人人爽人人片va| 国产真实乱freesex| 男女那种视频在线观看| 国产午夜福利久久久久久| 老熟妇仑乱视频hdxx| 美女高潮喷水抽搐中文字幕| 亚洲欧美日韩高清专用| 欧美成人免费av一区二区三区| 欧美高清成人免费视频www| 国产女主播在线喷水免费视频网站 | 国产高清视频在线播放一区| 久久久久久久午夜电影| 男人和女人高潮做爰伦理| 在线播放国产精品三级| 亚洲中文字幕日韩| 亚洲av免费在线观看| 在线观看午夜福利视频| 久久人妻av系列| 一级黄色大片毛片| 国产精品国产三级国产av玫瑰| 亚洲五月天丁香| 国产精品久久电影中文字幕| 婷婷精品国产亚洲av| 在线观看一区二区三区| 成人无遮挡网站| 免费黄网站久久成人精品| 国产精品乱码一区二三区的特点| 日本色播在线视频| 欧美成人a在线观看| 午夜福利成人在线免费观看| av天堂中文字幕网| 久久久久久久久久黄片| 在线免费十八禁| 天堂网av新在线| 日本-黄色视频高清免费观看| 99热网站在线观看| 美女cb高潮喷水在线观看| 亚洲国产精品久久男人天堂| 在线天堂最新版资源| 我的女老师完整版在线观看| 亚洲欧美日韩高清专用| 国产精品人妻久久久久久| 夜夜看夜夜爽夜夜摸| 国产精品免费一区二区三区在线| 久久久国产成人免费| 黄色丝袜av网址大全| 国产黄片美女视频| 五月玫瑰六月丁香| 午夜精品久久久久久毛片777| 亚洲在线观看片| 999久久久精品免费观看国产| 久久久久久久久久黄片| 51国产日韩欧美| 国产激情偷乱视频一区二区| 日韩精品青青久久久久久| 久久精品综合一区二区三区| xxxwww97欧美| 欧美人与善性xxx| 亚洲欧美日韩无卡精品| 性插视频无遮挡在线免费观看| 蜜桃久久精品国产亚洲av| 亚洲av五月六月丁香网| 一进一出好大好爽视频| 国产美女午夜福利| 亚洲va日本ⅴa欧美va伊人久久| 欧美日韩精品成人综合77777| 欧美成人性av电影在线观看| 中文在线观看免费www的网站| 国产熟女欧美一区二区| 哪里可以看免费的av片| 麻豆精品久久久久久蜜桃| 日日摸夜夜添夜夜添av毛片 | 欧美成人免费av一区二区三区| 国产精品国产高清国产av| 国产精品av视频在线免费观看| 一个人观看的视频www高清免费观看| 99久国产av精品| 国产精品国产高清国产av| 国产精品av视频在线免费观看| 亚洲精品久久国产高清桃花| 国产精品野战在线观看| 精品久久久久久,| 两个人视频免费观看高清| 日韩欧美在线二视频| 国产老妇女一区| 免费不卡的大黄色大毛片视频在线观看 | 亚洲最大成人手机在线| 在线国产一区二区在线| 一区福利在线观看| 99在线视频只有这里精品首页| 联通29元200g的流量卡| 深夜a级毛片| 免费人成视频x8x8入口观看| 日韩欧美国产在线观看| 国产精品久久久久久亚洲av鲁大| 99国产精品一区二区蜜桃av| 成人美女网站在线观看视频| 久久精品人妻少妇| 久久久久久久精品吃奶| 国产色婷婷99| 精品久久久久久,| 免费搜索国产男女视频| 欧美潮喷喷水| 神马国产精品三级电影在线观看| 99国产精品一区二区蜜桃av| 国内精品久久久久精免费| ponron亚洲| 听说在线观看完整版免费高清| 久久久国产成人精品二区| 日韩精品中文字幕看吧| 九色成人免费人妻av| 在线免费观看不下载黄p国产 | 一区二区三区免费毛片| 成人精品一区二区免费| 国产一区二区三区av在线 | 噜噜噜噜噜久久久久久91| 免费看av在线观看网站| 又紧又爽又黄一区二区| 久久久精品欧美日韩精品| 99久国产av精品| 国产高清不卡午夜福利| 嫩草影院精品99| 婷婷丁香在线五月| 免费在线观看影片大全网站| 免费看美女性在线毛片视频| 在线播放国产精品三级| 大型黄色视频在线免费观看| 日本免费a在线| 别揉我奶头 嗯啊视频| av.在线天堂| 成年女人永久免费观看视频| 欧美另类亚洲清纯唯美| 日韩一本色道免费dvd| 日韩欧美免费精品| 精品久久久噜噜| 亚洲精品一区av在线观看| 99国产精品一区二区蜜桃av| 亚洲av中文字字幕乱码综合| 午夜福利欧美成人| 日本欧美国产在线视频| 欧美精品啪啪一区二区三区| 天堂√8在线中文| 99热这里只有是精品在线观看| 国产精品一区二区三区四区免费观看 | 亚洲18禁久久av| x7x7x7水蜜桃| 九九在线视频观看精品| 国产精品女同一区二区软件 | 国产精品人妻久久久影院| 少妇人妻精品综合一区二区 | 精品久久久久久成人av| 999久久久精品免费观看国产| 中文字幕熟女人妻在线| 精品久久久久久成人av| 日韩欧美国产一区二区入口| 久久久久国内视频| 久久精品国产亚洲av涩爱 | 日韩欧美精品v在线| 嫩草影院入口| 在线播放无遮挡| 男女做爰动态图高潮gif福利片| 一本一本综合久久| 婷婷亚洲欧美| a级毛片免费高清观看在线播放| 中出人妻视频一区二区| 国内少妇人妻偷人精品xxx网站| 少妇裸体淫交视频免费看高清| 高清在线国产一区| 日韩人妻高清精品专区| 一边摸一边抽搐一进一小说| 韩国av一区二区三区四区| 久久精品久久久久久噜噜老黄 | 日本五十路高清| 嫩草影院入口| 伦精品一区二区三区| 亚洲av.av天堂| 美女 人体艺术 gogo| 国产乱人伦免费视频| 一级a爱片免费观看的视频| 国产精品久久视频播放| 亚洲精华国产精华液的使用体验 | 国产男靠女视频免费网站| 久久午夜福利片| 真人做人爱边吃奶动态| 久久精品国产清高在天天线| 很黄的视频免费| 国产乱人伦免费视频| 色哟哟·www| 欧美日韩亚洲国产一区二区在线观看| 日韩欧美国产一区二区入口| 亚洲精品影视一区二区三区av| 成人一区二区视频在线观看| 免费av毛片视频| 能在线免费观看的黄片| 国产精品98久久久久久宅男小说| 免费大片18禁| 免费人成在线观看视频色| 欧美日韩精品成人综合77777| 好男人在线观看高清免费视频| 两性午夜刺激爽爽歪歪视频在线观看| 有码 亚洲区| 欧洲精品卡2卡3卡4卡5卡区| 国产精品福利在线免费观看| 成人av在线播放网站| 少妇高潮的动态图| 中文字幕熟女人妻在线| 大又大粗又爽又黄少妇毛片口| 少妇被粗大猛烈的视频| 国产视频内射| 午夜福利高清视频| 国产精品久久久久久av不卡| 日韩在线高清观看一区二区三区 | 成人亚洲精品av一区二区| 一区二区三区高清视频在线| 亚洲五月天丁香| 日韩在线高清观看一区二区三区 | 老司机福利观看| 两个人的视频大全免费| 欧美成人一区二区免费高清观看| 熟妇人妻久久中文字幕3abv| 欧美一区二区国产精品久久精品| 乱码一卡2卡4卡精品| 日韩欧美精品v在线| 久久久色成人| 黄色配什么色好看| 噜噜噜噜噜久久久久久91| 最近最新中文字幕大全电影3| 日本与韩国留学比较| 日本一二三区视频观看| 久久久久国产精品人妻aⅴ院| 变态另类丝袜制服| 又黄又爽又刺激的免费视频.| 国产真实伦视频高清在线观看 | 亚洲欧美日韩无卡精品| 非洲黑人性xxxx精品又粗又长| 熟女电影av网| 性插视频无遮挡在线免费观看| 亚洲国产日韩欧美精品在线观看| 免费高清视频大片| 精品人妻一区二区三区麻豆 | 99热网站在线观看| 校园春色视频在线观看| 日韩人妻高清精品专区| 最近在线观看免费完整版| 国产精品一区二区三区四区免费观看 | 制服丝袜大香蕉在线| 精品国内亚洲2022精品成人| 久久久久久久久久黄片| 色尼玛亚洲综合影院| 亚洲美女黄片视频| 国产成人av教育| 中文亚洲av片在线观看爽| 男女之事视频高清在线观看| 久久久久免费精品人妻一区二区| 久久久久久久午夜电影| 午夜精品一区二区三区免费看| 久久精品国产自在天天线| 久久精品国产亚洲网站| 麻豆久久精品国产亚洲av| 毛片一级片免费看久久久久 | 免费高清视频大片| 色尼玛亚洲综合影院| 亚洲成人精品中文字幕电影| 欧美色欧美亚洲另类二区| 麻豆久久精品国产亚洲av| 精品久久久久久久末码| 免费无遮挡裸体视频| 偷拍熟女少妇极品色| 99热精品在线国产| 丰满人妻一区二区三区视频av| 久久草成人影院| 男女啪啪激烈高潮av片| 精品人妻熟女av久视频| 一进一出抽搐gif免费好疼| 国产成人影院久久av| 色综合色国产| 欧美zozozo另类| 欧美日本视频| 国产精品自产拍在线观看55亚洲| 18+在线观看网站| 国产亚洲91精品色在线| 久久国产精品人妻蜜桃| 久久精品国产清高在天天线| 精品久久久久久久久久久久久| 久久国产乱子免费精品| 女人被狂操c到高潮| 嫩草影视91久久| 最近在线观看免费完整版| 欧美区成人在线视频| 日韩av在线大香蕉| 白带黄色成豆腐渣| 亚洲黑人精品在线| 99久久九九国产精品国产免费| 欧美一区二区亚洲| 国产亚洲精品av在线| АⅤ资源中文在线天堂| 国产色婷婷99| 亚洲av成人av| 联通29元200g的流量卡| 少妇的逼好多水| 老师上课跳d突然被开到最大视频| 午夜福利欧美成人| 精品99又大又爽又粗少妇毛片 | 乱码一卡2卡4卡精品| 一区福利在线观看| 亚洲美女搞黄在线观看 | 精品免费久久久久久久清纯| 亚洲性久久影院| 日韩强制内射视频| netflix在线观看网站| 久久精品影院6| 日本一本二区三区精品| 亚洲精品色激情综合| 在线播放国产精品三级| 一进一出好大好爽视频| 老师上课跳d突然被开到最大视频| 国内揄拍国产精品人妻在线| 亚洲不卡免费看| 18禁黄网站禁片免费观看直播| 日本撒尿小便嘘嘘汇集6| 亚洲专区中文字幕在线| 在线免费观看不下载黄p国产 | 亚洲av不卡在线观看| 国产av在哪里看| 狂野欧美白嫩少妇大欣赏| 两个人的视频大全免费| 人妻少妇偷人精品九色| 22中文网久久字幕| 久久亚洲真实| 蜜桃久久精品国产亚洲av| 窝窝影院91人妻| 黄色欧美视频在线观看| 男人舔奶头视频| 毛片一级片免费看久久久久 | 国产在线精品亚洲第一网站| 国产爱豆传媒在线观看| 国产一区二区亚洲精品在线观看| 精品无人区乱码1区二区| 国产精品乱码一区二三区的特点| 亚洲精品久久国产高清桃花| 国产久久久一区二区三区| 国内精品美女久久久久久| 国内毛片毛片毛片毛片毛片| 亚洲avbb在线观看| 一区二区三区激情视频| 免费看美女性在线毛片视频| 亚洲国产精品久久男人天堂| av在线观看视频网站免费| 午夜精品在线福利| 波野结衣二区三区在线| 俄罗斯特黄特色一大片| 欧美一级a爱片免费观看看| 欧美日本亚洲视频在线播放| 午夜免费激情av| 国产激情偷乱视频一区二区| 一区福利在线观看| 一本一本综合久久| 亚洲色图av天堂| 中文字幕熟女人妻在线| 午夜福利成人在线免费观看| 免费观看在线日韩| 免费看美女性在线毛片视频| 人妻丰满熟妇av一区二区三区| 老熟妇仑乱视频hdxx| 嫩草影院入口| 18+在线观看网站| 精品国产三级普通话版| 亚洲成人久久爱视频| 国产伦在线观看视频一区| 亚州av有码| xxxwww97欧美| 亚洲av二区三区四区| 琪琪午夜伦伦电影理论片6080| xxxwww97欧美| 婷婷精品国产亚洲av| 国产精品爽爽va在线观看网站| 99久国产av精品| av在线蜜桃| 丝袜美腿在线中文| 亚洲在线观看片| 男人舔女人下体高潮全视频| 国产精品久久久久久av不卡| 成人综合一区亚洲| 国内揄拍国产精品人妻在线| 国产精品美女特级片免费视频播放器| 黄色日韩在线| 男女边吃奶边做爰视频| 直男gayav资源| av中文乱码字幕在线| 男女之事视频高清在线观看| 国产探花在线观看一区二区| 搡女人真爽免费视频火全软件 | 日日撸夜夜添| 国产中年淑女户外野战色| 成人特级黄色片久久久久久久| 国产一区二区三区在线臀色熟女| 久久人妻av系列| 亚洲精品一区av在线观看| 日本一二三区视频观看| 成人永久免费在线观看视频| 欧美精品国产亚洲| 亚洲精品乱码久久久v下载方式| 国内精品美女久久久久久| 欧美在线一区亚洲| 小蜜桃在线观看免费完整版高清| 搡女人真爽免费视频火全软件 | 欧美一区二区亚洲| 又爽又黄a免费视频| 一级a爱片免费观看的视频| 99在线视频只有这里精品首页| 三级男女做爰猛烈吃奶摸视频| 国产精品自产拍在线观看55亚洲| 国产在视频线在精品| 91av网一区二区| 夜夜夜夜夜久久久久| 九九在线视频观看精品| 深爱激情五月婷婷| 成人一区二区视频在线观看| 99久久精品热视频| 又爽又黄无遮挡网站| 成人毛片a级毛片在线播放| 免费大片18禁| 欧美一级a爱片免费观看看| 日韩精品有码人妻一区| 久久精品国产亚洲网站| 亚洲国产高清在线一区二区三| 制服丝袜大香蕉在线| 亚洲av日韩精品久久久久久密| 麻豆国产av国片精品| 内射极品少妇av片p| 淫秽高清视频在线观看| 国产精品电影一区二区三区| 国产91精品成人一区二区三区| 两人在一起打扑克的视频| 国内精品美女久久久久久| 国模一区二区三区四区视频| 中文字幕久久专区| 国产主播在线观看一区二区| 男人和女人高潮做爰伦理| 欧美最新免费一区二区三区| 18禁在线播放成人免费| 九色国产91popny在线| 最好的美女福利视频网| 男人的好看免费观看在线视频| 欧美潮喷喷水| 香蕉av资源在线| 亚洲成a人片在线一区二区| 亚洲第一区二区三区不卡| 亚洲欧美日韩卡通动漫| 国产色婷婷99| 99热网站在线观看| 久久精品国产亚洲av天美| 少妇丰满av| 久久久久性生活片| 我的老师免费观看完整版| 春色校园在线视频观看| 伊人久久精品亚洲午夜| 日韩强制内射视频| 成人欧美大片| 免费高清视频大片| 亚洲在线自拍视频| 一区福利在线观看| 一级av片app| 成人国产一区最新在线观看| 午夜福利视频1000在线观看| 日韩,欧美,国产一区二区三区 | 淫秽高清视频在线观看| 久久久精品大字幕| 国产免费av片在线观看野外av| 啦啦啦啦在线视频资源| 国产高清视频在线播放一区| 亚洲va在线va天堂va国产| 老熟妇乱子伦视频在线观看| 国产精品爽爽va在线观看网站| 免费在线观看日本一区| 日韩欧美一区二区三区在线观看| 成人二区视频| 日韩精品青青久久久久久| 午夜精品久久久久久毛片777| 亚洲中文字幕日韩| 亚洲精品影视一区二区三区av| 人妻制服诱惑在线中文字幕| 国产精品精品国产色婷婷| 成人欧美大片| 久久中文看片网| 一进一出抽搐动态| 又黄又爽又免费观看的视频| 久久精品国产清高在天天线| 欧美另类亚洲清纯唯美| 嫩草影视91久久| 精品一区二区三区视频在线| 99视频精品全部免费 在线| 69人妻影院| 国产精品不卡视频一区二区| 国产亚洲91精品色在线| 日本在线视频免费播放| 久久亚洲精品不卡| 欧美另类亚洲清纯唯美| 久久国产乱子免费精品| 日本撒尿小便嘘嘘汇集6| 成人国产一区最新在线观看| 国产精品嫩草影院av在线观看 | 国产精品,欧美在线| 精品人妻一区二区三区麻豆 | 色哟哟哟哟哟哟| 欧美xxxx黑人xx丫x性爽| 一个人看视频在线观看www免费| a级毛片免费高清观看在线播放| 国产av麻豆久久久久久久| 美女黄网站色视频| 国产大屁股一区二区在线视频| 亚洲欧美日韩无卡精品| 中文字幕精品亚洲无线码一区| 搞女人的毛片| 乱人视频在线观看| 精品国内亚洲2022精品成人| 国产精品人妻久久久影院| 男女那种视频在线观看| 91麻豆精品激情在线观看国产| 国产av一区在线观看免费| 亚洲av.av天堂| 尤物成人国产欧美一区二区三区| 最新中文字幕久久久久| 日本在线视频免费播放| 久久精品久久久久久噜噜老黄 | 中文字幕免费在线视频6| 搡老岳熟女国产| 国产亚洲欧美98| av在线观看视频网站免费| 麻豆成人午夜福利视频| 色哟哟哟哟哟哟| 国产亚洲精品久久久com| 国产精品亚洲一级av第二区| 日本 欧美在线| 网址你懂的国产日韩在线| 97热精品久久久久久| 少妇高潮的动态图| 校园人妻丝袜中文字幕| 欧美日本视频| 欧美成人性av电影在线观看| 老熟妇乱子伦视频在线观看| 亚洲精华国产精华精| 久久香蕉精品热| 国产精品嫩草影院av在线观看 | 国产一区二区激情短视频| 国产在线男女| 国产精品爽爽va在线观看网站| 亚洲午夜理论影院| 日韩欧美免费精品| 少妇高潮的动态图| 嫩草影院入口| 亚洲成人免费电影在线观看| av女优亚洲男人天堂| 日韩欧美 国产精品| 国产精品一区www在线观看 | 国产欧美日韩一区二区精品| 熟女电影av网| 日韩亚洲欧美综合| 日韩人妻高清精品专区| 99热6这里只有精品| 人妻夜夜爽99麻豆av| aaaaa片日本免费| 亚洲成人中文字幕在线播放| 亚洲avbb在线观看| 他把我摸到了高潮在线观看| 午夜精品一区二区三区免费看| 亚洲国产欧洲综合997久久,| 中文字幕av在线有码专区| 最后的刺客免费高清国语| 国产真实伦视频高清在线观看 | 日本免费a在线| 12—13女人毛片做爰片一| 日本三级黄在线观看| 听说在线观看完整版免费高清| 国产极品精品免费视频能看的| 亚洲一区高清亚洲精品| 亚洲内射少妇av| 三级男女做爰猛烈吃奶摸视频| 啦啦啦啦在线视频资源| 99在线人妻在线中文字幕| .国产精品久久| 日本黄色片子视频| 哪里可以看免费的av片| 亚洲专区国产一区二区| 性欧美人与动物交配| 有码 亚洲区| 在线观看免费视频日本深夜| 亚洲精品456在线播放app | 国内精品一区二区在线观看| 狂野欧美白嫩少妇大欣赏| 精品乱码久久久久久99久播| 欧美激情久久久久久爽电影| 很黄的视频免费| 亚洲熟妇中文字幕五十中出| 婷婷亚洲欧美| 亚洲成a人片在线一区二区| 长腿黑丝高跟| 在线a可以看的网站| 国产中年淑女户外野战色| 亚洲自偷自拍三级|