唐紅濤，楊志鵬，劉家毅

(武漢理工大學(xué) 機(jī)電工程學(xué)院，湖北 武漢 430070)

批調(diào)度[1](batch scheduling)作為車間調(diào)度的一個(gè)重要分支，是智能制造領(lǐng)域研究的熱點(diǎn)和難點(diǎn)問題之一。不同于傳統(tǒng)調(diào)度問題中機(jī)器每次只能加工一個(gè)工件，批處理機(jī)在不超過其容量限制的前提下可以同時(shí)加工多個(gè)工件。而帶有工序并行性的批調(diào)度問題，約束更加復(fù)雜，求解難度更大，在工程上該問題主要存在于半導(dǎo)體企業(yè)和鑄造企業(yè)，對(duì)該問題的研究能夠更好地指導(dǎo)企業(yè)生產(chǎn)，提高生產(chǎn)效率。

針對(duì)批調(diào)度和并行工序[2]的研究出現(xiàn)了眾多研究成果。Ikura等[3]研究了工件大小相同，到達(dá)時(shí)間和截止日期一致的單機(jī)批調(diào)度問題，并提出了一種多項(xiàng)式算法來優(yōu)化最大完工時(shí)間。在鑄造車間調(diào)度問題上，Stawowy等[4]研究了造型車間和制芯車間協(xié)同生產(chǎn)與調(diào)度的問題,并提出了一種拉格朗日啟發(fā)式算法來求解不同車間協(xié)調(diào)生產(chǎn)的問題，但其忽略了造型工序與制芯可并行的情形；胡常偉等[5]研究了鑄造車間工件同材質(zhì)情況下如何進(jìn)行分批與調(diào)度的問題。在工序可并行加工的問題上，劉曉平等[6]通過給并行工序設(shè)定優(yōu)先級(jí)來優(yōu)化最大完工時(shí)間。在差異工件批次劃分問題上，黃錦鈿等[7]采用啟發(fā)式規(guī)則對(duì)差異工件進(jìn)行分批以優(yōu)化總加權(quán)拖期；徐本柱等[8]采用試探法解決了批調(diào)度過程中工件分批無規(guī)則的問題；王萬良等[9]提出了一種基于產(chǎn)品需求量的批次劃分方案來解決工件盲目分批的問題，并采用差分進(jìn)化算法優(yōu)化總生產(chǎn)成本。這些學(xué)者的研究豐富了車間調(diào)度理論，其研究成果對(duì)鑄造車間實(shí)際生產(chǎn)有一定的指導(dǎo)意義。

國(guó)內(nèi)外對(duì)鑄造車間批調(diào)度問題已經(jīng)有了較豐富的研究成果，但由于實(shí)際鑄造車間生產(chǎn)比較復(fù)雜[10]，一般都會(huì)進(jìn)行近似化處理。如文獻(xiàn)[4]忽視了工序之間的并行性，且工件組批過程中不存在約束，皆不能較好地應(yīng)用于國(guó)內(nèi)實(shí)際鑄造生產(chǎn)車間。國(guó)內(nèi)鑄造行業(yè)以單件小批量生產(chǎn)模式為主導(dǎo)，具有產(chǎn)品種類與材質(zhì)多樣、生產(chǎn)周期長(zhǎng)、工藝約束多、排產(chǎn)紊亂等特點(diǎn)，本文以鑄造行業(yè)為背景，結(jié)合鑄造車間實(shí)際生產(chǎn)過程中存在不相容工件族約束、沙箱尺寸約束、熔煉重量約束，構(gòu)建一種混合整數(shù)規(guī)劃模型，并設(shè)計(jì)一種帶有單工序編碼與批首次匹配規(guī)則解碼的改進(jìn)和聲算法對(duì)模型求解。最后根據(jù)企業(yè)實(shí)際生產(chǎn)數(shù)據(jù)進(jìn)行案例仿真，驗(yàn)證本文研究的有效性。

1 問題描述及數(shù)學(xué)模型構(gòu)建

1.1 問題描述

鑄造車間按先組批后分配過程進(jìn)行生產(chǎn)。生產(chǎn)階段由班組完成，班組類似于批調(diào)度中的批處理機(jī)，因此本文將班組虛擬化為批處理機(jī)，將班組加工時(shí)間虛擬化為批處理機(jī)加工時(shí)間進(jìn)行研究。如圖1所示，按工藝流程主要分為工件組批、沙箱選擇、任務(wù)分配3個(gè)階段。不同階段存在不同約束，主要有以下3種。

