柳春鋒，趙善林，王居鳳

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

一、引言

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

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

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

二、問(wèn)題描述以及模型建立

（一）問(wèn)題描述

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

（二）參數(shù)說(shuō)明

1.參數(shù)

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

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

NL：工廠數(shù)量；

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

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

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

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

j：工序的索引號(hào)（j=1，2，3，…，NO）；

m：機(jī)器類型的索引號(hào)（m=1，2，3，…，NM）；

l：工廠的索引號(hào)（l=1，2，3，…，NL）；

c：?jiǎn)卧乃饕?hào)（c=1，2，3，…，NC·NL）（將各工廠的單元累加后進(jìn)行編號(hào)）；

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

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

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

MFCm：每臺(tái)機(jī)器m 的固定使用成本；

MVCm：每臺(tái)機(jī)器m 的單位時(shí)間使用成本；

L：?jiǎn)卧獌?nèi)機(jī)器最少數(shù)量；

U：?jiǎn)卧獌?nèi)機(jī)器最多數(shù)量；

ISC：兩個(gè)工廠之間運(yùn)輸單個(gè)在制品的成本；

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

2.決策變量

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

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

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

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

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

三、離散型人工魚(yú)群算法

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

（一）人工魚(yú)編碼

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

上述矩陣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 中進(jìn)行。由此，單元3 內(nèi)必須有加工該工序的機(jī)器，從而對(duì)Ymlc初始化產(chǎn)生影響。

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

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

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

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

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

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

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

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

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

（三）人工魚(yú)群算法的主要算子

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

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

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

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

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

（四）算法步驟

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

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

3.For g=1…GenNum

For p=1…Popsize

（a）第p 條人工魚(yú)進(jìn)行覓食、聚群、追尾行為；p 自增1。

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

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

四、典型實(shí)驗(yàn)分析

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

表1 不同原材料的采購(gòu)價(jià)格

表2 不同工序所需時(shí)間

表3 機(jī)器的固定使用成本和變動(dòng)使用成本

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

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

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

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

圖1 實(shí)驗(yàn)收斂圖

五、結(jié)束語(yǔ)

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