集成供應(yīng)流程的多工廠單元化制造人工魚群優(yōu)化

柳春鋒，趙善林，王居鳳

（1.杭州電子科技大學(xué) 管理學(xué)院，浙江 杭州 310018；2.中國計量大學(xué)，浙江 杭州 310018）

一、引言

經(jīng)濟的發(fā)展與人們消費模式的轉(zhuǎn)變給企業(yè)帶來了越來越短的產(chǎn)品周期和交貨期壓力。無論是高端裝備產(chǎn)品（如運載火箭箭體結(jié)構(gòu)），還是普通民用產(chǎn)品（如顯示器液晶模組），都能利用單元化制造提高市場響應(yīng)能力。互聯(lián)網(wǎng)的飛速發(fā)展，也使企業(yè)的制造單元實現(xiàn)了最大程度的共享，增強了制造系統(tǒng)內(nèi)部生產(chǎn)信息與外部供應(yīng)信息的交流能力。

國內(nèi)外許多學(xué)者圍繞著單元制造系統(tǒng)的優(yōu)化設(shè)計作了有益的探索。Liu 等（2016）[1]提出了在雙資源約束條件下單元制造系統(tǒng)中的單元構(gòu)建和任務(wù)調(diào)度的聯(lián)合決策模型，并通過啟發(fā)式細(xì)菌覓食算法對模型進行了數(shù)值檢驗。Méndez-Vázquez和Nembhard（2019）[2]在研究單元構(gòu)建時考慮了員工異質(zhì)性、知識轉(zhuǎn)移等人力資源因素。Kumar 和Singh（2017）[3]提出了一種新的基于相似性得分的兩階段啟發(fā)式算法，來最小化整個計劃期的單元間/單元內(nèi)物料控制成本和重新配置成本。Liu 等（2016）[4]為光纖連接器制造業(yè)CMS 建立了員工分配與生產(chǎn)計劃的集成優(yōu)化模型；另外，Liu 等（2018）[5]也提出了一種基于五階段啟發(fā)式算法的集成細(xì)菌覓食算法，實驗表明所提算法比基于啟發(fā)式的混合模擬退火算法和基于啟發(fā)式的混合遺傳算法更優(yōu)。Aalaei 和Davoudpour（2016）[6]構(gòu)建了一種動態(tài)虛擬單元制造系統(tǒng)和供應(yīng)鏈設(shè)計雙目標(biāo)優(yōu)化模型，考慮了多期生產(chǎn)計劃中的工廠和設(shè)施位置因素。

在實際的制造業(yè)中，產(chǎn)品可能在多個工廠的多個單元內(nèi)生產(chǎn)。如果這些單元都位于單個制造工廠，相應(yīng)的供應(yīng)鏈系統(tǒng)設(shè)計步驟也許能獨立進行，即先為每個制造工廠設(shè)計單元制造系統(tǒng)，再選擇采購和原材料運輸成本最低的供應(yīng)商。不過集成的供應(yīng)鏈設(shè)計無疑能最大程度地共享多工廠產(chǎn)能、并降低供應(yīng)成本。目前還很少有文獻涉及到這類集成的優(yōu)化問題。本文試圖建立一個融合產(chǎn)品簇識別、機器單元構(gòu)建、多工廠間在制品工藝路徑、原料供應(yīng)決策的綜合模型。另外，鑒于近幾年興起的人工魚群算法在求解連續(xù)型優(yōu)化問題上展現(xiàn)的優(yōu)越性能，本文設(shè)計了離散型人工魚群算法來解決高維度的單元化制造優(yōu)化問題。

二、問題描述以及模型建立

（一）問題描述

現(xiàn)實生活中，集團公司或聯(lián)盟企業(yè)的生產(chǎn)系統(tǒng)一般由許多工廠組成，每個工廠可以構(gòu)建一定數(shù)量的制造單元。各制造單元中，機器數(shù)量有一定的限制，而各類型的機器至多配置一臺。這些工廠將生產(chǎn)多種產(chǎn)品，已知需求是確定性的，即生產(chǎn)出的產(chǎn)品一定會有市場需求。產(chǎn)品不同的處理工序需要對應(yīng)的機器進行加工。產(chǎn)品可以被轉(zhuǎn)移到同一工廠的不同單元或不同工廠的單元中進行下一道工序的生產(chǎn)。每種產(chǎn)品需要一種原材料，各供應(yīng)商處有工廠需要的任意類型的原材料，并且能滿足工廠的需求。本問題旨在研究多工廠單元制造系統(tǒng)中的單元制造結(jié)構(gòu)和工廠之間的物流，同時選擇合理的供應(yīng)商，達(dá)到單元制造系統(tǒng)運行成本最小化的目的。

