馮定忠，吳 雄，丁楊科，范佳靜，何瀟楚，王 成

(1.浙江工業(yè)大學(xué) 機(jī)械工程學(xué)院，浙江 杭州 310014；2.浙江科技學(xué)院 經(jīng)濟(jì)與管理學(xué)院，浙江 杭州 310023)

基于U型布局制造單元的構(gòu)建研究

馮定忠1，吳 雄1，丁楊科1，范佳靜2，何瀟楚1，王 成1

(1.浙江工業(yè)大學(xué) 機(jī)械工程學(xué)院，浙江 杭州 310014；2.浙江科技學(xué)院 經(jīng)濟(jì)與管理學(xué)院，浙江 杭州 310023)

單元制造技術(shù)能夠?qū)⒋笈恐圃斓慕?jīng)濟(jì)性與中小批量制造的靈活性進(jìn)行有效結(jié)合，受到現(xiàn)代制造業(yè)的高度關(guān)注與應(yīng)用.以單元構(gòu)建問題為研究對(duì)象，針對(duì)U型布局這一單元制造系統(tǒng)的特殊形式，綜合考慮可選擇的工藝路徑、相應(yīng)工序的加工時(shí)間、設(shè)備的種類、加工能力、設(shè)備形狀大小、設(shè)備之間和單元之間的距離、搬運(yùn)工具的搬運(yùn)批量及費(fèi)用等信息，通過數(shù)學(xué)規(guī)劃法，以單元內(nèi)和單元間總的物流費(fèi)用最小和設(shè)備負(fù)荷差懲罰成本最小為目標(biāo)函數(shù)，建立單元構(gòu)建數(shù)學(xué)模型，進(jìn)而應(yīng)用遺傳算法，通過數(shù)值案例對(duì)單元構(gòu)建的數(shù)學(xué)模型進(jìn)行求解，得出最優(yōu)單元?jiǎng)澐址桨讣捌渑苛慵鄳?yīng)的最優(yōu)加工方案.

單元制造系統(tǒng)；單元構(gòu)建；U型布局；數(shù)學(xué)規(guī)劃法；遺傳算法

單元構(gòu)建是單元制造實(shí)施過程中首先要面對(duì)和解決的問題.它可以被定義為：在已知所要加工零件/產(chǎn)品的基本信息(包括數(shù)量、類型、工藝路徑等)、設(shè)備的基本信息(包括種類、數(shù)量、生產(chǎn)能力等)以及設(shè)備與零件/產(chǎn)品之間的相關(guān)性的基礎(chǔ)上，構(gòu)建產(chǎn)品/零件族和設(shè)備單元[1].單元構(gòu)建的方法主要有直觀法、可視化編碼法、相似系數(shù)法、業(yè)務(wù)流程重組法、聚類分析法、數(shù)學(xué)規(guī)劃法、圖論法和人工智能法等[2-5].

單元構(gòu)建需要滿足兩個(gè)要求：緊湊和獨(dú)立.緊湊的單元是指單元內(nèi)包括的設(shè)備少且設(shè)備之間的距離設(shè)置合理，從而減少單元內(nèi)物料流動(dòng)(搬運(yùn))的平均距離，降低搬運(yùn)成本；獨(dú)立的單元是指使零件的整個(gè)加工過程盡量在一個(gè)單元內(nèi)完成，減少零件在單元之間的流動(dòng)次數(shù).單元的緊湊性與獨(dú)立性之間是矛盾的，兩者之間是既相互對(duì)立又相互統(tǒng)一的關(guān)系.緊湊的單元相對(duì)而言設(shè)備數(shù)量較少，勢(shì)必會(huì)出現(xiàn)物料在單元間的移動(dòng)，反之亦然.實(shí)行單元制造方式，可將具有相同加工工藝的產(chǎn)品/零件配置在同一單元加工，能有效減少物料的搬運(yùn)距離及成本，但是考慮到單元緊湊性問題，又可能會(huì)增加單元間的物料搬運(yùn)，Vahid[6]所提的多周期單元構(gòu)建模型就特別強(qiáng)調(diào)物料在單元內(nèi)和單元間的平均移動(dòng)距離.U型布局一直是精益生產(chǎn)所倡導(dǎo)的生產(chǎn)布局形式，相對(duì)于傳統(tǒng)的直線型布局而言，它能夠在一定程度上滿足單元的緊湊及獨(dú)立的要求，本研究針對(duì)U型布局的制造系統(tǒng)，應(yīng)用數(shù)學(xué)規(guī)劃方法研究單元構(gòu)建問題.

