柳春鋒 王 艷 王居鳳

1(杭州電子科技大學(xué)管理學(xué)院 浙江 杭州 310018) 2(中國計(jì)量大學(xué)信息與計(jì)算科學(xué)系 浙江 杭州 310018)

0 引 言

單元制造系統(tǒng)CMS(Cellular Manufacturing System)是一種基于成組技術(shù)GT(Group Technology)的混合系統(tǒng)。由于產(chǎn)品創(chuàng)新周期的縮短以及客戶需求的多樣化，CMS應(yīng)運(yùn)而生[1]。

近年來高鐵等制造業(yè)興起，其內(nèi)部原有的傳統(tǒng)制造系統(tǒng)反應(yīng)慢、適應(yīng)力差等特點(diǎn)造成生產(chǎn)管理上的困難，因此越來越多的制造業(yè)開始尋求靈活的單元制造方式來應(yīng)對難題[2]。此外，豐田采用的柔性單元制造系統(tǒng)，使其內(nèi)部各種形式的浪費(fèi)在一定程度上得以消除，并且形成一套標(biāo)準(zhǔn)的操作程序[3]。CMS適合生產(chǎn)多品種少批量的產(chǎn)品，并帶來可觀的效益，例如庫存成本的降低、交貨期的縮短以及靈活的設(shè)施布局等[4]。

研究表明，物料搬運(yùn)費(fèi)用在生產(chǎn)經(jīng)營活動(dòng)總開銷中的比例高達(dá)20%～50%[5]。合理的單元構(gòu)建可以大幅度地減少生產(chǎn)中的物流成本。另外，學(xué)習(xí)效應(yīng)的存在使得員工實(shí)際生產(chǎn)時(shí)間變得難以估計(jì)，因而對生產(chǎn)成本的核算也非常困難。

Koulamas等[6]提出了廣義的學(xué)習(xí)效應(yīng)概念，構(gòu)建了與工件加工時(shí)間之和有關(guān)的學(xué)習(xí)模型。Liu等[7]在分析動(dòng)態(tài)單元制造系統(tǒng)中員工學(xué)習(xí)遺忘效應(yīng)的基礎(chǔ)上提出了人員分配和生產(chǎn)計(jì)劃的綜合決策模型。Toksar等[8]研究了一種基于位置依賴的具有模糊學(xué)習(xí)效果的單機(jī)調(diào)度問題，建立了模糊混合整數(shù)非線性規(guī)劃模型，目標(biāo)是最小化最大完工時(shí)間、總完工時(shí)間和總加權(quán)完工時(shí)間。

Hazarika等[9]提出了一種啟發(fā)式遺傳算法來優(yōu)化單元構(gòu)建中的產(chǎn)品加工路徑，從而最小化單元間物流成本。Soto等[10]設(shè)計(jì)了一種帝國主義競爭算法來解決單元間物流成本的最小化。Bychkov等[11]研究了單元化制造模式下產(chǎn)品在單元間移動(dòng)的物流成本優(yōu)化問題，并構(gòu)建了一種新的混合整數(shù)線性規(guī)劃模型。Aalaei等[12]提出了單元制造系統(tǒng)中產(chǎn)品庫存成本與員工總工資的優(yōu)化模型與方法。

雖然以往學(xué)者從不同視角研究了員工學(xué)習(xí)或產(chǎn)品物流，但同時(shí)考慮學(xué)習(xí)效應(yīng)與物流因素的單元化制造文獻(xiàn)還較罕見，而且員工學(xué)習(xí)因素對產(chǎn)品轉(zhuǎn)移的影響還有待進(jìn)一步深入探討。

因此，本文試圖構(gòu)建一個(gè)集成員工學(xué)習(xí)效應(yīng)與產(chǎn)品物流的單元化制造優(yōu)化模型。目標(biāo)是使產(chǎn)品的庫存成本、延期交貨成本以及產(chǎn)品物流成本在合理的人員分配、最佳產(chǎn)品路線下達(dá)到最小值。同時(shí)，為解決這個(gè)復(fù)雜的問題，設(shè)計(jì)遺傳算法來尋找模型的最優(yōu)解。

