考慮工序并行的差異工件批調度研究

唐紅濤，楊志鵬，劉家毅

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

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

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

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

1 問題描述及數學模型構建

1.1 問題描述

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

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

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

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

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

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

1.2 數學模型構建

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

假設如下。

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

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

3) 同類型沙箱個數沒有限制；

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

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

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

變量描述如下。

n為待加工工件總個數；J為待加工工件集合J={Ji,1≤i≤n}；Si為工件Ji的尺寸；Wi為工件Ji的重量；l為工件材質種類；ai為工件Ji材質；b為批次的數量；Bmk為造型批次Bk，Bm={Bmk,1≤k≤b}；Bck為制芯批次Bk，Bc={Bck,1≤k≤b}；S Bk為批次Bk的總尺寸；WBk為批次Bk的總重量；Tmij為批處理機Mi選擇沙箱Gj的造型加工時間；Tcij為批處理機Mi選擇沙箱Gj的制芯加工時間；q為沙箱類型數量；G為沙箱類型集合，G={Gj,1≤Gj≤q}；SG j為第Gj種沙箱的尺寸；m為批處理機的數量；M為批處理機集合，M={Mi,1≤Mi≤m}；Q為熔煉爐單次最大熔煉重量；L為一個足夠大的正數；Cmax為最大完工時間；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變量，批處理機Mi造型批次Bk為1，否則為0；

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

本文的數學模型構建如下。

1) 最大完工時間。最大完工時間是指在滿足前文約束和假設的條件下，每臺批處理機造型和制芯工序結束后所耗費的最大時間。

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

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

2 基于IHS-SA算法設計

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

2.1 編碼與解碼

本文和聲算法的每條和聲H=[Hj|Hs]基于工件和沙箱產生。其中，Hj中的值表示待加工工件編號，Hs中的值表示對應工件選擇的沙箱類型。由于每個工件有2道工序，且可同時加工，故采用單工序編碼方式，即單個工序編碼代表2道工序。

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

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

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

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

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

表1 工件信息Table 1 Workpiece information

2.2 機器分配規(guī)則

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

表3 批處理機加工時間信息Table 3 Batch processing time

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

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

2.3 交換算子和插入算子

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

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

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

2.4 算法流程

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

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

2.4.1 全局搜索階段

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

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

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

2.4.2 局部搜索階段

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

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

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

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

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

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

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

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

3 案例仿真與應用

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

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

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

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

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

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

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

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

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

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

表8 ECTF規(guī)則下4種算法評價指標對比Table 8 The comparison of algorithm evaluation indexes under ECTF rules

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

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

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

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

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

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

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

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

4 總結

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

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