袁小芳，楊育輝，譚偉華，尹柏鑫

（1.湖南大學 電氣與信息工程學院，湖南 長沙 410082；2.湖南大學機器人視覺感知與控制技術(shù)國家工程實驗室，湖南 長沙 410082）

鑄造行業(yè)作為制造業(yè)的基礎(chǔ)行業(yè)，其發(fā)展水平是衡量一個國家整體工業(yè)水平的重要因素.中國鑄件制造總體以低端鑄件為主，鑄造企業(yè)多為小微企業(yè)，主要依靠個人經(jīng)驗確定生產(chǎn)計劃，導致鑄件生產(chǎn)效率較低[1].迫切需要更合理的生產(chǎn)調(diào)度策略以降低企業(yè)資源消耗、提高生產(chǎn)效率、增強企業(yè)競爭力.

按生產(chǎn)鑄件方法分類，鑄造可分為砂型鑄造和特種鑄造，典型的砂型鑄造生產(chǎn)線生產(chǎn)流程如圖1所示，計劃生產(chǎn)系統(tǒng)從訂單池獲得訂單之后給出生產(chǎn)計劃，整個鑄件生產(chǎn)過程分為兩個階段，第一階段基于砂箱和熔爐對鑄件進行批次加工，熔煉爐根據(jù)批次熔煉合金并注入造型機造好的模具當中，經(jīng)過冷卻，鑄件從模具中取出，生產(chǎn)加工過程進入第二階段進行柔性單件生產(chǎn)加工，鑄件單件根據(jù)生產(chǎn)工藝進行后續(xù)加工.所有鑄件以相同的工藝順序通過第一階段批次加工后進行各自第二階段的生產(chǎn)加工操作.

圖1 典型砂型鑄造生產(chǎn)線生產(chǎn)流程Fig.1 Production flow of typical sand mold casting production line

針對鑄造生產(chǎn)線生產(chǎn)過程當中的批次生產(chǎn)調(diào)度問題，唐江濤等[2]對鑄造當中的批量造型計劃進行了研究.胡常偉等[3]針對任務重量不一致的同型熔煉爐批調(diào)度問題進行了研究.Francisco 等[4]將中型鑄造企業(yè)中的資源調(diào)度建模為項目調(diào)度問題并提出了一個元啟發(fā)式算法進行求解.Gauri[5]對有不同材質(zhì)的鑄件進行了熔煉澆注的批次計劃研究.針對鑄造生產(chǎn)線全流程優(yōu)化調(diào)度問題的研究，Tang[6]與Li[7]等將鑄造生產(chǎn)線的加工流程視為混合流水車間調(diào)度問題進行了研究.QIN 等[8]針對實際生產(chǎn)當中的特殊約束條件，建立了忽略批調(diào)度過程的鑄造生產(chǎn)線優(yōu)化調(diào)度模型進行求解.陳榮[9]將鑄造生產(chǎn)過程建立為兩階段的生產(chǎn)調(diào)度模型，并提出了相應的求解方法.然而，目前針對鑄造生產(chǎn)線全流程優(yōu)化調(diào)度問題的研究大都沒有考慮批次加工與機加工協(xié)同調(diào)度的問題，忽略鑄造生產(chǎn)兩階段耦合關(guān)系求得的解往往不是問題的最優(yōu)解，因此，對鑄造生產(chǎn)線全流程優(yōu)化調(diào)度問題的研究具有重要意義.

Maes[10]與劉蓉[11]等的研究證明鑄造生產(chǎn)線優(yōu)化調(diào)度問題屬于NP-hard 問題，傳統(tǒng)求解方法如分支定界法等求解困難.混沌優(yōu)化算法是一種利用混沌運動的遍歷性來搜索最優(yōu)解的啟發(fā)式算法，具有優(yōu)秀的全局尋優(yōu)能力與跳出局部最優(yōu)的能力[12-13].針對混沌優(yōu)化算法對初始值敏感的問題，并行混沌優(yōu)化算法（parallel chaos optimization algorithm，PCOA）采取多個混沌變量映射的措施，一個優(yōu)化變量對應多個混沌變量，混沌變量獨立搜索，并行變量的最優(yōu)值為需要的優(yōu)化解，提高了算法的搜索效率[14].