1 問題假設(shè)與描述

本文研究的優(yōu)化問題基于以下假設(shè)：

(1) 生產(chǎn)計(jì)劃假設(shè)：研究單周期多單元的生產(chǎn)系統(tǒng)，且認(rèn)為設(shè)備在生產(chǎn)過程中不會(huì)發(fā)生故障。各種產(chǎn)品的市場需求在計(jì)劃生產(chǎn)期內(nèi)可確定，并可按需求數(shù)量在各單元內(nèi)進(jìn)行流水線生產(chǎn)。

(2) 單元假設(shè)：單元數(shù)與產(chǎn)品類型數(shù)相同，且各單元內(nèi)工序數(shù)量相同，不同單元的相同的對應(yīng)位置具有相同的功能。

(3) 處理時(shí)間假設(shè)：由于設(shè)備新舊版本、產(chǎn)品復(fù)雜度、以及員工工作與學(xué)習(xí)能力的差異，導(dǎo)致員工處理各任務(wù)的時(shí)間不同。

(4) 物流成本假設(shè)：生產(chǎn)過程中允許產(chǎn)品(在制品)在單元間進(jìn)行移動(dòng)，同種產(chǎn)品在單元間的單位物流成本相同，不同產(chǎn)品的單位物流成本不同；單元內(nèi)發(fā)生的移動(dòng)成本可忽略不計(jì)。

單元制造系統(tǒng)優(yōu)化問題的描述如下：假設(shè)由P位多技能員工在C個(gè)單元中處理Q類產(chǎn)品，每個(gè)單元均包含J個(gè)工序。

如圖1所示，假設(shè)產(chǎn)品1有兩條備選生產(chǎn)路線，路線一：C11→C12→C13→C14；路線二：C11→C12→C23→C14。路線一的物流成本為零；假設(shè)路線二中C23位置的設(shè)備比C13版本更高，處理時(shí)間會(huì)小于同功能的C13，因此路線二的總處理時(shí)間小于路線一，但產(chǎn)品在單元間發(fā)生了兩次移動(dòng)，產(chǎn)生了物流成本。

圖1 生產(chǎn)流程圖

通常工人在一開始不熟悉任務(wù)的生產(chǎn)運(yùn)作，隨著員工加工同一類產(chǎn)品數(shù)量的增加，員工的學(xué)習(xí)效應(yīng)使加工每件同類產(chǎn)品的時(shí)間越來越短。不過，加工時(shí)間也會(huì)由于工人技能提升的邊際效應(yīng)逐漸趨向一個(gè)穩(wěn)定值。

企業(yè)管理者需要通過對員工、產(chǎn)品和機(jī)器的合理匹配，以及對最優(yōu)生產(chǎn)路線的確定，達(dá)到庫存成本、延期交貨成本以及物流成本的最小化。

2 模型建立

2.1 參數(shù)介紹

(1) 輸入?yún)?shù)：

P：員工總數(shù)，p表示員工索引(p=1,2,…,P)；

Q：產(chǎn)品類型總數(shù)，q代表產(chǎn)品索引(q=1,2,…,Q)；

M：機(jī)器設(shè)備總數(shù)，m代表機(jī)器索引(m=1,2,…,M)；

dq：產(chǎn)品q的生產(chǎn)期限；

Nq：產(chǎn)品q的市場需求或生產(chǎn)量；

J：各單元中工序數(shù)量，j表示工序的索引(j=1,2,…,J)；

C：單元總數(shù)量，c代表單元的索引(c=1,2,…,C)；

θq：產(chǎn)品q的單位時(shí)間延期成本；

φq：產(chǎn)品q的單位時(shí)間庫存成本；

Lq：產(chǎn)品q在單元間的單位物流成本。

(2) 決策變量：

Xpcj：若員工p被分配到單元c的第j道工序，則Xpcj=1，否則為0；

