基于改進(jìn)遺傳算法的制造單元設(shè)計研究

范佳靜 馮定忠

1.浙江工業(yè)大學(xué)，杭州，310014 2.浙江科技學(xué)院，杭州，310023

基于改進(jìn)遺傳算法的制造單元設(shè)計研究

范佳靜1，2馮定忠1

1.浙江工業(yè)大學(xué)，杭州，310014 2.浙江科技學(xué)院，杭州，310023

針對制造單元構(gòu)建問題的特征，構(gòu)建了以總搬運成本以及機(jī)器設(shè)備的折舊和維修成本最低為主要目標(biāo)，綜合考慮了產(chǎn)品設(shè)備單元劃分、單元內(nèi)機(jī)器布局以及單元間布局的綜合性制造單元模型。同時針對模型求解的復(fù)雜性，提出了改進(jìn)遺傳算法，并將其用于制造單元模型的求解。通過雙層遺傳算法，既保證了算法中染色體個體的有效性，又滿足了遺傳算法適者生存的根本原理；采用精英策略保證算法的收斂性；同時通過在求解過程中不斷調(diào)整交叉算子和變異算子防止了算法收斂到局部最優(yōu)解。最后將所提出的模型和改進(jìn)的遺傳算法應(yīng)用于復(fù)雜實例，證明模型和算法的有效性。

制造單元；數(shù)學(xué)模型；改進(jìn)遺傳算法；精英策略

0 引言

單元制造是成組技術(shù)在企業(yè)中的具體應(yīng)用，通過合理的單元構(gòu)建、單元內(nèi)機(jī)器布局以及單元間的布局，可以有效提高企業(yè)的生產(chǎn)效率、縮短準(zhǔn)備時間和提前期，以及降低在制品成本等，從而降低企業(yè)的物料搬運成本、工具使用成本、設(shè)備成本以及員工聘用成本。因此近30年來國內(nèi)外許多學(xué)者對其進(jìn)行了大量的研究。

單元構(gòu)建的方法有可視化編碼、聚類分析、模糊聚類法、圖論法、啟發(fā)式算法、仿真模擬技術(shù)、數(shù)學(xué)規(guī)劃法與智能技術(shù)等［1－8］。數(shù)學(xué)規(guī)劃法應(yīng)用智能技術(shù)解決單元構(gòu)建問題，由于其目標(biāo)函數(shù)及約束條件的任意選擇性特點與實際生產(chǎn)過程中零件結(jié)構(gòu)、批量以及工藝路徑的多樣性相符合，且便于應(yīng)用計算機(jī)等先進(jìn)手段的運用，因此這種方法在單元構(gòu)建中最具應(yīng)用潛力。

由于制造單元構(gòu)建問題較復(fù)雜，雖然學(xué)者們已經(jīng)提出了大量的規(guī)劃模型，但是具有可實施性的制造單元應(yīng)該是多種關(guān)聯(lián)因素共同作用的結(jié)果，這些因素包括產(chǎn)品投產(chǎn)數(shù)量、加工的單位時間、加工工藝路徑、設(shè)備能力、同種類型設(shè)備的數(shù)量（可選設(shè)備）等［9］，因此目前所考慮的數(shù)學(xué)規(guī)劃模型中，還存在以下問題：①考慮同種設(shè)備只有一臺，而實際情況是同種設(shè)備可能有2臺或2臺以上；②沒有考慮零件操作存在多路徑的問題，或者即使考慮到該問題，但是每條路徑中的操作順序沒有明確；③同種設(shè)備的數(shù)量直接影響產(chǎn)品生產(chǎn)過程中的搬運次數(shù)和搬運成本，設(shè)備數(shù)量越多，則勢必會減少物料的搬運次數(shù)，但是同樣會增加設(shè)備的折舊和維修成本，然而在目前學(xué)者的研究中都沒有同時考慮物料搬運成本與機(jī)器的折舊和維修成本這兩個成本因素。

因此本文在假設(shè)單元布局為直線形而單元內(nèi)機(jī)器布局為直線形或者L形的基礎(chǔ)上，就以上三方面問題進(jìn)行改進(jìn)，提出一個一般性的單元制造0－1非線性整數(shù)規(guī)劃模型，同時確定產(chǎn)品和機(jī)器的劃分、機(jī)器布局以及單元布局使得總搬運成本與機(jī)器維修和折舊成本為最小。