圖1 鑄造車間前工段產(chǎn)品工藝流程圖Figure 1 The flowchart of products in previous-stage casting workshop

1) 材質(zhì)約束。在工件組批階段，同一批工件在同一熔煉爐進(jìn)行熔煉，因此工件的材質(zhì)必須相同。

2) 尺寸約束。在沙箱選擇階段，同一批工件的尺寸和不能超出所選沙箱的最大尺寸。

3) 重量約束。在工件組批階段，同一批工件的重量和不能超出熔煉爐單次最大熔煉重量。

傳統(tǒng)批調(diào)度問題可以描述為：n個(gè)工件被分為k個(gè)不同的批次，在m臺(tái)批處理機(jī)(加工資源)上進(jìn)行加工，每臺(tái)批處理機(jī)同一時(shí)間段只能加工一個(gè)批次的一道工序，需要確定不同工件加工順序，并為每個(gè)工件選擇加工機(jī)器。鑄造車間調(diào)度問題和傳統(tǒng)批調(diào)度問題比較類似，但在鑄造車間每個(gè)批次的造型工序和制芯工序可以同時(shí)由不同機(jī)器加工，有沙箱和批處理機(jī)2種加工資源可供選擇。因此，鑄造車間調(diào)度問題可以被描述為具有工序并行性的批調(diào)度問題。在該調(diào)度問題中，需要解決以下4個(gè)子問題：工件分批；批次選擇沙箱；確定各工件的加工順序；確定各工序的加工機(jī)器。

1.2 數(shù)學(xué)模型構(gòu)建

針對(duì)工序并行性的批調(diào)度問題，以優(yōu)化最大完工時(shí)間和沙箱空置率為目標(biāo)，建立調(diào)度模型。為方便描述，引入以下假設(shè)條件和變量符號(hào)進(jìn)行說明。

假設(shè)如下。

1) 單個(gè)工件的尺寸未超出所有沙箱中的最大尺寸；

2) 單個(gè)工件的重量未超出熔煉爐單次最大熔煉重量；

3) 同類型沙箱個(gè)數(shù)沒有限制；

4) 同一個(gè)工件只能被分配到一個(gè)工件族且只能被分配一次；

5) 同一個(gè)工件族造型或制芯只能被一個(gè)批處理機(jī)加工，且只能被加工一次；

6) 批次加工過程中不允許被中斷，同時(shí)也不允許向該批次增加或減少工件。

變量描述如下。

n為待加工工件總個(gè)數(shù)；J為待加工工件集合J={Ji,1≤i≤n}；Si為工件Ji的尺寸；Wi為工件Ji的重量；l為工件材質(zhì)種類；ai為工件Ji材質(zhì)；b為批次的數(shù)量；Bmk為造型批次Bk，Bm={Bmk,1≤k≤b}；Bck為制芯批次Bk，Bc={Bck,1≤k≤b}；S Bk為批次Bk的總尺寸；WBk為批次Bk的總重量；Tmij為批處理機(jī)Mi選擇沙箱Gj的造型加工時(shí)間；Tcij為批處理機(jī)Mi選擇沙箱Gj的制芯加工時(shí)間；q為沙箱類型數(shù)量；G為沙箱類型集合，G={Gj,1≤Gj≤q}；SG j為第Gj種沙箱的尺寸；m為批處理機(jī)的數(shù)量；M為批處理機(jī)集合，M={Mi,1≤Mi≤m}；Q為熔煉爐單次最大熔煉重量；L為一個(gè)足夠大的正數(shù)；Cmax為最大完工時(shí)間；Vmax為沙箱空置率。

本文決策變量如下。

Xik為0-1變量，工件Ji分配到批次Bk為1，否則為0；

Yk j為0-1變量，批次Bk選擇沙箱Gj為1，否則為0；

Ymk j為0-1變量，造型批次Bk選擇沙箱Gj為1，否則為0；

Yck j為0-1變量，制芯批次Bk選擇沙箱Gj為1，否則為0；

Zmik為0-1變量，批處理機(jī)Mi造型批次Bk為1，否則為0；

Zcik為0-1變量，批處理機(jī)Mi制芯批次Bk為1，否則為0。

本文的數(shù)學(xué)模型構(gòu)建如下。

