王 朝，潘順發(fā)，方 博，周 林，張海濤，唐紅濤

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

機械行業(yè)中鑄件占機械產(chǎn)品總產(chǎn)量的80%，鑄造行業(yè)是離散制造企業(yè)的基礎(chǔ)行業(yè)[1]。鑄造行業(yè)推動自身信息化進程，實現(xiàn)鑄造行業(yè)整體的智能化、自動化、信息化水平是未來鑄造行業(yè)發(fā)展面臨的關(guān)鍵問題[2]。大部分鑄件的生產(chǎn)模式是砂型鑄造。砂型鑄造分為混砂、造型、制芯、熔煉和清理5道工序?？紤]鑄件造型的復(fù)雜性，鑄造企業(yè)普遍采用人工班組進行造型和制芯。混砂和熔煉工序是鑄造的主要工序，某批次鑄件訂單任務(wù)確定投產(chǎn)后，混砂在造型之前加工，熔煉在限定時間段內(nèi)獨立加工。Dos等[3]探討熔煉爐在單階段內(nèi)熔煉多少合金的問題，采用改進元啟發(fā)算法求解，計算結(jié)果在自動化鑄造企業(yè)中得到了應(yīng)用和驗證。對鑄造工藝剖析，將其轉(zhuǎn)變成經(jīng)典柔性流水車間調(diào)度優(yōu)化問題。柔性流水車間調(diào)度問題作為一種典型的優(yōu)化組合問題，一般通過智能算法用于求解該類問題。張其亮等[4]采用一種混合粒子群算法解決不考慮工件運輸條件約束的柔性流水車間調(diào)度問題，首先采用粒子群算法解決機器資源調(diào)度，然后確定工件加工順序，最終通過平移計算差值算法求解目標函數(shù)值。畢孝儒等[5]采用一種新型人工蜂群算法，采用全局最優(yōu)蜜源搜索策略強化改良算法的探索能力,避免算法出現(xiàn)陷入局部最優(yōu)現(xiàn)象。筆者結(jié)合國內(nèi)砂型鑄造車間單件小批量模式下鑄件的實際生產(chǎn)環(huán)境，針對砂型鑄造的熔煉工序具有多約束的特征，提出熔煉工序弱化機制，建立以總完工時間最小為目標的柔性流水車間調(diào)度模型。采用改進蛙跳算法(suffled frog leaping algorithm-simulated annealing,SFLA-SA)求解模型，通過反向?qū)W習策略改善初始種群，改進的蛙跳算法中嵌入具有3種鄰域結(jié)構(gòu)的模擬退火搜索局部搜索以提高算法局部搜索能力。最后將模型應(yīng)用于某鑄造企業(yè)以檢驗?zāi)Ｐ偷挠行?，與蛙跳算法SFLA(suffled frog leaping algorithm)，遺傳算法GA(genetic algorithm)和粒子種群算法PSO(particle swarm optimization)算法對比，表明改進蛙跳算法(SFLA-SA)的有效性和優(yōu)越性。

1 問題描述

1.1 典型砂型鑄造工藝流程分析

典型砂型鑄造工藝包括鑄型準備、鑄造金屬的熔化與澆注、鑄件處理和檢驗3大部分。砂型鑄造加工車工種大致可以分為2類，一類是機械加工，另一類是非機械加工。某典型砂鑄企業(yè)生產(chǎn)流程如圖 1所示。砂型鑄造工藝路線分為6道主要工序，即造型、制芯、熔煉、澆注、落砂和清理。在砂型鑄件的生產(chǎn)過程中，造型和制芯工序一般由人工班組進行操作，根據(jù)鑄件實際生產(chǎn)特點，將造型和制芯作為一道工序。

圖1 典型砂型鑄件生產(chǎn)工藝流程圖

1.2 熔煉工序弱化機制

熔煉工序不同于鑄件其他工序，不存在對單個鑄件單獨熔煉鐵水的操作，某批次鑄件的熔煉工序作為同一道工序即公共工序。當某批次生產(chǎn)鑄件數(shù)量確定時，根據(jù)鑄件工藝出品率等相關(guān)參數(shù)可確定熔煉工序所需熔煉鐵水的量，如式(1)所示。

(1)

式中：Mt為該批次生產(chǎn)中所需熔煉鐵水的總重量；mr為第r個鑄件的重量；kg為工藝出品率；s為該批次所需生產(chǎn)鑄件的數(shù)量。