1 模型分析

1.1 相關(guān)參數(shù)

p表示零件，p＝1，2，…，P；i，j表示機(jī)器，i，j＝1，2，…，M；r表示路徑，r＝1，2，…，RP；op表示操作，op＝1，2，…，OP；k，k′表示單元，k，k′＝1，2，…，K；s，q表示單元內(nèi)機(jī)器所處的位置；g，h表示單元所處的位置；Nmax為單元內(nèi)允許擁有的最多機(jī)器數(shù)；Nmin為單元內(nèi)允許擁有的最少機(jī)器數(shù)；Dintra為單元內(nèi)相鄰機(jī)器的移動距離；Dinter為相鄰單元間的移動距離；Ni為第i種機(jī)器最多擁有的臺數(shù)；Cintra為單元內(nèi)的單位移動成本；Cinter為單元間的單位移動成本；Dp為第p種零件的年需求量；Bp為第p種零件的移動批量；Ci為第i種機(jī)器每年的維修和折舊成本；W 為一個無窮大的數(shù)。

Xipr（op）＝1表示第p種零件的第r條路徑的第op 個操作需要使用機(jī)器i，否則 Xipr（op）＝0；Xik＝1表示第k個單元擁有機(jī)器i，否則Xik＝0；Xiks＝1表示第i種機(jī)器位于第k個單元的第s個位置，否則Xiks＝0；Xkg＝1表示第k個單元位于第g個位置，否則Xkg＝0；Xpr＝1表示第p種零件選擇第r條路徑進(jìn)行操作，否則Xpr＝0；Xipr（op）k＝1表示第p種零件的第r條路徑的第op個操作在單元k中的機(jī)器i上操作，否則Xipr（op）k＝0。

1.2 模型分析

上述模型中目標(biāo)函數(shù)表示綜合考慮單元構(gòu)建、機(jī)器布置和單元布置的情況下，使得總搬運成本和機(jī)器購買成本為最低。

約束條件中，式（1）和式（2）表示單元尺寸的限制；式（3）表示每種機(jī)器最多能夠購買的數(shù)量；式（4）表示每種零件只能選擇一條路徑進(jìn)行操作；式（5）表示如果某個零件的某條路徑被選擇，則該路徑上的所有操作都必須進(jìn)行；式（6）表示每個位置至多只能放置一臺設(shè)備；式（7）表示每個設(shè)備只能放置于一個位置；式（8）表示每個單元只能固定于一個位置；式（9）表示每個位置只能設(shè)置一個單元；式（10）表示變量Xipr（op）k和變量Xpr以及變量Xipr（op）之間的關(guān)系；式（11）表示變量Xipr（op）k、Xik、Xpr、Xkg和Xiks均為0－1變量。

2 改進(jìn)遺傳算法

目前學(xué)者們已經(jīng)提出了很多種制造單元構(gòu)建問題模型的求解算法，如兩階段法、粒子優(yōu)化算法、混合遺傳算法、神經(jīng)網(wǎng)絡(luò)法、模糊算法等［9-16］。遺傳算法是一種高效、并行、全局性的概率搜索算法。相比于傳統(tǒng)的優(yōu)化方法，遺傳算法具有較好的全局搜索性能、不容易陷入局部最優(yōu)等優(yōu)勢，適用于處理大規(guī)模的復(fù)雜非線性優(yōu)化問題。但是針對不同的數(shù)學(xué)模型，由于變量和約束條件的特殊性，在運用基本遺傳算法時往往會根據(jù)具體問題進(jìn)行算法改進(jìn)來適應(yīng)模型的求解。針對上述提出的0－1非線性整數(shù)規(guī)劃模型，鑒于其變量的復(fù)雜性以及較強(qiáng)的關(guān)聯(lián)性，本文采用雙層遺傳算法、精英策略以及自適應(yīng)算法來進(jìn)行模型的求解，既加快了求解的速度，又有利于獲得模型更好的滿意解。

2.1 染色體編碼