本文考慮實際鑄件加工生產(chǎn)環(huán)境，建立了鑄造生產(chǎn)線全流程優(yōu)化調(diào)度模型，并設(shè)計了一種混合并行混沌優(yōu)化算法（Hybrid parallel chaos optimization algorithm，HPCOA）對模型進行求解.算法設(shè)計了獨特的編碼解碼機制和分批策略，并引入交叉變異操作，提高算法迭代過程中解集的多樣性與算法的開發(fā)能力；然后引入變鄰域搜索算法進行局部搜索，采用針對關(guān)鍵路徑的四種鄰域結(jié)構(gòu)，避免了搜索的盲目性，提高了搜索效率.本文的創(chuàng)新在于對目前研究較少的鑄造生產(chǎn)過程中批次加工與機加工協(xié)同調(diào)度問題建立了優(yōu)化調(diào)度模型并進行了研究.算法創(chuàng)新上，并行混沌搜索與交叉變異算子的結(jié)合使算法具有較好的全局搜索性能.變鄰域搜索算子的引入增強了算法的局部搜索能力.編碼解碼機制的設(shè)計使得算法適用于求解離散調(diào)度問題.最后通過對比實驗驗證了算法的有效性.

1 問題描述與模型

1.1 問題描述

假設(shè)鑄造生產(chǎn)線造型機的造型能力足夠大，則可認為熔煉過程是生產(chǎn)瓶頸，假設(shè)企業(yè)的訂單池足夠大，每次計劃生產(chǎn)系統(tǒng)獲得具有相同材質(zhì)的訂單，從而使鑄件生產(chǎn)線優(yōu)化調(diào)度問題簡化為考慮鑄件質(zhì)量約束的單機優(yōu)化問題[3，15].由于技術(shù)要求，鑄件不能在熔煉和澆注工序之間等待，因此本文將熔煉澆鑄過程視為鑄件的第一道工序.

本文考慮的優(yōu)化問題定義為：針對以熔煉過程為生產(chǎn)瓶頸、只考慮鑄件質(zhì)量約束的鑄造生產(chǎn)線加工過程，優(yōu)化確定給定鑄件的批次劃分結(jié)果、鑄件加工順序以及鑄件工序的加工機器，使整個加工過程的總完工時間最小.

1.2 問題模型

參數(shù)與符號表示

n：待加工鑄件數(shù)量.

N：鑄件集合，N={Ni，i=1，2，…，n}.

qi：鑄件i 的工序數(shù).

Oi：鑄件i 的工序集合，Oi={O（i，j），j=1，2，…，qi}.

mij：鑄件i 的第j 道工序的可用機器數(shù)量.

Mij：鑄件i 的第j 道工序的可用機器集合.

Mij={Mijk，1 ≤k ≤mij}.

tijk：鑄件i 的第j 道工序交給機器Mijk加工所需時間.

w：鑄件質(zhì)量集合，w={wi，i=1，2，…，n}.

m′：熔爐數(shù).

M′：熔爐集合，M′={Md，d=1，2，…，m′}.

Q：熔爐熔煉速度，Q={Qd，d=1，2，…，m′}.

P：熔爐澆鑄速度，P={Pd，d=1，2，…，m′}.

U：熔爐最大熔煉質(zhì)量，U={Ud，d=1，2，…，m′}.

L：鑄件批次劃分結(jié)果.

NTd：第d 個熔爐的爐次數(shù).

Fd：第d 個熔爐的爐次集合，F(xiàn)d={1，2，…，NTd}，f∈Fd表示熔爐d 的第f 個爐次.

Ld：熔爐d 負責的鑄件批次集合，d=1，2，…，m′，l∈Ld表示鑄件批次l.

Cmax：最大完工時間.

A：足夠大的正整數(shù).

xijk：鑄件i 的第j 道工序如果交給機器Mijk加工則xijk=1，否則為0.

yhgj：如果工序O（h，j）在O（g，j）之后加工或O（h，j）不存在或O（g，j）不存在則yhgj=1，否則為0.