在熔煉設(shè)備和熔煉工藝水平穩(wěn)定的前提下，熔煉工序所需熔煉鐵水量的確定，熔煉工序所需時間確定。砂型鑄件生產(chǎn)中熔煉工序加工時間較長，熔煉爐耗電量占鑄件生產(chǎn)能耗較大部分。為減少能耗，熔煉工序開始時間在晚上8點以后才符合實際生產(chǎn)。針對熔煉工序一般在限定時間段內(nèi)獨立進行，下芯合箱工序?qū)θ蹮捁ば虿淮嬖谙拗萍s束，熔煉工序?qū)沧⒐ば虼嬖谙拗萍s束的特點提出熔煉工序弱化機制，即將熔煉工序作為砂型鑄造生產(chǎn)中工件的下芯合箱工序和澆注工序之間特定時間區(qū)間內(nèi)的固定調(diào)整時間段。

2 柔性砂型鑄造流水車間調(diào)度模型建立

經(jīng)典柔性流水車間調(diào)度(flexible foow shop scheduling problem,FFSP)描述為：在m個資源和n個工件的生產(chǎn)環(huán)境下，所有的工件必須經(jīng)過多道工序加工，各道工序可選加工資源設(shè)備集合已知，至少多于一道工序存在多個可選加工資源設(shè)備，這些資源的性能可相同也可不同。在傳統(tǒng)的FFSP問題研究基礎(chǔ)上，考慮砂型鑄造實際生產(chǎn)狀況后提出熔煉工序弱化機制。該砂型鑄造車間調(diào)度模型存在以下假設(shè)：①初始時刻，所有資源均可用，所有鑄件的第一道工序均可加工；②任意工序只能選定某一種資源進行加工，且加工過程連續(xù)不間斷；③任意一種資源在某一時刻只能對鑄件的某道工序單獨加工，每種資源前可容納無限量的待加工工件；④同一鑄件不同工序間存在加工順序限制，多個鑄件之間不存在加工順序限制機制；⑤鑄件任意工序的加工時間包含有效加工時間和調(diào)整時間兩部分；⑥工序移動時間忽略；⑦鑄件不考慮成批運輸情況。

柔性砂型鑄造流水車間調(diào)度的數(shù)學模型描述和相關(guān)概念的定義為：n為待加工鑄件數(shù)量；J為待加工鑄件集合，J={Ji,1≤i≤n}；Ji為第i個加工鑄件(i=1,2,3,…,n)；m為鑄件加工資源總數(shù)；M為鑄件加工資源集合，M={Mh,1≤h≤m}；Mh為第h個加工資源(h=1,2,3,…,m)；j為工序序號；Oij為第i個鑄件的第j道工序；Oijh為工序Oij在加工資源h上加工；tijh為工序Oij在加工資源h上的有效加工時間；Biq為鑄件i的下芯合箱工序的完工時間；Jiq為鑄件i的下芯合箱工序的固定休整時間；Mend為該批次鑄件的公共工序即熔煉工序完工時間；Aij為鑄件i的第j道工序的起始加工時刻；Bij為鑄件i的第j道工序的加工結(jié)束時刻；Bijh為工序Oij在機器h上最早完工時刻；Bi(j-1)l為工序Oi(j-1)在機器l上最早完工時刻；Bi′j′h為機器h上加工工序Oij的相鄰上一道工序Oi′j′在機器h上最早完工時刻；Ci為第i個鑄件的最后一道工序的完工時刻；Cmax為最大完工時間。該調(diào)度模型的決策變量如下，xijh為0-1變量，工序Oij在加工資源h上加工則xijh=1，否則為0。Rijgh為0-1變量，工序Oij先于工序Ogh在加工資源h上加工則Rijgh=1，否則為0?？紤]最小化某批次鑄件的最大完工時間，目標函數(shù)和約束限制條件如下：

minf1=max(Ci)i=1,2,…,n

(2)

(3)

(4)

(5)

Ai(j+1)≥Bi,j

(6)

(7)

Aijh≥Bi′j′h

(8)

(9)

其中式(2)為模型的目標函數(shù)，即最小鑄件最大完工時間。式(3)中Ci為第i個鑄件的完工時間。式(4)中Delijh為安排在加工資源h上的工序Iij因機器資源約束而延遲的時間。式(5)中TX為第i個鑄件由于熔煉工序弱化機制而延遲的時間。式(6)為同一種鑄件的不同工序的加工順序約束限制機理，表明鑄件的某道工序只能在前一道工序加工完成后才可開始加工。式(7)為工序的完工時間限制條件，在柔性流水車間調(diào)度中，工序的加工過程不可以被中斷，也就是說工序完工時間應(yīng)為工序的起始時間和其在所選擇資源上加工時間的和。式(8) 限制了同一時刻內(nèi)每個資源設(shè)備只能對鑄件某道工序進行加工。式(9)為鑄件的任意一道工序存在多個可選加工資源，但其任意一道工序只能被可選加工資源集中某個資源單獨加工。

3 基于改進蛙跳算法的調(diào)度模型求解