Yqcj：若產(chǎn)品q被分配到單元c的第j道工序，則Yqcj=1，否則為0。

2.2 單元化制造中的學(xué)習(xí)效應(yīng)

根據(jù)單元化制造特征，員工學(xué)習(xí)效應(yīng)可采用以下改進(jìn)模型[6]。

考慮學(xué)習(xí)效應(yīng)時(shí)員工p在單元c的第j道工序?qū)Φ趎件產(chǎn)品q的實(shí)際處理時(shí)間Spqncj：

Spqncj=tqcj·max{f(p,q,n,mcj),hq}

(1)

f(p,q,n,mcj)=[1+(n-1)(1-βq)epmcj]α

(2)

模型中涉及的參數(shù)：

(1)f(p,q,n,mcj)：學(xué)習(xí)效應(yīng)系數(shù)函數(shù)，取值范圍為(0,1]，n指產(chǎn)品q加工件數(shù)的索引；

(2)ep：與員工學(xué)習(xí)能力相關(guān)的學(xué)習(xí)效應(yīng)因子，ep值越大員工的學(xué)習(xí)能力越強(qiáng)，0.75≤ep≤0.95；

(3)βq：產(chǎn)品類型q的復(fù)雜度，βq值越大產(chǎn)品越復(fù)雜，0<βq<1；

(4)mcj：在單元c的第j道工序上機(jī)器的能力系數(shù)，mcj值越大機(jī)器版本越高，機(jī)器效率越高，0

(5)α：與加工時(shí)間相關(guān)的學(xué)習(xí)效應(yīng)因子，α≤0；

(6)hq：截?cái)鄥?shù)，即考慮學(xué)習(xí)效應(yīng)后員工在處理產(chǎn)品q時(shí)，隨著生產(chǎn)產(chǎn)品件數(shù)的增加，員工處理每件產(chǎn)品的時(shí)間會(huì)慢慢趨于一個(gè)穩(wěn)定值hq，0

(7)tqcj：產(chǎn)品q在單元c的第j道工序的標(biāo)準(zhǔn)處理時(shí)間。

學(xué)習(xí)效應(yīng)函數(shù)圖像是一條緩慢下降的曲線。例如，對于q=1，c=1，j=1，為參數(shù)賦值：t111=22.20，N1=2 100，β1=0.5，e1=0.943，α=-0.11，h1=0.5，m11=0.26，可得如圖2所示的學(xué)習(xí)效應(yīng)曲線。

隨著產(chǎn)品的持續(xù)生產(chǎn)，最終生產(chǎn)一件產(chǎn)品的時(shí)間取決于該產(chǎn)品瓶頸工序的處理時(shí)間，產(chǎn)品在瓶頸工序的移動(dòng)也會(huì)對生產(chǎn)運(yùn)作產(chǎn)生重要影響。

2.3 目標(biāo)函數(shù)與約束條件

考慮員工學(xué)習(xí)效應(yīng)以及產(chǎn)品物流構(gòu)建一個(gè)生產(chǎn)模型，目標(biāo)函數(shù)為最小化庫存成本與延期成本，以及物流成本：

MinC=ω1+ω2

(3)

(1) 第一部分：ω1為考慮員工學(xué)習(xí)效應(yīng)對實(shí)際完工時(shí)間影響后的庫存成本與延期交貨成本。

(2) 第二部分：ω2為產(chǎn)品在單元間的物流成本。

式中：|Yqcj-Yqc(j+1)|表示同一產(chǎn)品的相鄰工序在單元間是否發(fā)生了移動(dòng)。

約束條件：

?q,n

(4)

(5)

(6)

Xpcj,Yqcj∈{0,1} ?p,q,c,j

(7)

約束式(4)對于給定的第n件產(chǎn)品q確定了瓶頸工序位于單元c*的第j*道工序；約束式(5)確保各單元的各工序只分配一個(gè)員工；約束式(6)確保各單元的各工序只處理一類產(chǎn)品；約束式(7)規(guī)定了決策變量Xpcj和Yqcj為二元變量。