本文采取二進(jìn)制編碼和整數(shù)編碼混合的方法進(jìn)行變量染色體的設(shè)定。變量Xik和Xipr（op）k采取二進(jìn)制編碼，而Xiks、Xpr和Xkg則采取整數(shù)編碼方式，如圖1所示。通過這種編碼方式可以使得隨機(jī)選取的個體滿足式（4）和式（6）～ 式（9）。

圖1 染色體編碼

2.2 雙層遺傳算法流程

由于變量Xik和Xpr與變量Xiks和Xipr（op）k之間存在較強(qiáng)的關(guān)聯(lián)性，且對目標(biāo)函數(shù)都有一定的貢獻(xiàn)性，因此在運用遺傳算法求解模型時，采用雙層遺傳算法來防止大量無效解的產(chǎn)生，從而加快運算速度。即首先確定變量Xik、Xpr和Xkg的初始種群，在對這三個變量運用遺傳算法進(jìn)行循環(huán)時，對與之相關(guān)的 Xiks、Xipr（op）k變量再套用遺傳算法進(jìn)行迭代優(yōu)化，找出與每組Xik、Xpr和Xkg變量相對應(yīng)的使得目標(biāo)函數(shù)最優(yōu)的 Xiks、Xipr（op）k。通過雙層遺傳算法既可體現(xiàn)遺傳算法適者生存的本質(zhì)，又可以保證所有的變量均滿足式（5）和式（10）。具體過程如圖2所示。

2.3 主層遺傳算法

（1）選擇策略。選擇策略采用的是隨機(jī)競爭選擇方式。先通過普通方法計算選擇概率，然后采用輪盤賭方法選出染色體對，通過染色體對之間的比較，使高適應(yīng)度值的個體進(jìn)入復(fù)制階段。

（2）交叉算子。根據(jù)染色體結(jié)構(gòu)，本文采用三點交叉方式進(jìn)行交叉操作，在交配池中隨機(jī)選取一對進(jìn)行交叉的染色體后，再隨機(jī)生成3個交叉點進(jìn)行交叉，如圖3所示。

（3）變異算子。對變量Xik和Xpr采用單點變異方式進(jìn)行變異，變量Xkg則不進(jìn)行變異。

（4）自適應(yīng)算法。根據(jù)Srinvia提出的自適應(yīng)遺傳算法，交叉算子和遺傳算子會隨著個體適應(yīng)度值自動改變。交叉概率Pc和變異概率Pm按照以下公式自適應(yīng)調(diào)整：

圖2 雙層遺傳算法流程

圖3 染色體交叉過程

其中，fmax為群體中最大適應(yīng)度值；favg為每一代群體的平均適應(yīng)度值；f′為待交叉的兩個中較大適應(yīng)度值；f為要變異個體的適應(yīng)度值；Pc1＝0.9；Pc2＝0.6；Pm1＝0.1；Pm2＝0.01。

2.4 二層遺傳算法

針對變量Xik和Xpr染色體個體的進(jìn)化，通過二層遺傳算法對與之有一定關(guān)聯(lián)的Xiks和Xipr（op）k變量的染色體進(jìn)行循環(huán)迭代，從而得到每一組Xik和Xpr的染色體相對應(yīng)的Xiks和Xipr（op）k較優(yōu)染色體。在第二層遺傳算法中染色體的選擇采用隨機(jī)選擇的方式任意選擇一條染色體，然后根據(jù)相應(yīng)的變異方式進(jìn)行變異，其中不進(jìn)行交叉過程。如圖4所示，針對Xiks變量的染色體編碼，每一單元分別選擇兩個不為零的隨機(jī)點進(jìn)行換位變異。而變量Xipr（op）k的染色體為0－1編碼，因此迭代過程中采用單點變異的方法。

圖4 Xiks染色體變異過程

2.5 精英策略

在每一次迭代完成時，為了提高群體進(jìn)化水平，本算法還加入了精英策略方法。也就是每次迭代完成后的父代群體和子代群體合并，并按照適應(yīng)度的高低進(jìn)行排列，選擇適應(yīng)度高的Y1個群體作為下一次迭代的父代群體，以此保證每次迭代完成后的群體均為最優(yōu)群體，并采用最優(yōu)群體作為后代復(fù)制的基礎(chǔ)。