基本蛙跳算法(suffled frog leaping algorithm，SFLA)是一種全新的生物進化算法，其受到自然界尋找食物的青蛙種群啟示。SFLA參數(shù)簡單，算法計算效率高、全局尋優(yōu)能力強[6]。目前為止蛙跳算法已經(jīng)被應(yīng)用到很多優(yōu)化問題中并取得了良好的效果。模擬退火算法(simulated annnealing,SA)是一種全局最優(yōu)的串行結(jié)構(gòu)的優(yōu)化算法，其賦予搜索過程采用一種時變概率突跳性機制，可以有效的避免SFLA陷入局部最優(yōu)[7]。筆者在基于基本蛙跳算法的基礎(chǔ)上采用一種改進的蛙跳算法(SFLA-SA)用于求解柔性砂型鑄造流水車間調(diào)度問題。

3.1 染色體編碼與解碼

參考文獻[8]采用雙層編碼，一層基于加工工序，給鑄件的所有工序確定加工順序，一層基于可選機器，給工序選擇可選加工機器。各層編碼長度均為工序總數(shù)，編碼取值范圍為[0,1]。表1為3個鑄件在3臺機器上加工的柔性調(diào)度問題示例。3個鑄件的總工序數(shù)為8，則兩層編碼的長度均為8。隨機給定以下編碼：工序?qū)泳幋a為[0.07,0.88,0.73,0.53,0.96,0.84,0.81,0.66]，機器層編碼為[0.24,0.83,0.28,0.17,0.72,0.53,0.45,0.29]。相應(yīng)的第一層解碼過程如下：將第一層解碼結(jié)果按其數(shù)值升序排列，令最小的3處數(shù)值為1，數(shù)值排在第4和5位處編碼設(shè)置為2，令最大的3處數(shù)值為3，并按照各個工件的加工順序來確定所有工序排列規(guī)則，工序?qū)泳幋a結(jié)果如圖2所示。機器層編碼依據(jù)工序?qū)泳幋a的解碼結(jié)果采用基于輪盤賭選擇算子的解碼方法，在各個工序下面的第二層編碼數(shù)值用于確定該工序?qū)?yīng)的加工機器。例如，O1,1對應(yīng)的編碼數(shù)值為0.24，該數(shù)值表示確定進行工序O1,1加工的機器編號。加工機器的選擇采用輪盤賭模型，由參數(shù)設(shè)置可知，O1,1工序可在機器1、機器2和機器3上進行加工，因而當編碼數(shù)值在[0,1/3) 上時，O1,1由機器1加工，當編碼數(shù)值在[1/3,2/3)上時，O1,1由機器2加工，當編碼數(shù)值在[2/3,1]上時，O1,1由機器3加工。由于0.24在[0,1/3)上，因此O1,1由機器1加工。機器層編碼解碼結(jié)果見圖3所示。圖4為兩層編碼對應(yīng)的解碼結(jié)果的甘特圖。

表1 示例鑄件信息

圖2 工序?qū)泳幋a解碼示意圖

圖3 機器層編碼解碼示意圖

圖4 雙層編碼解碼對應(yīng)甘特示意圖

3.2 種群初始化

筆者參考文獻[9],改進蛙跳算法采用反向?qū)W習構(gòu)造初始種群解?；舅悸窞椋菏紫入S機生成N個初始種群解。隨后針對每個隨機解構(gòu)建其反向解得到N個反向解。最后在2N個初始解中選擇較優(yōu)的N個解組成初始種群。

3.3 基于模擬退火算法的局部搜索策略

標準SFLA算法種群的全局最優(yōu)解和各子種群的最優(yōu)解的優(yōu)劣質(zhì)量對種群進化具有重要影響。改進蛙跳算法采用模擬退火算法來對各子種群的群內(nèi)最優(yōu)解進局部搜索，以達到提高各子種群的群內(nèi)最優(yōu)解和全局最優(yōu)解的質(zhì)量。在SFLA-SA中，采用SA對子種群群內(nèi)最優(yōu)解局部搜索，由當前解生成變異解的過程采用交換、翻轉(zhuǎn)和插入3種變異算子[10]。結(jié)合工序?qū)泳幋a示意圖對3種變異敘述如下：

(1)交換變異。隨機交換當前解上兩處位置上的編碼，如圖5所示，選擇待變異解編碼的第3和第6位置交換。

圖5 交換變異

(2)翻轉(zhuǎn)變異。隨機翻轉(zhuǎn)當前解上的兩處位置間的編碼，如圖6所示，選擇待變異解第3和第7編碼處位置，翻轉(zhuǎn)變異。

圖6 翻轉(zhuǎn)變異

(3)插入變異。隨機將某位置上的編碼數(shù)值插入到另一位置之前，如圖7所示，將待變異解第6位置處編碼插到位置2之前。

圖7 插入變異

