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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在構(gòu)建單元規(guī)劃的數(shù)學(xué)模型時，需要綜合考慮到總的物流費用和單元的設(shè)備負荷均衡性，但這兩者之間的單位量綱不同.因此，在考慮單元設(shè)備負荷差的合理范圍的情況下，加入懲罰成本，當(dāng)設(shè)備與單元內(nèi)平均負荷相差過大時，就給予一定的懲罰，從而要求單元內(nèi)的設(shè)備負荷盡量滿足要求，同時也使得這些目標(biāo)能匹配到同一個目標(biāo)函數(shù)之下.單元構(gòu)建目標(biāo)函數(shù)最終考慮的是總的物流費用和總的負荷差懲罰成本，目標(biāo)函數(shù)越小，說明單元劃分越優(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)表示每臺設(shè)備只能放在一個單元內(nèi)和每臺設(shè)備只能放在相應(yīng)的一個位置；式(6)表示每種零件只能選擇一條工藝路徑進行加工和任何單元的任何位置只能放置一臺設(shè)備；式(7)對所構(gòu)建的單元規(guī)模做了限制，即單元內(nèi)不能沒有設(shè)備但是設(shè)備數(shù)量也不能超過單元內(nèi)的位置數(shù)；式(8)為單元內(nèi)設(shè)備的負荷確定了上限，即單元內(nèi)任何設(shè)備在加工期內(nèi)的負荷都不能超過該時期內(nèi)設(shè)備能提供的有效工作時間；式(9)表示變量的取值范圍.

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

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

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

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

遺傳算法求解過程如下：

1)染色體編碼

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

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

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

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

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

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

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

(10)

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

4)選擇操作

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

5)交叉操作

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

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

6)變異操作

對于種群中個體基因的變異操作雖然也是隨機進行的，但是與交叉操作是隨機選擇個體不同，變異操作是隨機選擇基因來進行的.

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

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

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

7)循環(huán)終止

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

8)解 碼

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

在該案例中，最大迭代次數(shù)Kmax=500，交叉概率Pc=20%，變異概率Pm=0.01，最佳個體保留數(shù)占種群比例的8%.其適應(yīng)度函數(shù)f(x)=100/z(x)，收斂曲線如圖6所示.當(dāng)?shù)?62代時輸出最優(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)單元劃分方案如表2所示，最優(yōu)解下單元布局方案如圖7所示.

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

零件編號批量搬運運量選擇路徑設(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è)備負荷/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)物流費用Cra=680，單元間物流費用Cer=800，設(shè)備負荷差懲罰成本CC=500.單元緊湊性和獨立性這兩個要求都得到基本滿足，只有零件9和零件2跨單元加工；設(shè)備負荷基本得到控制，沒有出現(xiàn)太大波動，結(jié)果令人滿意.

4 結(jié) 論

本研究以單元制造實施過程中的關(guān)鍵階段——單元構(gòu)建問題為研究對象，針對U型布局這一單元制造系統(tǒng)的特殊形式，通過數(shù)學(xué)規(guī)劃法，以單元內(nèi)和單元間總的物流費用最小和設(shè)備負荷差懲罰成本最小為目標(biāo)函數(shù)，綜合考慮企業(yè)實際生產(chǎn)中的零件的批量需求、零件的多工藝路徑和加工時間、設(shè)備的負荷均衡和能力限制、物料的搬運距離和次數(shù)等因素，建立了單元構(gòu)建數(shù)學(xué)模型，并應(yīng)用遺傳算法，通過一個數(shù)值案例對單元構(gòu)建的數(shù)學(xué)模型進行求解，得出了最優(yōu)單元劃分方案及其批量零件相應(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] 蔣美仙,魏宗敬,諸葛進豪,等.基于BPR的壽生酒生產(chǎn)流程單元布局優(yōu)化[J].浙江工業(yè)大學(xué)學(xué)報,2014,42(3):287-290.

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

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

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

[7] 周明.遺傳算法原理及應(yīng)用[M].北京：國防工業(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

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

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

TH181

A

1006-4303(2017)01-0088-06