Sigk：鑄件i 的第j 道工序在機器Mijk上加工的開始時間.

目標函數(shù)：

式中：式（1）為本文模型的目標函數(shù)，最小化最大完工時間；式（2）表示一道工序只能由一臺機器加工；式（3）表示熔爐每爐次只能生產(chǎn)一種鑄件產(chǎn)品批次組合；式（4）表示只有熔爐當前爐次的熔煉澆鑄工序完成之后才能進行下一爐次的熔爐澆鑄工作；式（5）表示熔爐生產(chǎn)能力約束；式（6）表示每個鑄件只能分配到一個批次當中；式（7）表示鑄件的工序必須在其前一道工序完成之后才能開始加工；式（8）表示除熔爐外一臺機器一次只能加工一道工序.

2 并行混沌優(yōu)化算法（PCOA）

混沌優(yōu)化算法的思想是產(chǎn)生與優(yōu)化變量相同數(shù)目的混沌變量，用類似載波的方式將其引入優(yōu)化變量使其呈現(xiàn)混沌狀態(tài)，把混沌遍歷范圍放大到優(yōu)化變量取值范圍后，用混沌變量取代優(yōu)化變量，直接利用混沌變量搜索[16]，并行混沌優(yōu)化算法在混沌優(yōu)化算法的基礎(chǔ)上引入并行機制，每個優(yōu)化變量由多個混沌變量映射，所有的混沌變量獨立搜索，并行變量的最優(yōu)值為需要的優(yōu)化解，并行混沌優(yōu)化算法的計算過程可以總結(jié)如下.

Step1.初始化，在這一步中，需要設(shè)置的參數(shù)包括總迭代次數(shù)k=1，2，…，S，一次載波迭代次數(shù)S1，并行個數(shù)P，全局最優(yōu)目標函數(shù)值H*，以及混沌變量的隨機初始，其中i=1，2，…，P，代表并行候選個體，j=1，2，…，D，代表優(yōu)化問題的決策變量.

Step2.利用式（9）將混沌變量映射到?jīng)Q策變量的搜索空間內(nèi)，

式中：UBj，LBj分別代表第j 個決策變量的搜索空間上界與下界；表示全局最優(yōu)解對應的解決方案；β為重要的局部搜索參數(shù)，用于調(diào)整決策變量的搜索范圍.

Step4.利用Logistic 一維混沌序列更新混沌變量值，序列表達式：

Step5.迭代直至滿足終止條件.

3 HPCOA 求解鑄造生產(chǎn)線兩階段協(xié)同調(diào)度問題

3.1 編碼與解碼

染色體的編碼與解碼是解決調(diào)度問題的關(guān)鍵，考慮到鑄造生產(chǎn)線優(yōu)化調(diào)度問題的離散特性以及批次加工與機加工協(xié)同調(diào)度的問題，本文提出一種基于工件與機器的分層編碼方式.編碼由工件編碼和機器編碼兩部分組成，分別對應工件的加工順序和工序的加工機器.表1 為一個鑄造生產(chǎn)線調(diào)度問題示例，本文只列出鑄件部分工序用于顯示編碼過程.工件編碼OS 由兩層基因組成，第一層基因S1代表鑄件批次加工過程中的熔煉澆鑄工序，第二層基因S2代表鑄件機加工過程中的工序.假設(shè)初始混沌向量X=[0.7，0.55，0.1，0.3，0.4|0.15，0.6，0.9，0.85，0.2，0.23，0.86，0.73]，利用整數(shù)序列φ 記錄X 中各數(shù)的位置信息，鑄件工序與φ 中數(shù)字一一對應，對X 排序 得X′=[0.1，0.3，0.4，0.55，0.7 |0.15，0.2，0.23，0.6，0.73，0.85，0.86，0.9]，整數(shù)序列作相應變化得新整數(shù)序列φ′.根據(jù)整數(shù)與工序的對應關(guān)系將φ′中數(shù)字替換為代表工件號的基因值即得到工件編碼.最終得到的工件編碼染色體中，每個基因值為工件號，在染色體中出現(xiàn)的次數(shù)等于相應工件的工序總數(shù)，是第幾道工序取決于其位置順序.機器編碼MA 產(chǎn)生過程為，首先產(chǎn)生與加工鑄件總工序數(shù)相等的混沌變量初始值，假設(shè)M=[0.1，0.85，0.67，0.45，0.92，0.31，0.62，0.23，0.18，0.24，0.78，0.05，0.71]，M中基因與基因?qū)墓ば蚩蛇x加工機器數(shù)的乘積向上取整即為選擇的加工機器序號，序號對應的機器即為工序最終選擇的加工機器.例如M 中第一個基因值0.1對應鑄件三的第一道工序O31，O31可選加工機器數(shù)為2，分別為機器一與機器二，基因值與機器數(shù)的乘積向上取整得1，代表O31選擇可選加工機器集中的第一臺機器，即機器一.其他亦然直到所有工序加工機器安排完畢.編碼方案詳細過程如圖2 所示.