2.6 迭代終止

對于主層次遺傳算法，為了獲得更好的適應(yīng)度值，循環(huán)次數(shù)較多，一般T1取500～1000，而對于二層遺傳算法，由于針對每一個變量Xik和Xpr染色體個體的改變都要進(jìn)行一次迭代，同時在迭代的過程中容易出現(xiàn)重復(fù)的編碼值，因此一次循環(huán)的次數(shù)可以相對較少，一般T2取20～50。

3 算例分析

本文應(yīng)用上述模型和改進(jìn)遺傳算法對一個復(fù)雜算例進(jìn)行建模，該問題共有18種機(jī)器和17種產(chǎn)品，每種產(chǎn)品有2條路徑和3～6個操作，具體情況見表1。通過改進(jìn)遺傳算法對該問題進(jìn)行求解，在第900代時收斂于最優(yōu)解，到1000代時獲得的最優(yōu)解見表2，各零件選擇的路徑分別為2＿2＿1＿1＿1＿1＿2＿2＿2＿2＿1＿2＿2＿1＿2＿1＿2，設(shè) 備 6、10、15各有兩臺，而其他設(shè)備均為一臺，同時存在4次單元間的移動，歷代最優(yōu)適應(yīng)度值如圖5所示。

圖5 歷代適應(yīng)度值

4 結(jié)束語

面對越來越激烈的市場競爭壓力，以及客戶對產(chǎn)品的多樣化、個性化的需求和交付條件，許多企業(yè)已經(jīng)或正在由傳統(tǒng)的大批量生產(chǎn)方式向多品種、小批量的方式轉(zhuǎn)變。在此背景下，各種先進(jìn)的生產(chǎn)制造系統(tǒng)和生產(chǎn)制造方式被提出并應(yīng)用于企業(yè)的生產(chǎn)實踐。單元制造系統(tǒng)由于兼顧了大批量生產(chǎn)的成本和質(zhì)量優(yōu)勢，以及多品種、小批量生產(chǎn)的快速響應(yīng)能力，越來越受到企業(yè)的歡迎。

本文主要考慮到單元構(gòu)建、單元內(nèi)機(jī)器布局以及單元布局問題存在的相關(guān)性，在具有多路徑和操作順序，并允許擴(kuò)大機(jī)器數(shù)量的基礎(chǔ)上提出了制造單元模型，從而為企業(yè)合理安排機(jī)器零件加工提供了一定的數(shù)學(xué)依據(jù)。但是本文主要考慮的是單周期下需求已知的情況下的集成數(shù)學(xué)模型，而隨著客戶需求變化的不斷擴(kuò)大，對于不同產(chǎn)品的需求量也起伏不定，在不同時期產(chǎn)品的需求量是不恒定的。因此接下來的研究將進(jìn)一步擴(kuò)大到多周期環(huán)境中在需求不確定的情況下的單元制造問題。

表1 機(jī)器與零件的關(guān)聯(lián)表

表2 機(jī)器－零件單元劃分、單元內(nèi)機(jī)器分布以及單元分布表

［1］ Ahi A，Aryanezhad M B，Ashtiani B，et al.A Novel Approach to Determine Cll Formation，Intracellular Machine Layout and Cell Layout in CMS Problem Based on TOPSIS Method［J］.Computer ＆ Operation Research，2009，36：1478－1496.

［2］ Norman B A，Smith A E.A Continuous Approach to Considering Uncertainty in Facility Design［J］.Computers and Operations Research，2006，33：1760－1775.

［3］ Chiang C P，Lee S D.Joint Determination of Machine Cells and Linear Intercell Layout［J］.Computers ＆ Operations Research，2004，31：1603－1619.

［4］ Tavakkoli－Moghaddam R，Javadian N，Javadian B，et al.Desigh of a Facility Layout Probelem in Cellualr Manufacturing Systems with Stochastic Demands［J］.Applied Mathematics and Computation，2007，184：721－728.

［5］ 白書清，王愛民，李伯虎.面向應(yīng)急動員批產(chǎn)的流水式制造單元構(gòu)建技術(shù)［J］.計算機(jī)集成制造系統(tǒng)，2008，14（1）：64－73.