1) 最大完工時(shí)間。最大完工時(shí)間是指在滿足前文約束和假設(shè)的條件下，每臺(tái)批處理機(jī)造型和制芯工序結(jié)束后所耗費(fèi)的最大時(shí)間。

2) 沙箱空置率。沙箱空置率是指沙箱空置尺寸占沙箱總尺寸的平均值。沙箱空置率越低表明沙箱的有效利用率越高。

式(3)表示一個(gè)工件只能被分配到一個(gè)批次；式(4)表示一個(gè)批次只能選擇一種沙箱，并且造型工序和制芯工序選擇同一個(gè)沙箱；式(5)表示一臺(tái)批處理機(jī)同時(shí)只能造型或者制芯一個(gè)沙箱；式(6)表示一個(gè)批次的總尺寸等于該批次所有工件尺寸之和；式(7)表示一個(gè)批次的總重量等于該批次所有工件重量之和；式(8)表示一個(gè)批次的尺寸之和不能超出所選沙箱的尺寸；式(9)表示一個(gè)批次重量之和不能超出熔煉爐單次最大熔煉重量；式(10)表示只有同種材質(zhì)工件才可以被分配到一個(gè)沙箱。

2 基于IHS-SA算法設(shè)計(jì)

和聲搜索算法(harmony search,HS)是由Geem等[11]提出的一種新型的元啟發(fā)式算法。近幾年諸多學(xué)者[12-13]也對(duì)其進(jìn)行改進(jìn)，并將其應(yīng)用在車間調(diào)度問題上。和聲算法本身適用于解決連續(xù)性問題，而批調(diào)度為離散性問題，因此本文提出一種改進(jìn)和聲算法并將其應(yīng)用于批調(diào)度問題。改進(jìn)算法由2個(gè)階段組成，全局搜索階段和局部搜索階段。全局搜索階段由和聲算法完成，局部搜索階段由模擬退火(simulated annealing，SA)算法完成。兩階段保證算法有較強(qiáng)全局搜索能力的同時(shí)，能大概率跳出局部次優(yōu)解，最終找到算法的近似全局最優(yōu)解。

2.1 編碼與解碼

本文和聲算法的每條和聲H=[Hj|Hs]基于工件和沙箱產(chǎn)生。其中，Hj中的值表示待加工工件編號(hào)，Hs中的值表示對(duì)應(yīng)工件選擇的沙箱類型。由于每個(gè)工件有2道工序，且可同時(shí)加工，故采用單工序編碼方式，即單個(gè)工序編碼代表2道工序。

表2 砂箱類型信息Table 2 Sandbox information

和聲解碼是將每條和聲還原為有意義的解，本文采用批首次匹配[14-15](batch first fit,BFF)規(guī)則對(duì)每條和聲進(jìn)行解碼。首先，從Hj中選擇第1個(gè)位置的工件建立第1批次；然后，從Hs中選擇對(duì)應(yīng)于該位置的沙箱為第1批次的沙箱，取Hj中第2個(gè)位置的工件，將該工件在不違背沙箱尺寸約束、熔煉重量約束和工件材質(zhì)約束的情況下放入前一批次，若違反上述某個(gè)約束條件則建立新批次，同時(shí)該批次的沙箱類型為Hj中對(duì)應(yīng)位置的沙箱，直到為所有工件分配好批次和沙箱。各批次的順序即為工件的加工順序。采用此方法Hs中某些位置的編碼會(huì)失去作用，但不影響批次的劃分。

表1～3給出了5個(gè)工件、2種沙箱和2臺(tái)批處理機(jī)的信息。假設(shè)一臺(tái)熔煉爐單次最大熔煉重量為3，對(duì)一條和聲H=[Hj|Hs]=[2 4 1 3 5|2 1 2 1 1]進(jìn)行解碼。如圖2所示，首先選擇第1個(gè)工件2建立第1個(gè)批次，該批次選擇的沙箱類型為2；將工件4加入第1批會(huì)違反尺寸約束和材質(zhì)約束，則以工件4建立第2個(gè)批次；將工件1加入第2批會(huì)違反材質(zhì)約束，故以工件1建立第3批；將工件3加入第3批不違反任何約束，說明工件1和工件3可以組成第3批，該批次選擇工件1對(duì)應(yīng)位置的沙箱2；工件5加入第3批違反材質(zhì)約束，則以工件5建立第4批。表4給出了5個(gè)工件的分批情況，此時(shí)工件3位置對(duì)應(yīng)的沙箱編碼未發(fā)揮作用，通過編解碼解決了工件批次劃分和沙箱選擇的問題。