圖2 分層編碼示意圖Fig.2 Schematic of layered coding

表1 示例鑄件信息Tab.1 Example casting information

對編碼方案解碼時，假設(shè)熔爐一、二的最大熔煉質(zhì)量為8 和10，首先將工件編碼中S1部分工序按照選擇的熔煉爐進行分類，分類完成后根據(jù)熔爐的最大熔煉質(zhì)量約束進行分批，鑄件分批時，為了提高爐次利用率，盡可能將更多的鑄件劃分到同一批次當中.本例中選擇爐二的鑄件N1、N4、N5，N1、N4的總質(zhì)量為10，N1、N4、N5的總質(zhì)量為14 大于爐二的最大熔煉質(zhì)量，因此將N1，N4組成一批，N5單獨成為一批，詳細分批過程如圖3 所示.根據(jù)分批結(jié)果得出鑄件熔煉澆鑄工序的加工時間之后采取主動調(diào)度[17]的解碼方式對編碼方案進行解碼.

圖3 鑄件分批示意圖Fig.3 Block diagram of casting

3.2 交叉變異策略

在提出的HPCOA 算法中，通過交叉變異策略實現(xiàn)并行解決方案之間的信息交流，提高解的質(zhì)量.交叉和變異策略的引入對于提高算法在每次迭代中解集的多樣性、加快算法收斂速度有較大的作用.交叉方式本文采取優(yōu)先操作交叉[18]，任意劃分工件集合為2 個非空集合，保持一個集合的工件基因不變，交換另一集合的工件基因順序.機器編碼采取單點變異策略，隨機選擇一個位置，在此工序所對應的可選機器集中選擇一個與當前機器號不同的機器，替換當前機器.工件編碼采取逆序變異策略，將染色體中兩不同隨機位置間的基因序列逆序.需要注意的是，本文中的工件編碼由兩層基因組成，因此逆序變異策略在兩層基因上單獨進行且在執(zhí)行交叉變異操作之后，混沌向量做相應改變.

3.3 變鄰域搜索策略

由于混沌的隨機性強、導致PCOA 算法在最優(yōu)解鄰域搜索時收斂速度變慢，算法的局部搜索能力較弱，為了提高算法的收斂速度，本文將PCOA 算法與變鄰域搜索（variable neighborhood search，VNS）算法結(jié)合從而開發(fā)出更有效的混合優(yōu)化算法.VNS 算法通過對當前最優(yōu)解進行不同鄰域的反復遞進搜索，使當前最優(yōu)解不斷向全局最優(yōu)解靠近.具有強大的局部搜索能力，在車間調(diào)度問題中展示出了優(yōu)異的性能[19-20].鄰域結(jié)構(gòu)的選擇對VNS 的求解質(zhì)量和執(zhí)行效率有很大的影響.研究表明，對關(guān)鍵路徑上的工序塊進行鄰域搜索是改善解質(zhì)量的最有效方式[21]且在一個關(guān)鍵塊內(nèi)交換內(nèi)部操作不會減少最大完工時間[22].關(guān)鍵塊的確定參考文獻[23].假設(shè)一個關(guān)鍵塊KB={KB1，KB2，…，KBn-1，KBn}，其中KB1，…，KBn，代表關(guān)鍵工序，首先定義三個函數(shù)：1）Swap（x，y）表示交換工序x 和y；2）Insertb（x，y）表示將x 插入y 的正后方；3）Insertf（x，y）表示將x 插入y 的正前方.本文給出如下四種有效鄰域：