1 單元構(gòu)建問題描述

在單元運(yùn)作中，零件作業(yè)等待時(shí)間主要取決于單元內(nèi)各設(shè)備的負(fù)荷均衡性(Machineworkloadbalancing).單元內(nèi)設(shè)備的均衡性越大，則整個(gè)生產(chǎn)過程越流暢，零件的作業(yè)等待時(shí)間就越短，生產(chǎn)效率越高；相反，如果設(shè)備的均衡性很差，那就會(huì)出現(xiàn)零件在一臺(tái)設(shè)備上加工完后，在下一臺(tái)設(shè)備上加工前會(huì)有很長(zhǎng)的時(shí)間處于排隊(duì)等待狀態(tài)，這不僅增加了大量的等待時(shí)間，降低了其他設(shè)備的利用率，還會(huì)造成很高的在制品庫存成本，降低產(chǎn)品的整體產(chǎn)量和生產(chǎn)效率.因此單元設(shè)備負(fù)荷的均衡性是單元構(gòu)建的主要指標(biāo)之一.

以U型布局的制造系統(tǒng)作為研究對(duì)象，基于零件的類別、需求信息、可選擇的工藝路徑、相應(yīng)工序的加工時(shí)間、設(shè)備的種類、加工能力、設(shè)備形狀大小、設(shè)備之間和單元之間的距離、搬運(yùn)工具的搬運(yùn)批量及費(fèi)用等信息，在總的物流費(fèi)用最少，單元內(nèi)設(shè)備負(fù)荷差懲罰成本最小的目標(biāo)下，研究確定最優(yōu)的設(shè)備/零件分組、設(shè)備布局以及各工藝路徑下相應(yīng)零件的加工數(shù)量.為此，可將單元構(gòu)建問題進(jìn)一步描述如下：

1) 每種零件有多條生產(chǎn)路徑，且每條生產(chǎn)路徑所需要的設(shè)備是已知的，零件最終只能選擇一種加工工藝路線.

2) 每種零件的需求量都是已知的，且每種零件均按照一定的批量進(jìn)行搬運(yùn).

3) 每種設(shè)備的臺(tái)數(shù)均為一臺(tái)，且每臺(tái)設(shè)備的工作時(shí)間已知.

4) 單元內(nèi)的設(shè)備采用U型布局且限制為單一物流方向，即逆時(shí)針方向，如圖1所示.

圖1 設(shè)備的U型布局示意圖Fig.1 The schematic diagram of U-shaped layout of equipments

5) 每臺(tái)設(shè)備視為規(guī)格統(tǒng)一的矩形，設(shè)備的出口和入口視為同一位置，且每臺(tái)設(shè)備之間的距離是已知的.

6) 每個(gè)單元之間的搬運(yùn)距離d(c,c')是已知的，且單元間的搬運(yùn)距離大于單元內(nèi)搬運(yùn)距離.

7) 設(shè)備只能放在單元內(nèi)某個(gè)固定的位置，且同一個(gè)位置上只能放置一臺(tái)設(shè)備.

8) 每種零件在對(duì)應(yīng)設(shè)備上加工所需的時(shí)間是已知的.

9) 每臺(tái)設(shè)備在一定時(shí)期內(nèi)的可用工作時(shí)間和其利用率是已知的.

2 單元構(gòu)建數(shù)學(xué)模型

在構(gòu)建單元規(guī)劃的數(shù)學(xué)模型時(shí)，需要綜合考慮到總的物流費(fèi)用和單元的設(shè)備負(fù)荷均衡性，但這兩者之間的單位量綱不同.因此，在考慮單元設(shè)備負(fù)荷差的合理范圍的情況下，加入懲罰成本，當(dāng)設(shè)備與單元內(nèi)平均負(fù)荷相差過大時(shí)，就給予一定的懲罰，從而要求單元內(nèi)的設(shè)備負(fù)荷盡量滿足要求，同時(shí)也使得這些目標(biāo)能匹配到同一個(gè)目標(biāo)函數(shù)之下.單元構(gòu)建目標(biāo)函數(shù)最終考慮的是總的物流費(fèi)用和總的負(fù)荷差懲罰成本，目標(biāo)函數(shù)越小，說明單元?jiǎng)澐衷絻?yōu)，所以單元構(gòu)建的目標(biāo)函數(shù)可以表述為

minZ=αCra+βCer+γCC=

(1)

其中

(2)

(3)

權(quán)重系數(shù)α，β，γ應(yīng)滿足

α+β+γ=1 0<α<1,0<β<1,0<γ<1

(4)

約束條件為