（二）參數(shù)說明

1.參數(shù)

NP：產(chǎn)品種類數(shù)；

NO：產(chǎn)品所需要的工序數(shù)；

NL：工廠數(shù)量；

NC：每個工廠制造單元的數(shù)量；

NF：供應(yīng)商的數(shù)量；

NM：機器種類數(shù)；

i：產(chǎn)品類型的索引號（i=1，2，3，…，NP）；

j：工序的索引號（j=1，2，3，…，NO）；

m：機器類型的索引號（m=1，2，3，…，NM）；

l：工廠的索引號（l=1，2，3，…，NL）；

c：單元的索引號（c=1，2，3，…，NC·NL）（將各工廠的單元累加后進行編號）；

f：供應(yīng)商的索引號（f=1，2，3，…，NF）；

amij：如果機器m 有能力處理產(chǎn)品i 的工序j則為1，否則為0；

tijm：產(chǎn)品i 的工序j 在機器m 上完成所需的時間；

MFCm：每臺機器m 的固定使用成本；

MVCm：每臺機器m 的單位時間使用成本；

L：單元內(nèi)機器最少數(shù)量；

U：單元內(nèi)機器最多數(shù)量；

ISC：兩個工廠之間運輸單個在制品的成本；

ICC：同一個工廠內(nèi)兩個單元間運輸單個在制品的成本。

2.決策變量

Xlif：如果工廠l 中產(chǎn)品i 的原材料是由供應(yīng)商f 提供的則為1，否則為1；

Ymlc：如果機器類型m 被分配到工廠l 的單元c 內(nèi)則為1，否則為0；

Kijlc：產(chǎn)品i 的工序j 在工廠l 的單元c 進行生產(chǎn)，則為1，否則為0。

（三）數(shù)學(xué)模型

目標(biāo)函數(shù)Cost 為總的運作成本，其中：式（1-1）表示機器的固定成本和變動成本；式（1-2）表示不同工廠之間產(chǎn)生的物流成本；式（1-3）表示只要發(fā)生工廠間和工廠內(nèi)的單元間移動，都按單位成本ICC 折算入工廠內(nèi)單元間的移動成本。所以多折算的工廠間的單元間移動成本將在（1-4）剔除；式（1-4）表示按單位成本ICC 折算的工廠間的單元間移動成本；式（1-5）表示進貨固定成本和變動成本。約束式（2）表示每種產(chǎn)品的每道工序僅在某個工廠中某個單元內(nèi)的某臺機器上完成。約束（3）和（4）分別表示每個制造單元內(nèi)機器數(shù)量不能低于下限、不能高于上限。約束（5）表示任意產(chǎn)品的原材料供應(yīng)商是唯一的。約束（6）表示如果某產(chǎn)品的某工序在一制造單元內(nèi)加工，則該單元必須有一臺機器支持該工序的加工。約束（7）、（8）、（9）是各個決策變量的取值范圍。

三、離散型人工魚群算法

該算法的基本思想為：在一片水域中，魚群最有可能生存在營養(yǎng)物質(zhì)最多的地方，算法根據(jù)這一特點來模仿魚群的覓食等行為，從而實現(xiàn)全局最優(yōu)[7]。

（一）人工魚編碼

本文的編碼方式如下：根據(jù)問題的決策變量形成一個人工魚，其中包含三個解，分別為Xlif，Kijc和Ymlc（為方便編碼，將各工廠的所有單元進行累加，Kijlc可轉(zhuǎn)化為Kijc）。下面舉例說明三個解所代表的含義。

上述矩陣Xlif的行代表產(chǎn)品類型，列代表工廠，矩陣中的數(shù)字代表供應(yīng)商，比如上面加粗的1代表：工廠2 中產(chǎn)品3 的原材料由供應(yīng)商1 供應(yīng)。

上述矩陣Kijc的行代表產(chǎn)品類型，列代表工序，矩陣中的數(shù)字代表加工該工序所在的單元，比如上述加粗的3 代表：產(chǎn)品3 的工序4 在單元3 中進行。由此，單元3 內(nèi)必須有加工該工序的機器，從而對Ymlc初始化產(chǎn)生影響。