N1：選擇關(guān)鍵塊塊內(nèi)工序，將其插入塊首工序之前或塊尾工序之后，N1可表述如下：

N2：將關(guān)鍵塊的前兩道工序與關(guān)鍵塊的后兩道工序互相交換.N2可表述如下：

N3：將關(guān)鍵塊塊首工序插入關(guān)鍵塊內(nèi)部.N3可表述如下：

N4：將關(guān)鍵塊塊尾工序插入關(guān)鍵塊內(nèi)部.N4可表述如下：

變鄰域搜索步驟如下所述：

Step1.給定初始解H，確定解的關(guān)鍵塊，定義m個鄰域，i=1.

Step2.使用鄰域結(jié)構(gòu)Ni進行搜索，如果在鄰域內(nèi)找到比H 更優(yōu)的解H′，則令H=H′，i=1.

Step3.如果搜遍鄰域結(jié)構(gòu)Ni仍找不到比H 更好的解，則令i++.

Step4.if i≤m，轉(zhuǎn)Step2.否則輸出最優(yōu)解H.

3.4 算法的實現(xiàn)

本文針對鑄造生產(chǎn)線全流程優(yōu)化調(diào)度問題，提出了結(jié)合并行混沌優(yōu)化與變鄰域搜索的混合算法.混合算法擁有良好的全局搜索與局部搜索能力，產(chǎn)生新解能力強，搜索精度高，對初始值不敏感，不易陷入局部最優(yōu)解，在解決本文提出的鑄造生產(chǎn)線全流程調(diào)度模型問題時表現(xiàn)出良好的性能.算法具體步驟如下，流程圖如圖4 所示.

圖4 HPCHO 算法流程圖Fig.4 Flowchart of HPCHO

Step1.確定算法參數(shù).設(shè)置迭代次數(shù)k=1，指定最大迭代次數(shù)S、一次載波迭代次數(shù)S1、并行數(shù)P.

Step2.初始化.隨機產(chǎn)生與種群數(shù)相等的混沌初始向量，一個初始向量中包含與工序個數(shù)相等的隨機數(shù).

Step3.確定當前迭代次數(shù)，利用式（9）與本文提出的編碼解碼規(guī)則將混沌向量映射到?jīng)Q策變量的搜索空間內(nèi).

Step4.采取交叉變異策略形成新解，如果新解的目標函數(shù)得以改進，則用新解替代原來的解.

Step5.對解進行變鄰域搜索操作，直到解的工序塊中所有關(guān)鍵工序都已移動完畢，不能繼續(xù)改進，結(jié)束鄰域搜索.

Step6.利用式（10）的混沌序列函數(shù)更新混沌向量中隨機數(shù)的值，得到新的混沌向量.

Step7.if k≥S，則終止搜索，否則轉(zhuǎn)Step3.

4 仿真研究

為便于分析算法性能，本文結(jié)合實際鑄造生產(chǎn)線生產(chǎn)加工情況，參考文獻[3]和[9]設(shè)計測試算例，數(shù)據(jù)按任務與資源的規(guī)模分為小、中、大三類算例.具體參數(shù)設(shè)置見表2.對于表中有范圍限制的參數(shù)均采用隨機的方式在指定范圍內(nèi)生成數(shù)據(jù)，其中，質(zhì)量單位為t，時間單位為h，速度單位為t/h.

表2 算例數(shù)據(jù)參數(shù)取值Tab.2 Numerical example data parameter value