3.4 改進蛙跳算法的基本流程

Step 1：SFLA算法與SA局部搜索算法的基本參數(shù)設(shè)置。初始種群規(guī)模為N；子種群數(shù)目為m；子種群個體數(shù)為n；種群迭代次數(shù)為Maxit；初始溫度為T0；內(nèi)循環(huán)次數(shù)為L；溫度退化率為ps。

Step 2：隨機生成N個個體，采用反向?qū)W習法得N個個體，計算全部個體適應(yīng)度值，按降序排列選擇較優(yōu)的N個個體構(gòu)建初始種群P0，令t=0; 隨機選擇個體作為全局最優(yōu)解gbest。

Step 3：降序排序初始種群適應(yīng)度值，將N個個體均勻分配在m個子種群中。

Step 4：若t

Step 5：采用SA算法對各個子種群中的最優(yōu)解進行局部搜索，更新各個子種群的最優(yōu)解。

Step 6：SFLA-SA算法采用均勻抽樣選擇子種群的子集并更新子集中最劣解。

Step 7：令t=t+1并更新種群的全局最優(yōu)解gbest，轉(zhuǎn)Step 5。

改進SFLA-SA算法的基本流程如圖8所示。

圖8 改進蛙跳算法基本流程圖

4 案例應(yīng)用與分析

4.1 案例描述

以某砂型鑄造企業(yè)為例驗證模型以及算法的有效性，該企業(yè)客戶訂單多為機床類零部件，鑄件材質(zhì)單一。對其某個周期內(nèi)的訂單進行調(diào)度研究,該批鑄件開始加工時間為早8點，該周期鑄件熔煉公共工序起始時刻為當天晚8點，所需時間為5 h。該周期內(nèi)一共有6個鑄件單件需要鑄造生產(chǎn)且屬于同一材質(zhì)。該周期實際生產(chǎn)數(shù)據(jù)如表2所示，各工序的可調(diào)度資源一共有14個，表2中可用資源集是鑄件該道工序可以加工的資源序號集合，加工時間集與可用資源集的順序相對應(yīng)。

4.2 案例求解與分析

算法在Windows 10系統(tǒng)、CPU主頻四核2.3 GHz、運行內(nèi)存8 GB的計算機中運行，軟件為MATLAB R2016。選取標準蛙跳算法(SFLA)、傳統(tǒng)遺傳算法(GA)以及文獻[11]中所提粒子群算法(PSO)進行對比, 驗證SFLA-SA對模型求解的有效性及優(yōu)越性。其中SFLA與SFLA-SA在參數(shù)上的選取均一致，SFLA采取隨機種群初始化，且迭代過程未采取局部搜索，其他算子均與SFLA-SA一致。本文算法參數(shù)采用正交實驗設(shè)計法進行選取，經(jīng)過組合實驗得最優(yōu)參數(shù)：子種群數(shù)目為10，局部搜索次數(shù)為10，子種群數(shù)目為20，迭代次數(shù)MaxIt為400。GA染色體解碼方案和PSO粒子解碼方案及算法流程與文獻[11]一致，種群大小與迭代次數(shù)均和SFLA-SA相同，其余參數(shù)采用文獻[11]中建議參數(shù)。四種算法最優(yōu)迭代曲線如圖9所示，由于SFLA-SA采用了反向?qū)W習規(guī)則構(gòu)建初始種群，初始種群質(zhì)量相比PSO、GA和SFLA有較大提升，同時SA局部搜索算子使SFLA-SA能跳出局部陷阱。

表2 某鑄造企業(yè)某周期生產(chǎn)鑄件信息

圖9 四種算法最優(yōu)解迭代曲線對比

為驗證SFLA-SA的穩(wěn)定性，分別使用4種算法求解30次，算法穩(wěn)定性如表3所示。根據(jù)分析可知，PSO表現(xiàn)最差。SFLA-SA表現(xiàn)最優(yōu)，但迭代過程加入SA導致其運行速度稍慢，綜合分析可知SFLA-SA尋優(yōu)能力最強。圖10為SFLA-SA對模型求解30次所得最優(yōu)解36.05對應(yīng)的甘特圖，圖10中矩形代表鑄件工序，矩形長度表示工序加工時間，符號表示工序信息，例如符號為O4,1表示4號鑄件的第一道工序。

表3 算法穩(wěn)定性分析

圖10 改進蛙跳算法(SFLA-SA)最優(yōu)解甘特圖

5 結(jié)論

筆者構(gòu)建了以總完工時間最小為目標的柔性砂型鑄造流水車間調(diào)度模型。通過對某企業(yè)案例分析，驗證所采用SFLA-SA求解模型的有效性和優(yōu)越性，求解結(jié)果對砂型鑄件的實際生產(chǎn)具有現(xiàn)實意義。