(5)

(6)

(7)

(8)

xjc,xjp,xir=0 or 1,?i,j,r

(9)

式(5～9)中：式(5)表示每臺(tái)設(shè)備只能放在一個(gè)單元內(nèi)和每臺(tái)設(shè)備只能放在相應(yīng)的一個(gè)位置；式(6)表示每種零件只能選擇一條工藝路徑進(jìn)行加工和任何單元的任何位置只能放置一臺(tái)設(shè)備；式(7)對(duì)所構(gòu)建的單元規(guī)模做了限制，即單元內(nèi)不能沒有設(shè)備但是設(shè)備數(shù)量也不能超過單元內(nèi)的位置數(shù)；式(8)為單元內(nèi)設(shè)備的負(fù)荷確定了上限，即單元內(nèi)任何設(shè)備在加工期內(nèi)的負(fù)荷都不能超過該時(shí)期內(nèi)設(shè)備能提供的有效工作時(shí)間；式(9)表示變量的取值范圍.

3 基于遺傳算法的模型求解與案例分析

遺傳算法(Genetic algorithm)[7]是一種模擬生物進(jìn)化論中的自然選擇過程和遺傳學(xué)中的生物進(jìn)化過程的計(jì)算模型，它通過模擬自然界的進(jìn)化過程來尋找問題的最優(yōu)解.Hsu等[8]與Fan[9]等不少學(xué)者將遺傳算法引入到求解制造單元構(gòu)建的問題中并取得了良好的效果.

針對(duì)所研究的U型布局單元構(gòu)建問題，現(xiàn)結(jié)合數(shù)值案例(表1)，將遺傳算法應(yīng)用于該類問題的求解.表1中M表示設(shè)備，R表示零件，共有12臺(tái)設(shè)備來加工10種零件，R1-1表示第一種零件R1的第一條加工路徑，100/25表示加工批量為100，單次搬運(yùn)批量為25，對(duì)應(yīng)單元格中的數(shù)字3(2)表示零件在該加工路徑下，在這臺(tái)設(shè)備上的加工順序，括號(hào)中的數(shù)字為對(duì)應(yīng)的加工時(shí)間.

表1 多工藝路徑下的零件-設(shè)備加工順序(時(shí)間)相關(guān)信息

遺傳算法求解過程如下：

1)染色體編碼

根據(jù)以上單元構(gòu)建問題的數(shù)學(xué)模型，染色體中必須包含兩類信息，即零件工藝路徑的選擇信息xir(哪個(gè)零件選擇哪條工藝路徑)和設(shè)備位置分配信息xjcp(哪個(gè)設(shè)備放置在哪個(gè)單元的哪個(gè)位置).由于設(shè)備位置分配信息的確定是要在設(shè)備確定分到某個(gè)單元之后才能進(jìn)行，為了方便后面遺傳算法的計(jì)算，將變量xjc和xjp合并為xjcp進(jìn)行染色體編碼，并通過一個(gè)二維數(shù)組來表示，由此可以構(gòu)成如圖2所示的染色體組合.

圖2 染色體表達(dá)示意圖Fig.2 The schematic diagram of chromosomes representation

圖2中：R1=1表示第一種零件選擇第一條加工工藝進(jìn)行加工；M1=(3,2)表示設(shè)備M1放置在第三個(gè)單元的位置2上.

2)初始種群的產(chǎn)生

全局隨機(jī)產(chǎn)生初始種群P1,P2,…,Pm，初始種群的規(guī)模初步設(shè)定為m=100，初始的進(jìn)化代數(shù)K=0，前代最大的適應(yīng)度值PFmax=0，取最大迭代次數(shù)Kmax=500.

3)適應(yīng)度值計(jì)算

根據(jù)單元構(gòu)建問題模型的特點(diǎn)可知，每個(gè)個(gè)體代入目標(biāo)函數(shù)后得到的值均為非負(fù)值，因此在這里采用倒數(shù)的形式對(duì)目標(biāo)函數(shù)進(jìn)行轉(zhuǎn)換，其表達(dá)式為

(10)

如果直接取倒數(shù)，適應(yīng)度值會(huì)較小，因此取原目標(biāo)函數(shù)倒數(shù)的100倍作為轉(zhuǎn)換后的目標(biāo)函數(shù).

4)選擇操作

使用“最佳個(gè)體保留法”和“輪盤賭法”相結(jié)合的方法進(jìn)行選擇操作.最佳個(gè)體保留數(shù)占種群比例的8%，即適應(yīng)度值最大的8%的個(gè)體將被保留至下一代，其余的92%由“輪盤賭法”選擇產(chǎn)生.

