基于U型布局制造單元的構建研究

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

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

基于U型布局制造單元的構建研究

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

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

單元制造技術能夠將大批量制造的經濟性與中小批量制造的靈活性進行有效結合，受到現代制造業的高度關注與應用.以單元構建問題為研究對象，針對U型布局這一單元制造系統的特殊形式，綜合考慮可選擇的工藝路徑、相應工序的加工時間、設備的種類、加工能力、設備形狀大小、設備之間和單元之間的距離、搬運工具的搬運批量及費用等信息，通過數學規劃法，以單元內和單元間總的物流費用最小和設備負荷差懲罰成本最小為目標函數，建立單元構建數學模型，進而應用遺傳算法，通過數值案例對單元構建的數學模型進行求解，得出最優單元劃分方案及其批量零件相應的最優加工方案.

單元制造系統；單元構建；U型布局；數學規劃法；遺傳算法

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

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

1 單元構建問題描述

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

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

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

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

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

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

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

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

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

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

8) 每種零件在對應設備上加工所需的時間是已知的.

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

2 單元構建數學模型

在構建單元規劃的數學模型時，需要綜合考慮到總的物流費用和單元的設備負荷均衡性，但這兩者之間的單位量綱不同.因此，在考慮單元設備負荷差的合理范圍的情況下，加入懲罰成本，當設備與單元內平均負荷相差過大時，就給予一定的懲罰，從而要求單元內的設備負荷盡量滿足要求，同時也使得這些目標能匹配到同一個目標函數之下.單元構建目標函數最終考慮的是總的物流費用和總的負荷差懲罰成本，目標函數越小，說明單元劃分越優，所以單元構建的目標函數可以表述為

minZ=αCra+βCer+γCC=

(1)

其中

(2)

(3)

權重系數α，β，γ應滿足

α+β+γ=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)表示每臺設備只能放在一個單元內和每臺設備只能放在相應的一個位置；式(6)表示每種零件只能選擇一條工藝路徑進行加工和任何單元的任何位置只能放置一臺設備；式(7)對所構建的單元規模做了限制，即單元內不能沒有設備但是設備數量也不能超過單元內的位置數；式(8)為單元內設備的負荷確定了上限，即單元內任何設備在加工期內的負荷都不能超過該時期內設備能提供的有效工作時間；式(9)表示變量的取值范圍.

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

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

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

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

遺傳算法求解過程如下：

1)染色體編碼

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

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

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

2)初始種群的產生

全局隨機產生初始種群P1,P2,…,Pm，初始種群的規模初步設定為m=100，初始的進化代數K=0，前代最大的適應度值PFmax=0，取最大迭代次數Kmax=500.

3)適應度值計算

根據單元構建問題模型的特點可知，每個個體代入目標函數后得到的值均為非負值，因此在這里采用倒數的形式對目標函數進行轉換，其表達式為

(10)

如果直接取倒數，適應度值會較小，因此取原目標函數倒數的100倍作為轉換后的目標函數.

4)選擇操作

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

5)交叉操作

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

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

6)變異操作

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

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

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

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

7)循環終止

循環執行步驟4～6)，當進化周期數K大于種群最大進化周期數Kmax時，算法終止，跳出循環.

8)解 碼

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

在該案例中，最大迭代次數Kmax=500，交叉概率Pc=20%，變異概率Pm=0.01，最佳個體保留數占種群比例的8%.其適應度函數f(x)=100/z(x)，收斂曲線如圖6所示.當迭代到262代時輸出最優解，路徑選擇部分為1_3_2_2_1_3_2_1_2_3，設備位置分配部分為(2，4)_(1，1)_(2，1)_(3，1)_(1，3)_(2，2)_(3，2)_(1，2)_(3，3)_(2，5)_(1，4)_(2，3)，最優單元劃分方案如表2所示，最優解下單元布局方案如圖7所示.

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

零件編號批量搬運運量選擇路徑設備(操作時間)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)設備負荷/h510600510540580560530500540470610540

圖6 適應度函數收斂曲線圖Fig.6 The curve of fitness function convergence

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

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

4 結 論

本研究以單元制造實施過程中的關鍵階段——單元構建問題為研究對象，針對U型布局這一單元制造系統的特殊形式，通過數學規劃法，以單元內和單元間總的物流費用最小和設備負荷差懲罰成本最小為目標函數，綜合考慮企業實際生產中的零件的批量需求、零件的多工藝路徑和加工時間、設備的負荷均衡和能力限制、物料的搬運距離和次數等因素，建立了單元構建數學模型，并應用遺傳算法，通過一個數值案例對單元構建的數學模型進行求解，得出了最優單元劃分方案及其批量零件相應的最優加工方案，該方案可為相關制造業應用類似單元制造方案提供有效的技術指導.

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

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

[3] 蔣美仙,魏宗敬,諸葛進豪,等.基于BPR的壽生酒生產流程單元布局優化[J].浙江工業大學學報,2014,42(3):287-290.

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

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

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

[7] 周明.遺傳算法原理及應用[M].北京：國防工業出版社,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

(責任編輯：劉 巖)

2016-04-19

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

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

TH181

A

1006-4303(2017)01-0088-06