Ymlc矩陣的行代表機器類型，列代表單元的編號（將兩工廠所有單元累計編號，可確定各單元屬于哪個工廠）。Ymlc矩陣的特定位置的值可以由Kijc矩陣和以下輸入?yún)?shù)amij決定。下文涉及amij處都取此值。

上述加粗的（0，0，0，1）表示機器4 有能力對產(chǎn)品3 的工序4 進行加工。

Ymlc矩陣先部分初始化為如上矩陣。其中數(shù)字1 代表某單元內(nèi)配備該種機器，例如，上述矩陣中加粗的1 表示，單元3 中有類型4 的機器。標(biāo)框□的位置代表需要進一步被隨機賦值為0 或者1，得到下面的矩陣，其中數(shù)字0 代表某單元內(nèi)沒有配備該種機器。

（二）人工魚群算法的基本術(shù)語

1.人工魚之間的距離：人工魚個體A 與B 之間的距離表示為distance（A，B）=||RA-RB||，其中RA與RB是人工魚A 與B 的位置。本離散問題中，其中sign（x）=即在兩條魚的相同位置上如果值相同則取0，否則取1。例如，假設(shè)人工魚A 的三個解分別為：

2.人工魚的視野：假定視野范圍是Visual，則人工魚只能在視野Visual 范圍內(nèi)進行覓食。

3.人工魚的鄰居：若人工魚A 與B 之間的距離distance（A，B）＜Visual，則表示A 與B 互為鄰居。

4.人工魚的聚群中心：統(tǒng)計人工魚的所有鄰居中，每條人工魚三個解中每個位置出現(xiàn)次數(shù)最多的基因，將該基因填進對應(yīng)位置，以此形成聚群中心（即一個虛擬的人工魚）。例如：人工魚1 有鄰居2 和3則對于中E 位置出現(xiàn)次數(shù)最多的基因為1，故E=1，以此類推得到的中心同理得到的中心，但得到的未必是可行解。假設(shè)模型中L 和U 分別為1 和3。首先需要檢查每個單元是否都出現(xiàn)，如果存在未出現(xiàn)的單元C*，則隨機挑選出現(xiàn)次數(shù)最多的單元C∧位置，并將該位置的數(shù)值替換為C*，循環(huán)檢查直至每個單元都出現(xiàn)。然后判斷是否存在單元C◇出現(xiàn)的列數(shù)（即此單元中機器數(shù)量）大于U，如果存在則隨機挑選一個單元C◇，并將其位置數(shù)據(jù)替換為出現(xiàn)次數(shù)最少的單元數(shù)值，循環(huán)檢查直至其成為可行解。舉例如下：人工魚1 有鄰居2、3 和4得到的初始中心經(jīng)檢查知不是可行解，故根據(jù)上述規(guī)則，得到可行的聚群中心再根據(jù)得到的中心，即可以得到人工魚1 的聚群中心RΔ。

5.食物濃度：人工魚群算法中魚兒會趨向本水域中食物濃度最高的地方。在求解一個極大值問題時，人工魚所處的位置食物濃度越高則代表該解越理想。由于本模型需要求解的是一個極小值問題，所以需要將目標(biāo)函數(shù)的倒數(shù)作為食物濃度。

（三）人工魚群算法的主要算子

1.覓食。人工魚A 的位置為XA，當(dāng)前的狀態(tài)為FA（食物濃度）。為保證覓食后的人工魚依然為可行解，故隨機交換解1 中的基因m 次（m≤Visual 可保證人工魚是在其視野范圍內(nèi)進行覓食的）。如解1，Xlif=中的和交換得到，解2 同理進行交換得到，進而得到解3 為，則人工魚A 的位置變?yōu)椋錉顟B(tài)為。如果，則將XA替換成如果上述行為執(zhí)行了TryNum 次后依然沒有成功則執(zhí)行2.3.4 的隨機行為。

2.聚群。人工魚A 的聚群中心為RΔ，其狀態(tài)為FΔ。如果FΔ＞FA，表明中心RΔ的食物濃度更高，則將人工魚A 的位置替換為RΔ，否則執(zhí)行覓食行為。