表4 工件組批信息Table 4 Workpiece batch information

圖2 示例解碼圖Figure 2 The diagram of case decoding

表1 工件信息Table 1 Workpiece information

2.2 機(jī)器分配規(guī)則

本文提出2種機(jī)器分配規(guī)則來解決工序分配和機(jī)器選擇問題：完工時(shí)間最短優(yōu)先規(guī)則(the earliestcompletion time first,ECTF)和機(jī)器最早可用優(yōu)先規(guī)則(the earliest available machine first,EAMF)。每個(gè)批次的工件有造型和制芯2道工序，但在實(shí)際生產(chǎn)中一般優(yōu)先加工造型工序，因此本文在工序分配時(shí)優(yōu)先分配造型工序。

表3 批處理機(jī)加工時(shí)間信息Table 3 Batch processing time

式(11)中，TECTF為在ECTF分配規(guī)則下每個(gè)批次造型和制芯工序總完工時(shí)間；Tmxj和Tcyj分別為每個(gè)批次造型與制芯時(shí)間，根據(jù)該規(guī)則選擇滿足造型和制芯完工時(shí)間最短的機(jī)器，如果有多種機(jī)器組合都滿足完工時(shí)間最短的要求，則隨機(jī)選擇其中一個(gè)機(jī)器組合。

式(12)中，TEAMF為在EAMF分配規(guī)則下每個(gè)批次造型和制芯工序總完工時(shí)間；Tmxj和Tcyj為每個(gè)批次造型與制芯時(shí)間，在該規(guī)則下首先確定造型工序在所有批處理機(jī)中完工最早的機(jī)器，其次再確定所有批處理機(jī)中制芯工序完工最早的機(jī)器，若有多個(gè)機(jī)器完工時(shí)間一致，隨機(jī)選擇其中一個(gè)，將2道工序的加工順序和加工機(jī)器作為最終分配方案。

2.3 交換算子和插入算子

插入(insert)算子[16]，如圖3所示。在[1,n]之間生成2個(gè)隨機(jī)數(shù)，如{2,4}，將位置4的工件插入到位置2，中間各位置工件保持原有次序依次后移，沙箱編碼部分采取同樣策略。交換(swap)算子如圖4所示。隨機(jī)生成2個(gè)位置，在父代中找到2個(gè)位置對(duì)應(yīng)的工件，將2個(gè)位置的工件互換，將互換后的工件集作為子代，沙箱編碼部分采取同樣策略。

圖3 Insert算子示意圖Figure 3 The insert operator

圖4 Swap算子示意圖Figure 4 The swap operator

2.4 算法流程

為便于下文描述，介紹Pareto支配[17]概念：對(duì)于多目標(biāo)優(yōu)化問題，若 ?i，有fi(α)≤fi(β)，且 ?j，使fj(α)≤fj(β)，則稱α支配β(α比β更優(yōu))，記做α＜β。Pareto支配數(shù)量即種群中受某個(gè)解支配的數(shù)量，不被種群中任何解所支配的解，其Pareto等級(jí)為1，所有Pareto等級(jí)為1的解組成Pareto非支配解集，所有非支配解集組成Pareto前沿。

本文定義一種初始化策略提高和聲記憶庫(kù)質(zhì)量。將工件按照材質(zhì)分類，并將每種材質(zhì)的工件按重量升序排列，對(duì)應(yīng)的沙箱采用隨機(jī)方式產(chǎn)生，在初始化階段為保證和聲記憶庫(kù)的多樣性，按照該策略生成的和聲個(gè)體占20%，其余的和聲采用隨機(jī)方式生成。由于隨機(jī)選擇的沙箱可能不滿足尺寸約束，因此，初始化完成后需要對(duì)不滿足尺寸約束的沙箱進(jìn)行糾正，重新選擇能滿足尺寸約束的最小沙箱類型。

2.4.1 全局搜索階段

和聲搜索算法具有全局搜索能力較強(qiáng)的優(yōu)點(diǎn)，原始和聲算法主要根據(jù)和聲記憶庫(kù)取值概率HMCR和音調(diào)微調(diào)概率PAR產(chǎn)生新解，如式(13)所示。在解決離散問題上，HS算法一般采用最大位置法實(shí)現(xiàn)從連續(xù)空間到離散空間的映射，但在映射過程中容易失去原始解中包含的有效信息，并且原始和聲算法每次迭代只產(chǎn)生一條和聲，不能較好地執(zhí)行全局搜索過程。