3 遺傳算法與實(shí)驗(yàn)

遺傳算法是一種基于生物進(jìn)化理論發(fā)展起來的高效的搜索與優(yōu)化方法，能自動(dòng)獲取和引導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向。它通過一定的編碼方式，將問題中的各類信息轉(zhuǎn)化為一條特定的染色體，反復(fù)搜索得到最優(yōu)染色體，即所求優(yōu)化問題的解[13]。下面結(jié)合實(shí)例說明算法的有效性和模型的合理性。

3.1 實(shí)例描述

以某光纖連接器制造企業(yè)為例，制造系統(tǒng)中有6個(gè)直線型制造單元，各單元有6臺(tái)不可移動(dòng)的生產(chǎn)設(shè)備(安裝、拋光、組裝、表面檢查、光學(xué)檢查、以及包裝設(shè)備)。共有6類產(chǎn)品(FC、SC、MT-RJ、LC、MU、及MC型)需要生產(chǎn)，每單元生產(chǎn)一類產(chǎn)品；有36位多技能員工，每臺(tái)機(jī)器分配一個(gè)員工，各單元的各工序只處理一類產(chǎn)品(即C=Q=J=6,P=36)。令tqcj∈[0.01，99.99]，由于tqcj的取值與產(chǎn)品、工序和單元有關(guān)，因此共取6×6×6個(gè)隨機(jī)值。按照學(xué)習(xí)效應(yīng)式(1)和式(2)可進(jìn)一步求出產(chǎn)品的實(shí)際處理時(shí)間Spqncj。另外，α取-0.11，其他參數(shù)賦值見表1和表2。

表1 與學(xué)習(xí)效應(yīng)函數(shù)相關(guān)的參數(shù)(1)

表2 與學(xué)習(xí)效應(yīng)函數(shù)相關(guān)的參數(shù)(2)

對部分參數(shù)特殊化處理來體現(xiàn)算法的有效性。首先，對于表1中產(chǎn)品1，將N1、θ1及L1設(shè)置得較其他產(chǎn)品低，而d1和φ1較其他產(chǎn)品高，屬于非加急產(chǎn)品；對于產(chǎn)品6而言，參數(shù)設(shè)置與產(chǎn)品1相反，屬于加急產(chǎn)品。其次，表2中對角線位置的機(jī)器設(shè)置為低效機(jī)器，即能力系數(shù)較低(下劃線已標(biāo)出)。

3.2 遺傳算法

(1) 染色體編碼：考慮到構(gòu)建的模型由兩部分目標(biāo)函數(shù)組成，所以解的結(jié)構(gòu)(即染色體)設(shè)計(jì)為二維結(jié)構(gòu)[7]，即解的結(jié)構(gòu)由解一和解二組成。解一輸出36個(gè)員工在36臺(tái)機(jī)器上的分配情況，形狀為6×6的矩陣，如圖3所示。為了簡化，將解一每行首尾相接組成一條數(shù)字串編碼，如圖4所示。

圖3 解一染色體的組成

25306…172433

圖4 解一染色體變體

解二輸出6類產(chǎn)品生產(chǎn)路徑，如圖5所示。

圖5 解二染色體的組成

解二的形狀是一個(gè)長方體。共有6個(gè)縱截面，每個(gè)縱截面表示每類產(chǎn)品的生產(chǎn)路徑信息。為了簡潔，解二用6×6的簡易矩陣表示，如圖6所示。

圖6 解二的簡易矩陣表示

圖6的矩陣中行和列分別代表單元、工序，矩陣?yán)锏臄?shù)字代表產(chǎn)品類型。比如“6”表示在第3單元的第4道工序生產(chǎn)產(chǎn)品6。

(2) 初始種群的生成:根據(jù)設(shè)定的參數(shù)，采用隨機(jī)產(chǎn)生染色體的方法構(gòu)造初始種群。通過預(yù)實(shí)驗(yàn)設(shè)定初始種群數(shù)Nind=200。