［6］ 劉敏，嚴(yán)雋薇，于軼.基于SOA的網(wǎng)格制造單元構(gòu)造方法［J］.同濟(jì)大學(xué)學(xué)報（自然科學(xué)版），2008，（10）：1417－1424.

［7］ 邵長運，初紅艷，費仁元，等.基于專家系統(tǒng)的制造單元構(gòu)建研究［J］.機(jī)械設(shè)計與制造，2008，（12）：100－103.

［8］ 王軍強(qiáng)，孫樹棟，王東成，等.基于約束理論的制造單元管理和控制研究［J］.計算機(jī)集成制造系統(tǒng)，2006，12（7）：1108－1121.

［9］ 王國新，閻艷，寧汝新，等.模糊神經(jīng)網(wǎng)絡(luò)與啟發(fā)式算法相結(jié)合的制造單元構(gòu)建方法［J］.計算機(jī)集成制造系統(tǒng)，2008，14（11）：2175－2185.

［10］ Chu C H.Genetic Algorithms for Integrating Cell Formation with Machine Layout and Scheduling［J］.Computer ＆Industrial Engineering，2007，53：277－289.

［11］ Chan Felix T S，Lau K W.Two－stage Approach for Machine－part Grouping and Cell Layout Problems［J］.Robotics and Computer－integrated Manufacturing，2006，22：217－238.

［12］ 康艷，朱宏，李旭偉.混合遺傳算法在制造單元構(gòu)建中的應(yīng)用［J］.微計算機(jī)信息（測控自動化），2009，5（12）：186－188.

［13］ 李杰，王云峰，等.基于模糊技術(shù)的制造單元構(gòu)建方法研究［J］.計算機(jī)集成制造系統(tǒng)，2004，10（12）：1561－1567.

［14］ 帥旗，陳耀軍，楊瑩.敏捷制造系統(tǒng)單元建模與優(yōu)化研究現(xiàn)狀綜述［J］.機(jī)電工程，2008（5）：29－32.

［15］ 王東成，何衛(wèi)平.神經(jīng)網(wǎng)絡(luò)在制造單元構(gòu)建中的研究與應(yīng)用［J］.中國機(jī)械工程，2006，17（5）：1040－1044.

［16］ 王雷，唐敦兵，等.基于粒子群優(yōu)化算法的制造單元聚類研究［J］.計算機(jī)集成制造系統(tǒng)，2009，15（2）：328－332.

Study on Manufacturing Cellular Design Based on Advanced Genetic Algorithm

Fan Jiajing1，2Feng Dingzhong1
1.Zhejiang University of Technology，Hangzhou，310014
2.Zhejiang University of Science and Technology，Hangzhou，310023

A comprehensive model for manufacturing cellular was put forward which aimed at abtaining the minmum of material handling cost and machine depreciable and repair cost as well as synchronously considering the cellular formaiton，machine layout and cellular layout according to the characteristics of the problem of manufacturing cellular.And an advanced genetic algorithm was brought forward to solve this model.The individual validity and the characteristic of genetic algorithm were ensured；the convergence of algorithm through the elite strategy was ensured and the local convergence was protected by adjusting the crossover operator and mutation operator constantly.At last，the validity of the model and algorithm was proved by a complicated example.

manufacturing cellular；mathmatical model；advanced genetic algorithm；elite strategy

TH165

1004—132X（2011）01—0039—06

2010—03—09

浙江省自然科學(xué)基金資助項目（Y6090482，Y6090533）；浙江省錢江人才計劃資助項目（2010R10096）

（編輯 郭 偉）

范佳靜，女，1977年生。浙江工業(yè)大學(xué)機(jī)械工程學(xué)院博士研究生，浙江科技學(xué)院經(jīng)濟(jì)與管理學(xué)院講師。主要研究方向為工業(yè)工程、可重構(gòu)制造系統(tǒng)建模及控制、企業(yè)物流規(guī)劃。馮定忠（通訊作者），男，1963年生。浙江工業(yè)大學(xué)機(jī)械工程學(xué)院教授、博士研究生導(dǎo)師。