本文提出的改進(jìn)和聲算法每次迭代都產(chǎn)生與原始和聲記憶庫(kù)數(shù)量相等的新和聲。在迭代過程中算法新解的產(chǎn)生基于當(dāng)前最優(yōu)調(diào)度方案Nbest(Pareto等級(jí)為1，若有多個(gè)隨機(jī)選擇其中一個(gè))和未調(diào)度工件序列Narray產(chǎn)生，如式(14)所示。生成[0,1]上隨機(jī)數(shù)R1。若R1＜HMCR，從和聲記憶庫(kù)中隨機(jī)選擇一條和聲，并從第z(z為和聲的位置編號(hào))列中選擇工件編碼和對(duì)應(yīng)的沙箱編碼放入新解中，若新解中包含此工件，則從最優(yōu)解Nbest中選擇第一個(gè)位置的工件和對(duì)應(yīng)沙箱放入新解中；若R1≥ HMCR，則選擇未調(diào)度工件序列Narray中第y(隨機(jī)整數(shù))列工件放入新解中，此時(shí)沙箱部分采用隨機(jī)方式產(chǎn)生，直到新解產(chǎn)生完畢。每次放入新解中的工件都要從最優(yōu)解Nbest和未調(diào)度工件序列Narray中劃去，避免非法解的產(chǎn)生。

本文對(duì)新解的擾動(dòng)采用自適應(yīng)音調(diào)微調(diào)概率PAR，如式(15)所示。式中，It為當(dāng)前迭代次數(shù)，max It為總迭代次數(shù)。當(dāng)新解產(chǎn)生后采用上述2種算子對(duì)新解進(jìn)行擾動(dòng)，如式(16)所示。前期解的質(zhì)量較差，因此，用i nsert算子進(jìn)行較大范圍擾動(dòng)，后期解的質(zhì)量比較穩(wěn)定，故用swap算子進(jìn)行小范圍擾動(dòng)，式中N表示某個(gè)待擾動(dòng)的解，Nnew表示擾動(dòng)后產(chǎn)生的新解。

2.4.2 局部搜索階段

模擬退火算法是一種貪心算法，在迭代過程中引入了隨機(jī)接受概率，能以一定的概率接受比當(dāng)前解更差的解，增強(qiáng)了算法跳出局部最優(yōu)的能力。本文采用基于Pareto支配數(shù)量的機(jī)制接受新解，即比較鄰域擾動(dòng)前的解θ和鄰域擾動(dòng)后的解θ*支配其他解的數(shù)量差Δf=DominateNum(θ)-DominateNum (θ*)(其中，DominateNum(θ)表示解θ支配當(dāng)前種群中其余解的總數(shù)量)，并以Metropolis準(zhǔn)則接受新解(即Rand＜exp(-Δf/t)時(shí)接受新解，否則不接受，其中，t為當(dāng)前溫度)，當(dāng)算法達(dá)到指定溫度或新解達(dá)到指定未改善次數(shù)時(shí)，結(jié)束內(nèi)循環(huán)。本文基于2種鄰域結(jié)構(gòu)產(chǎn)生新解。

1) 沙箱變異(mutation)。對(duì)于每條和聲H=[Hj|Hs]，檢查Hj中第k維和第k+1維的工件材質(zhì)是否相同。若材質(zhì)相同，檢查Hs中沙箱類型是否相同；若不同，則令k+1維的沙箱與第k維相同。

2) 批次合并(combine)。對(duì)工件進(jìn)行預(yù)分批，檢查是否存在2個(gè)批次的沙箱和材質(zhì)都相同。若存在相同的2個(gè)批次，則將2個(gè)批次的工件放到相近的位置，如圖5所示；若B2和B52個(gè)批次的沙箱和材質(zhì)都相同，則將B2和B52個(gè)批次的工件放到相近位置。

圖5 批次合并示意圖Figure 5 The diagram of batch consolidation

算法整體流程如圖6所示。

圖6 IHS-SA算法流程圖Figure 6 The flowchart of IHS-SA algorithm