(3) 適應(yīng)度計(jì)算:種群中個(gè)體的適應(yīng)度表明其優(yōu)劣性，某個(gè)體x的適應(yīng)度fx為：

(8)

式中：ξx為個(gè)體x的目標(biāo)函數(shù)值；ξmax、ξmin分別為種群中個(gè)體目標(biāo)函數(shù)的最大值、最小值；ε為一個(gè)很小的正數(shù)。

(4) 選擇:采用輪盤賭選擇[15]方法。生成一個(gè)輪盤，輪盤每個(gè)區(qū)的角度與個(gè)體的適應(yīng)度成正比。產(chǎn)生一個(gè)隨機(jī)數(shù)，它落入轉(zhuǎn)盤的哪個(gè)區(qū)域就選擇相應(yīng)的個(gè)體。個(gè)體的適應(yīng)度越高，被選擇的概率就越大。按此法從種群中選出90%的個(gè)體進(jìn)行交叉和變異。

(5) 交叉:將選擇出來的個(gè)體兩兩之間進(jìn)行交叉，交叉概率為0.8。解一和解二的交叉規(guī)則如下：

① 解一的交叉規(guī)則采用部分匹配交叉法：分別在兩條直線數(shù)字串中相同位置取兩點(diǎn)，并將兩點(diǎn)中間的基因進(jìn)行交叉變換，如圖7所示。

圖7 解一交叉示意圖

② 解二交叉規(guī)則為：將兩條染色體中的解二部分分別切成左右兩半，將父代1的左側(cè)與父代2的右側(cè)、父代1的右側(cè)與父代2的左側(cè)重新組合成新的子代1和子代2。圖8展示了子代1的生成。

圖8 解二交叉示意圖

(6) 變異:基因變異方法為：從種群中依次取一條染色體，以變異概率0.4對該染色體上部分編碼按照一定的規(guī)則進(jìn)行改變。變異規(guī)則如下：

解一遵循逆向排序法(Reverse Sorting)。任取染色體上兩點(diǎn)，將它們之間的基因逆向排序，如圖9所示。

圖9 解一變異示意圖

解二變異規(guī)則為：任取一個(gè)平面，在平面的水平和豎直方向各取兩個(gè)點(diǎn)，獲得一個(gè)區(qū)域(如圖10中虛線框)，區(qū)域內(nèi)以行為單位，將所有行逆向交換順序，如圖10所示。

(a) 變異前

(7) 插入算子：每次進(jìn)行完交叉、變異之后，將上一代中10%的最優(yōu)個(gè)體復(fù)制插入到下一代，以保證每代種群中個(gè)體總數(shù)不變。

(8) 終止條件：通過多次測試，迭代次數(shù)MaxGen=400時(shí)最終結(jié)果可趨于穩(wěn)定，以此值作為最大迭代次數(shù)來終止運(yùn)算[14]。

3.3 實(shí)例結(jié)果

運(yùn)用MATLAB編寫算法程序，最終得出的目標(biāo)函數(shù)收斂情況如圖11所示。

可以看出，該遺傳算法在第369次迭代時(shí)收斂于最優(yōu)解或近似最優(yōu)解。此時(shí)員工與機(jī)器匹配情況、各產(chǎn)品生產(chǎn)路線簡易矩陣表示如圖12和圖13所示。可以看出，生產(chǎn)非加急產(chǎn)品1時(shí)，選擇在對角線低效機(jī)器加工(圖13中虛線路線)；而生產(chǎn)加急產(chǎn)品6時(shí)，則避開對角線的低效機(jī)器、在單元間不斷轉(zhuǎn)移(產(chǎn)生物流)并選擇在高效機(jī)器上加工(圖13中實(shí)線路線)。此結(jié)果說明了算法的有效性。

圖12 員工與機(jī)器匹配矩陣

圖13 產(chǎn)品生產(chǎn)路線簡易矩陣

3.4 數(shù)值實(shí)驗(yàn)