5)交叉操作

這里先設(shè)定交叉概率Pc=20%，表示在交配池中的父代個(gè)體在平均水平上有20%的個(gè)體將進(jìn)行染色體交叉.為了保證交叉過程中產(chǎn)生的個(gè)體仍然滿足模型約束，所以針對(duì)位置擺放這一部分的染色體不進(jìn)行交叉，而只對(duì)路徑選擇的染色體部分進(jìn)行單點(diǎn)交叉操作，如圖3所示.

圖3 染色體交叉示意圖Fig.3 The schematic diagram of chromosomes chiasma

6)變異操作

對(duì)于種群中個(gè)體基因的變異操作雖然也是隨機(jī)進(jìn)行的，但是與交叉操作是隨機(jī)選擇個(gè)體不同，變異操作是隨機(jī)選擇基因來進(jìn)行的.

對(duì)于染色體中第一部分的路徑選擇信息，通過改變基因上的數(shù)字來進(jìn)行變異，數(shù)字的變化范圍為該基因位上的路徑選擇范圍，變異點(diǎn)的隨機(jī)取值范圍為[1,I]，如圖4所示.

圖4 路徑選擇信息變異示意圖Fig.4 The schematic diagram of information variation in routing selection

對(duì)于設(shè)備位置分配信息，采用逆轉(zhuǎn)變異算子來進(jìn)行變異.首先隨機(jī)選擇兩個(gè)逆轉(zhuǎn)點(diǎn)，再把這兩個(gè)逆轉(zhuǎn)點(diǎn)上的基因進(jìn)行互換，從而實(shí)現(xiàn)變異，見圖5.

7)循環(huán)終止

循環(huán)執(zhí)行步驟4～6)，當(dāng)進(jìn)化周期數(shù)K大于種群最大進(jìn)化周期數(shù)Kmax時(shí)，算法終止，跳出循環(huán).

8)解 碼

對(duì)種群中輸出的最優(yōu)解進(jìn)行解碼，則可以得到零件和設(shè)備的分配方案.

在該案例中，最大迭代次數(shù)Kmax=500，交叉概率Pc=20%，變異概率Pm=0.01，最佳個(gè)體保留數(shù)占種群比例的8%.其適應(yīng)度函數(shù)f(x)=100/z(x)，收斂曲線如圖6所示.當(dāng)?shù)?62代時(shí)輸出最優(yōu)解，路徑選擇部分為1_3_2_2_1_3_2_1_2_3，設(shè)備位置分配部分為(2，4)_(1，1)_(2，1)_(3，1)_(1，3)_(2，2)_(3，2)_(1，2)_(3，3)_(2，5)_(1，4)_(2，3)，最優(yōu)單元?jiǎng)澐址桨溉绫?所示，最優(yōu)解下單元布局方案如圖7所示.

圖5 設(shè)備位置信息變異示意圖Fig.5 The schematic diagram of information variation of facilities location

零件編號(hào)批量搬運(yùn)運(yùn)量選擇路徑設(shè)備(操作時(shí)間)M2M8M5M11M3M6M12M1M10M4M7M9P850/2511(2)2(3)3(3)P970/2521(3)2(4)3(2)P380/1621(2)2(2)3(2)P7100/3021(2)2(2)3(2)4(1)P1100/2511(4)2(2)3(2)4(3)P490/2521(2)2(3)3(2)4(2)P660/2031(3)2(3)3(2)4(2)5(1)P570/1611(3)2(3)3(3)P290/2033(1)1(2)2(1)P1080/3031(1)2(5)3(3)設(shè)備負(fù)荷/h510600510540580560530500540470610540

圖6 適應(yīng)度函數(shù)收斂曲線圖Fig.6 The curve of fitness function convergence

圖7 最優(yōu)解下的單元布局圖Fig.7 The cell layout under the optimal solution

從表2可以得到目標(biāo)函數(shù)值為656元，其中單元內(nèi)物流費(fèi)用Cra=680，單元間物流費(fèi)用Cer=800，設(shè)備負(fù)荷差懲罰成本CC=500.單元緊湊性和獨(dú)立性這兩個(gè)要求都得到基本滿足，只有零件9和零件2跨單元加工；設(shè)備負(fù)荷基本得到控制，沒有出現(xiàn)太大波動(dòng)，結(jié)果令人滿意.

4 結(jié) 論