以表4中5工件4批次的劃分方案為例，在2種機(jī)器分配規(guī)則下，得到調(diào)度甘特圖，如圖7所示。圖中字母下標(biāo)索引表示同一批次的造型和制芯工序，后綴表示批次信息。如Bm-1表示第1批次造型工序，Bc-2表示第2批次制芯工序。從實(shí)例可以看出，工件加工順序相同的情況下采用ECTF規(guī)則總完工時(shí)間較短。

圖7 2種不同規(guī)則下調(diào)度甘特圖Figure 7 The Gantt chart of scheduling under two different rules

3 案例仿真與應(yīng)用

本文以浙江某企業(yè)鑄造車間實(shí)際生產(chǎn)狀況為研究對(duì)象，針對(duì)該車間工件材質(zhì)種類多，計(jì)劃制定效率低等情形，選擇該車間某周期任務(wù)來驗(yàn)證本文模型的有效性。該車間某周期任務(wù)為生產(chǎn)40個(gè)工件，工件材質(zhì)有3種，工件信息如表5所示。該鑄造車間目前有3種類型沙箱，第1種沙箱尺寸為1 m3，第2種類型沙箱尺寸為3 m3，第3種類型沙箱尺寸為5 m3，每種類型沙箱個(gè)數(shù)足夠多；3臺(tái)可用批處理機(jī)(M1，M2，M3)，每臺(tái)都可加工造型和制芯工序，熔煉爐單次最大熔煉重量為20 000 kg，需要確定工件的加工順序和工序的加工機(jī)器以保證完工時(shí)間最短和沙箱空置率最小。機(jī)器加工時(shí)間如表6所示。

表5 待加工工件信息Table 5 The information of workpiece to be processed

表6 批處理機(jī)加工時(shí)間(造型/制芯)Table 6 The processing time of batch processor (molding/coring) h

算法的運(yùn)行環(huán)境為2.7 GHz CPU，8 G內(nèi)存，64位win 7系統(tǒng)計(jì)算機(jī)，編程環(huán)境為Matlab 2016。為驗(yàn)證本文IHS-SA算法的有效性，選擇與文獻(xiàn)[18]中NSGA-II算法及改進(jìn)前后的和聲算法進(jìn)行對(duì)比。經(jīng)多次試驗(yàn)確定IHS-SA算法的和聲記憶庫(kù) (種群) HMS=80，HMCR=0.9，PARmax=0.7，PARmin=0.2，模擬退火設(shè)定初始溫度tb=3，終止溫度te=1，溫度衰減系數(shù)K=0.9，最大未改善次數(shù)maxFail=5；改進(jìn)IHS算法去除局部搜索階段，其余參數(shù)保持和上面一致，原始和聲算法HS保持和IHS算法參數(shù)一致，但根據(jù)式(11)采用連續(xù)到離散空間映射方式編解碼；NSGA-II算法初始種群數(shù)量PopSize=80，交叉概率Pcross=0.6，變異概率Pmutation=0.1。算法迭代次數(shù)max It=100。在2種機(jī)器分配規(guī)則下,每種算法獨(dú)立運(yùn)行30次，得出最大完工時(shí)間和沙箱空置率的最優(yōu)值、平均值及最優(yōu)值出現(xiàn)次數(shù)。由于算法受2種規(guī)則影響不大，故采用ECTF規(guī)則評(píng)測(cè)算法性能，如表7所示。在ECTF規(guī)則下本文所提算法的最優(yōu)解及最優(yōu)解的數(shù)量均優(yōu)于其他3種算法。

表7 ECTF規(guī)則下實(shí)例仿真結(jié)果Table 7 The simulation results of example under ECTF rules

本文采用收斂性指標(biāo)γ、多樣性指標(biāo)Δ和支配性指標(biāo)Ω[18]評(píng)測(cè)所提算法性能。由于模型的真實(shí)最優(yōu)Pareto前沿(net optimal Pareto front,NOPF)未知，因此采用4種算法的非支配解集進(jìn)行非支配比較后的解作為NOPF。各指標(biāo)計(jì)算公式如下。

式(17)中，ds為非支配解集中第s個(gè)解與NOPF的歐氏距離；ψ為非支配解集個(gè)數(shù)。γ越小表明算法的收斂性越好。

式(18)中，dσ和dδ分別為算法非支配解集中極端解與邊界點(diǎn)之間的歐氏距離；de為第e個(gè)解和第e+1個(gè)解之間的歐氏距離；d為所有距離的平均值；φ為個(gè)體數(shù)目。Δ越小表明算法多樣性越好。