3.追尾。針對人工魚A，探索其當(dāng)前所有鄰居中食物濃度最大的伙伴B。如果滿足FB＞FA，表明伙伴B 的周圍食物濃度更高，則將人工魚A 替換為人工魚B，否則執(zhí)行覓食行為。

4.隨機行為。如果某條人工魚覓食行為執(zhí)行失敗，則執(zhí)行隨機行為。隨機行為即在視野范圍內(nèi)，人工魚隨機挑選若干個位置進行隨機賦值。

5.公告板行為。各人工魚在自身尋優(yōu)活動結(jié)束后，自動與公告板上狀態(tài)進行比較，如果自身狀態(tài)優(yōu)于公告板狀態(tài)，則將公告板狀態(tài)替換為自身狀態(tài)，這樣可以使公告板狀態(tài)始終是歷史最優(yōu)。

（四）算法步驟

1.控制參數(shù)的設(shè)置，包括人工魚編號p、魚群規(guī)模Popsize、覓食行為執(zhí)行的最大次數(shù)TryNum、視野大小Visual、種群迭代計數(shù)器g、最大迭代次數(shù)GenNum。

2.根據(jù)上述編碼機制，進行人工魚群的隨機初始化，取優(yōu)值賦給公告板。

3.For g=1…GenNum

For p=1…Popsize

（a）第p 條人工魚進行覓食、聚群、追尾行為；p 自增1。

（b）執(zhí)行上述行為后，更新人工魚p 的狀態(tài)并與公告板進行比較，若優(yōu)于公告板則進行替換。

4.輸出公告板上的值，結(jié)束算法。

四、典型實驗分析

以某制造型企業(yè)為例，該企業(yè)擁有兩個異地制造工廠Q1和Q2，且兩個工廠都擁有3 個制造單元。該企業(yè)可以加工生產(chǎn)3 種產(chǎn)品，每種產(chǎn)品有4 道工序（安裝、拋光、打磨、組裝），對應(yīng)的加工機器也是4 種。每個制造單元最多可容納3 臺機器，最少擁有1 臺機器。原材料可以從附近的供應(yīng)商f1和f2處進購，固定進購成本分別為100和84。工廠l 的產(chǎn)品i 從供應(yīng)商f 處采購的單位成本如表1 所示。產(chǎn)品i 的工序j 在機器m上加工所需要的時間（tijm）如表2 所示。每臺機器固定使用成本（MFCm）以及單位時間使用成本（MVCm）如表3 所示。單個在制品從一個工廠運往另一個工廠的運費為80，單個在制品在工廠內(nèi)的單元之間移動成本為20。

表1 不同原材料的采購價格

表2 不同工序所需時間

表3 機器的固定使用成本和變動使用成本

采用Java 語言編程，IDE 為Intellij IDEA，控制參數(shù)中Popsize 取100，TryNum 取60，Visual 取16，GenNum 取60，經(jīng)過多次試驗，可以穩(wěn)定得到一個較優(yōu)的結(jié)果。

某次典型實驗的初始解如下，其目標(biāo)函數(shù)值為123 973。

該次實驗的最終解如下，其目標(biāo)函數(shù)值為33 115。這表明算法具有較強尋優(yōu)的能力。

該實驗中每次迭代公告板的目標(biāo)函數(shù)值如圖1 所示。

圖1 實驗收斂圖

五、結(jié)束語

本文將供應(yīng)鏈集成在單元制造系統(tǒng)中，一方面允許在制品在工廠之間產(chǎn)生物流以共享制造單元的產(chǎn)能，另一方面決策者可以自由決定從任一供應(yīng)商處進購原材料。該模型可以同時優(yōu)化生產(chǎn)設(shè)施配置和供應(yīng)商選擇過程，為供應(yīng)鏈中主要合作企業(yè)節(jié)省大量制造及采購成本。根據(jù)模型的特點，采用了改進的離散型人工魚群算法進行求解，所得最終解相對于隨機挑選的初始解得到很大的提升，表明該算法有較強的尋優(yōu)性能。人工魚的覓食行為奠定了算法收斂的基礎(chǔ)，聚群行為增強了算法收斂的穩(wěn)定性以及全局性，追尾行為則增強了算法收斂的快速性和全局性。未來還可以考慮勞動力的雇傭與配置，以及銷售市場對單元制造系統(tǒng)帶來的影響，使勞動密集型企業(yè)可以利用面向供應(yīng)鏈的單元制造系統(tǒng)更有效地組織資源進行生產(chǎn)。