本研究以單元制造實(shí)施過程中的關(guān)鍵階段——單元構(gòu)建問題為研究對(duì)象，針對(duì)U型布局這一單元制造系統(tǒng)的特殊形式，通過數(shù)學(xué)規(guī)劃法，以單元內(nèi)和單元間總的物流費(fèi)用最小和設(shè)備負(fù)荷差懲罰成本最小為目標(biāo)函數(shù)，綜合考慮企業(yè)實(shí)際生產(chǎn)中的零件的批量需求、零件的多工藝路徑和加工時(shí)間、設(shè)備的負(fù)荷均衡和能力限制、物料的搬運(yùn)距離和次數(shù)等因素，建立了單元構(gòu)建數(shù)學(xué)模型，并應(yīng)用遺傳算法，通過一個(gè)數(shù)值案例對(duì)單元構(gòu)建的數(shù)學(xué)模型進(jìn)行求解，得出了最優(yōu)單元?jiǎng)澐址桨讣捌渑苛慵鄳?yīng)的最優(yōu)加工方案，該方案可為相關(guān)制造業(yè)應(yīng)用類似單元制造方案提供有效的技術(shù)指導(dǎo).

[1]WUN,SALVENDYG.Amodifiednetworkapproachforthedesignofcellularmanufacturingsystems[J].Internationaljournalofproductionresearch,1993,31(6):1409-1421.

[2]FANTAHUNMD,CHENMY.Amathematicalmodelforthedesignofcellularmanufacturingsystems[J].Internationaljournalorproductioneconomics,2006,103(2):767-783.

[3] 蔣美仙,魏宗敬,諸葛進(jìn)豪,等.基于BPR的壽生酒生產(chǎn)流程單元布局優(yōu)化[J].浙江工業(yè)大學(xué)學(xué)報(bào),2014,42(3):287-290.

[4] 王愛民,丁國(guó)智,寧汝新.制造單元快速構(gòu)建技術(shù)研究[J].北京理工大學(xué)學(xué)報(bào),2006,26(10):850-856.

[5] 韓毅,王德志,林華珍,等.基于單點(diǎn)變異算法的單元分組問題的研究[J].浙江工業(yè)大學(xué)學(xué)報(bào),2016,44(2):202-206.

[6]VAHIDMD.Newmathematicalmodelforproblemofdynamiccellformationbasedonnumberandaveragelengthofintraandintercellularmovements[J].Appliedmathematicalmodeling,2013,37(4):1884-1896.

[7] 周明.遺傳算法原理及應(yīng)用[M].北京：國(guó)防工業(yè)出版社,1999.

[8]HSUCM,SUCT.Multi-objectivemachine-componentgroupingincellularmanufacturing:ageneticalgorithm[J].Productionplanning&control,1998,9(2):155-166.

[9]FANJJ,FENGDZ.Designofcellularmanufacturingsystemwithquasi-dynamicdualresourceusingmulti-objectiveGA[J].Internationaljournalofproductionresearch,2013,51(14):4134-4154.

Research of manufacturing cell formation based on U-shaped layout

FENG Dingzhong1, WU Xiong1, DING Yangke1, FAN Jiajing2, HE Xiaochu1, WANG Cheng1

(1.College of Mechanical Engineering, Zhejiang University of Technology, Hangzhou 310014, China；2.College of Economics and Management, Zhejiang University of Science and Technology, Hangzhou 310023, China)

The economy of the mass manufacturing and the flexibility of medium and small-batch manufacturing are effectively combined through cellular manufacturing technology, which is got high attention and application in modern manufacturing. Taking cell formation as an object of study, aiming at the special form of cellular manufacturing system of U-shaped layout, the factors of optional process routing, processing time, equipment type and size, processing capacity, distance between equipments and cells, and handling batch and costs of handling tools were overall considered. Through the mathematical programming method, taking the least-cost of logistics within and between cells and the penalty cost minimizing of the equipment load disparity as objective function, the cell formation mathematical model was set up. By the genetic algorithm, the mathematical model of cell formation was solved through a numerical case, the optimal scheme for dividing cells and the corresponding optimal processing scheme of volume parts were concluded.

cellular manufacturing system; cell formation; U-shaped layout; mathematical programming method; genetic algorithm

(責(zé)任編輯：劉 巖)

2016-04-19

國(guó)家自然科學(xué)基金(青年)資助項(xiàng)目(71301148)；浙江省科技計(jì)劃(公益類)項(xiàng)目(2015C33014)

馮定忠(1963—)，男，浙江紹興人，教授，博士生導(dǎo)師，研究方向?yàn)楣?yīng)鏈與智能物流，E-mail：fdz@zjut.edu.cn.

TH181

A

1006-4303(2017)01-0088-06