為了驗證本文提出的HPCOA 算法對模型求解的有效性，我們選取傳統(tǒng)的并行混沌優(yōu)化算法（PCOA）、經(jīng)典的遺傳優(yōu)化算法（GA）與融合禁忌搜索的混合離散灰狼優(yōu)化算法（HDMGWO）[8]在三類算例上與HPCOA 進行了對比實驗，其中PCOA 與HPCOA 在參數(shù)的選取上保持一致，PCOA 在迭代過程中取消了交叉變異步驟與變鄰域搜索步驟.算法均使用Matlab R2018 b 實現(xiàn)，在CPU2.2.GHz、4GB 內(nèi)存的環(huán)境下運行.經(jīng)過實驗測試，設(shè)置小規(guī)模算例算法的運行時間為300 s，中等規(guī)模算例算法運行時間為600 s，大規(guī)模算例算法運行時間為900 s.PCOA與HPCOA 算法一次載波運行時間占總運行時間的1/3.并行數(shù)P=50，HDMGWO 算法的禁忌搜索次數(shù)在三類算例上分別取值為20、40、60.算法的交叉概率Pc=0.7，變異概率Pm=0.5，種群規(guī)模N=50.為了排除隨機性的影響，每個算例求解15 次，計算結(jié)果如表3 所示，其中，Best 為算例15 次求解結(jié)果中，最大完工時間的最優(yōu)值.Avg 為算例15 次求解結(jié)果的平均值，StDev 為算例15 次求解結(jié)果的標準差.Worst 代表算例15 次求解結(jié)果的最差值.

表3 不同任務規(guī)模下算法計算結(jié)果比較Tab.3 Comparison of computational results for different task sizes

圖5 為按任務規(guī)模計算的算法性能比分析圖，圖6 為四種算法不同算例下Avg 值、Best 值與Worst值的對比分析圖.圖中可以看出，HPCOA 與GA、HDMGWO 及PCOA 相比，在不同任務規(guī)模下混合算法都能取得最優(yōu)的結(jié)果，且任務規(guī)模越大算法性能越好，這是因為隨著任務規(guī)模的擴大，問題的解空間急速擴張，而GA 與PCOA 缺乏強大的局部搜索能力，容易陷入局部最優(yōu)解，從而影響算法整體的性能.HDMGWO 不如HPCOA 的原因在于HDMGWO每次交叉的父代之一來自于當前種群最優(yōu)的三個解中的一個，這導致算法的全局搜索能力變?nèi)?，影響了算法最終的表現(xiàn).

圖5 按任務規(guī)模計算的算法性能比Fig.5 Algorithm performance ratio by task size

圖6 算法在不同算例下Best、Avg與Worst值的對比分析Fig.6 Comparison and analysis of the Best、Avg and Worst value of the algorithm in different examples

算法穩(wěn)定性方面，如圖7 所示，隨著算例規(guī)模擴大，StDev 值明顯增加，但總體而言，PCOA 在不同算例規(guī)模上StDev 值都最小，但由于其每次求得的解質(zhì)量都不高，導致其總體性能一般，而HPCOA 雖然StDev 值較大，但算法在大規(guī)模算例下15 次求解結(jié)果的最差解甚至要優(yōu)于其他算法得到的最優(yōu)解.因此，綜合考慮算法的性能，本文提出的混合并行混沌優(yōu)化算法能更有效地解決本文所提出的鑄造生產(chǎn)線優(yōu)化調(diào)度問題.

圖7 算法不同算例下的StDev 值Fig.7 StDev values under different calculation examples of the algorithm

5 結(jié)論

鑄造生產(chǎn)線加工過程分為批次生產(chǎn)加工和單件機加工兩個階段，針對鑄造生產(chǎn)線生產(chǎn)加工過程當中熔煉澆鑄加工與機加工協(xié)同調(diào)度問題，以總完工時間最小為目標函數(shù)，建立了以熔煉過程為生產(chǎn)瓶頸、只考慮鑄件質(zhì)量約束的鑄造生產(chǎn)線全流程優(yōu)化調(diào)度模型.為求解該模型，本文設(shè)計了一種HPCOA算法，算法設(shè)計獨特的編碼解碼機制并在算法中引入變鄰域搜索與交叉變異策略以避免算法陷入局部最最優(yōu)值，提高了算法的局部搜索能力，增強了算法的開發(fā)效率.仿真實驗表明HPCOA 算法在求解本文所提出的鑄造生產(chǎn)線優(yōu)化調(diào)度問題時具有比GA、PCOA、HDMGWO 算法更好的性能.