為了進(jìn)一步說明模型的合理性，即檢驗(yàn)對產(chǎn)品物流進(jìn)行研究的必要性，分別嘗試不同參數(shù)設(shè)置情況下產(chǎn)品存在物流與無物流時(shí)運(yùn)作成本的比較，具體情況如表3-表7所示。在表5-表7中，N1=1.2a,N2=1.8a,N3=1.8a,N4=2.0a,N5=1.9a,N6=2.1a,a=1.0×10e。

表3 不同C有無物流的成本比較(J=6,N1=1 200,N2=N3=1 800,N4=2 000,N5=1 900,N6=2 100)

表4 不同J有無物流的成本比較(C=6,N1=1 200,N2=N3=1 800,N4=2 000,N5=1 900,N6=2 100)

表5 不同Nq有無物流的成本比較(C=6,J=6)e=2時(shí)的成本比較 %

表6 e=3時(shí)的成本比較 %

表7 e=4時(shí)的成本比較 %

dq、θq、φq、Lq以及tqcj在合理范圍內(nèi)隨機(jī)取值(本例中dq∈[8 000,13 000],θq∈[6,40],φq∈[6,24],Lq∈[0.4,1.2]，tqcj∈[0.01,99.99])；ep、βq、mcj以及hq在各自定義范圍內(nèi)隨機(jī)取值；α取-1。

表3中固定J和Nq值，改變C值，針對每個(gè)C值隨機(jī)生成10個(gè)實(shí)例，求出它們目標(biāo)函數(shù)的最小值MIN、最大值MAX和平均值A(chǔ)VE。通過比較有物流與無物流情形下的平均值，計(jì)算成本下降百分比。表4中固定C和Nq值，改變J值。表5中固定C和J值，改變Nq值。從以上三種情況可以看出，成本下降百分比可達(dá)11.66%～35.39%，即在增大單元、工序規(guī)模以及擴(kuò)大生產(chǎn)量的情況下，產(chǎn)品存在物流總比無物流的運(yùn)作成本低。此結(jié)果說明了模型中討論物流因素的重要價(jià)值。

4 結(jié) 語

本文研究了在單元制造系統(tǒng)中對員工與機(jī)器進(jìn)行配置從而生產(chǎn)多類型產(chǎn)品的優(yōu)化問題。多技能員工的學(xué)習(xí)效應(yīng)使加工每件同類產(chǎn)品的時(shí)間逐步縮短并趨向穩(wěn)定值，因此員工與機(jī)器匹配的復(fù)雜度大大增加。由于允許產(chǎn)品在單元間移動(dòng)及同功能機(jī)器的效率差異，使得生產(chǎn)路線對各瓶頸工序的生產(chǎn)時(shí)間產(chǎn)生重要影響。以庫存成本、延期交貨成本和物流成本最小化為目標(biāo)，對該問題建立了0-1非線性規(guī)劃模型，設(shè)計(jì)遺傳算法得出合理的人員機(jī)器配置方案以及各產(chǎn)品的最優(yōu)生產(chǎn)路線。典型實(shí)例顯示，生產(chǎn)加急產(chǎn)品時(shí)，該算法可使產(chǎn)品在單元間不斷轉(zhuǎn)移并選擇在高效機(jī)器上加工。大量隨機(jī)數(shù)值實(shí)驗(yàn)也表明，在不同生產(chǎn)規(guī)模的單元化制造實(shí)踐中，構(gòu)建合理的單元間產(chǎn)品物流對于有效降低運(yùn)作成本具有重要的現(xiàn)實(shí)意義。

本研究還可從以下方面做進(jìn)一步探索。首先，可針對工業(yè)互聯(lián)網(wǎng)環(huán)境下，考慮設(shè)備移動(dòng)、租賃及共享等因素對單元制造系統(tǒng)資源配置的影響進(jìn)行研究；其次，可將單周期生產(chǎn)情況拓展至多周期；最后，可設(shè)計(jì)有效的啟發(fā)式算法，以改善遺傳算法初始種群的質(zhì)量，實(shí)現(xiàn)快速收斂，這對于工業(yè)級(jí)的大規(guī)模問題而言也有重要的研究價(jià)值。