式(19)中，|C(ξ)|表示集合ξ中的非支配解數(shù)量的交集；Pe為第e種算法的非支配解集。Ω越大表明算法的支配性能越好。

如表8所示，通過計(jì)算4種算法的評(píng)價(jià)指標(biāo)可以得出，本文改進(jìn)算法的收斂性、多樣性和支配性都比其余3種算法好。IHS算法的收斂性、多樣性和支配性都比HS算法更好。HS結(jié)果較差的原因有2點(diǎn)。1) 連續(xù)空間到離散空間映射時(shí)失去部分有效信息；2) 原始和聲算法迭代過程中產(chǎn)生的新解個(gè)數(shù)過少。

表8 ECTF規(guī)則下4種算法評(píng)價(jià)指標(biāo)對(duì)比Table 8 The comparison of algorithm evaluation indexes under ECTF rules

根據(jù)實(shí)驗(yàn)數(shù)據(jù)繪制Pareto前沿圖，如圖8所示。通過對(duì)比4種算法的Pareto前沿，IHS-SA算法結(jié)果較IHS算法更好，原因在于本文加入局部搜索策略后，算法能夠跳出局部最優(yōu)而趨于全局最優(yōu)解。NSGA-II算法結(jié)果和IHS算法相近，說明2種算法均陷入了局部次優(yōu)解。

圖8 ECTF規(guī)則下算法Pareto前沿圖Figure 8 The Pareto front graph of algorithm under ECTF rules

根據(jù)IHS-SA算法，在ECTF 規(guī)則下40個(gè)工件被分為17個(gè)批次，各批次包含工件如表9所示。圖9所示為根據(jù)其中一個(gè)Pareto非支配解繪制的調(diào)度甘特圖，甘特圖中每一行表示在一臺(tái)機(jī)器上加工，每個(gè)矩形表示同一個(gè)加工批次，矩形長(zhǎng)度表示該批次加工時(shí)間，各批次的順序表示工件的加工順序，字母下標(biāo)表示同一批次的造型和制芯工序，后綴為批次信息。如Bm-1表示第1批次造型工序，Bc-2表示第2批次制芯工序，屬于該批次的工件10、4、9、2、11、3先加工，甘特圖中最大完工時(shí)間為66 h，沙箱空置率為 20.329 4%。

表9 ECTF規(guī)則下工件批次劃分表Table 9 The table of workpiece batch division under ECTF rules

圖9 ECTF規(guī)則下調(diào)度甘特圖Figure 9 The scheduling Gantt chart under ECTF rules

在不同的機(jī)器分配規(guī)則下會(huì)產(chǎn)生不同的調(diào)度甘特圖。在EAMF規(guī)則下，40個(gè)工件被分為17個(gè)批次，如表10所示。根據(jù)其中一個(gè)Pareto非支配解繪制調(diào)度甘特圖，如圖10所示。甘特圖中最大完工時(shí)間為77 h，沙箱空置率為15.537 3%。

圖10 EAMF規(guī)則下調(diào)度甘特圖Figure 10 The scheduling Gantt chart under EAMF rules

表10 EAMF規(guī)則下算法工件批次劃分表Table 10 The table of workpiece batch division under EAMF rules

4 總結(jié)

本文研究了鑄造車間工件多材質(zhì)、組批多約束、工序可并行的批調(diào)度問題，建立相應(yīng)的數(shù)學(xué)模型，通過改進(jìn)和聲算法結(jié)合模擬退火算法對(duì)模型進(jìn)行求解以優(yōu)化完工時(shí)間和沙箱空置率。針對(duì)和聲搜索算法提出一種單工序編碼方式和BFF解碼規(guī)則解決工件組批和沙箱選擇問題，并提出2種不同機(jī)器分配規(guī)則解決工序分配和機(jī)器選擇問題。最后將本文所建立模型進(jìn)行仿真實(shí)驗(yàn)，在不同的分配規(guī)則下產(chǎn)生不同的調(diào)度甘特圖，方便企業(yè)根據(jù)自身的生產(chǎn)狀況選擇合適調(diào)度方案。

本文僅考慮了鑄造車間前工段穩(wěn)定狀態(tài)下的調(diào)度情形，下一步可以對(duì)特殊情況下如何進(jìn)行重調(diào)度和批次劃分的問題進(jìn)行研究。