基于DNA遺傳算法的表面貼裝生產(chǎn)線的平衡研究 0830(共7頁(yè))

1、基于(jy)DNA遺傳算法的表面(biomin)貼裝生產(chǎn)線的負(fù)荷均衡研究摘要(zhiyo) 本文以實(shí)際SMT生產(chǎn)現(xiàn)場(chǎng)為背景，在DNA遺傳算法的基礎(chǔ)上，構(gòu)建出了表面貼裝生產(chǎn)線的負(fù)荷均衡模型。在生產(chǎn)節(jié)拍給定以及滿足一些約束條件下，目的是使得所研究的不同貼片機(jī)負(fù)荷均衡，讓生產(chǎn)線平衡得以優(yōu)化。相關(guān)數(shù)值實(shí)驗(yàn)證實(shí)了數(shù)學(xué)模型與算法的有效性，適當(dāng)處理后可作為實(shí)際生產(chǎn)現(xiàn)場(chǎng)的現(xiàn)有軟件, 用于日常生產(chǎn)安排。關(guān)鍵字 SMT DNA遺傳算法 負(fù)荷均衡 生產(chǎn)線平衡;1引言表面組裝技術(shù)( Surface Mount Technology, SMT)是將不同元器件( 無(wú)引腳或短引腳的元器件) 貼、焊到印制電路板( Print

2、ed Circuit Board, PCB) 規(guī)定位置上的電子貼裝技術(shù)。SMT技術(shù)作為新興電子行業(yè)中的核心技術(shù)，在電子工業(yè)中得到越來(lái)越廣泛的應(yīng)用，特別是在筆記本電腦、智能手機(jī)等電子生產(chǎn)企業(yè)中,SMT技術(shù)正成為影響產(chǎn)品質(zhì)量、公司效率最重要的因素。SMT生產(chǎn)線一般會(huì)由不同種類型的貼片機(jī)組成，其中貼片機(jī)是整個(gè)SMT生產(chǎn)線的核心設(shè)備，其生產(chǎn)效率的高低直接決定整條生產(chǎn)線的效率。由于貼片機(jī)是全自動(dòng)設(shè)備，技術(shù)含量高，其工作原理和貼片工藝較復(fù)雜，如若不能很好的進(jìn)行貼片機(jī)之間的負(fù)荷均衡，會(huì)降低整條生產(chǎn)線的效率以及設(shè)備的利用率。因此，研究表面貼片機(jī)負(fù)荷均衡對(duì)于提高SMT生產(chǎn)線的生產(chǎn)效率具有十分重要的意義。2 研究

3、背景本文以國(guó)內(nèi)某大型電腦代加工企業(yè)SMT生產(chǎn)車間為背景，以松下公司目前最新研發(fā)的NPM-D高速貼片機(jī)為研究對(duì)象，分別是可以超高速貼裝微小元件的16吸嘴貼裝頭高速貼片機(jī)、可以高速貼裝微小元件到中型元件的8吸嘴貼裝頭高速貼片機(jī)、可以貼裝各種異形元件的2吸嘴貼裝頭泛用貼片機(jī)。本文主要研究的是多臺(tái)貼片機(jī)之間的負(fù)荷均衡優(yōu)化,即不同種類元件在不同貼片機(jī)之間的負(fù)荷均衡問(wèn)題，目的是使不同型號(hào)的貼片機(jī)作業(yè)時(shí)間近乎相同，接近于已知的Cycle Time，從而使SMT生產(chǎn)裝配線的平衡率達(dá)到最優(yōu)。遺傳算法雖然作為目前最廣泛使用且被認(rèn)同的解決最優(yōu)化問(wèn)題的方法，但是(dnsh)有其自身的缺點(diǎn)，其局部搜索能力差，容易過(guò)早收

4、斂，而且基于0與1的二進(jìn)制的編碼方式存在明顯的不足，對(duì)于一些繁復(fù)的表達(dá)方式，會(huì)出現(xiàn)編碼長(zhǎng)度(chngd)過(guò)長(zhǎng)、編碼方式復(fù)雜且混亂的情況。從DNA生物學(xué)的生物進(jìn)化過(guò)程(guchng)受到啟發(fā)，將遺傳算法與DNA機(jī)理相結(jié)合，組成DNA遺傳算法。DNA遺傳算法同時(shí)具有遺傳算法與生物學(xué)DNA的諸多優(yōu)點(diǎn)，可使編碼方式實(shí)現(xiàn)更靈活的表達(dá)，并且能使遺傳算法的過(guò)程變得更加容易，很好的解決了單一遺傳算法過(guò)早收斂以及編碼方式欠佳等不足的缺點(diǎn)。3 表面貼裝生產(chǎn)線負(fù)荷均衡數(shù)學(xué)模型的建立設(shè)一條表面貼裝生產(chǎn)線由臺(tái)貼片機(jī)組成，有個(gè)獨(dú)立的元件分配到臺(tái)機(jī)器中去，其中一臺(tái)貼片機(jī)可以吸取個(gè)原件。每個(gè)工作站的實(shí)際工作時(shí)間應(yīng)盡可能地接近

5、給定的生產(chǎn)線節(jié)拍時(shí)間，這樣可使得臺(tái)貼片機(jī)作業(yè)時(shí)間近乎相同，使得各臺(tái)機(jī)器負(fù)荷均衡，從而提升設(shè)備利用率。設(shè)每一臺(tái)機(jī)器的時(shí)間為，求解目標(biāo)是尋求一種最優(yōu)方案，在節(jié)拍給定以及滿足實(shí)際生產(chǎn)現(xiàn)場(chǎng)下的一些約束條件下，使得整條生產(chǎn)線平衡達(dá)到最優(yōu)。滿足上述條件的數(shù)學(xué)模型如下：表示貼片機(jī)編號(hào)，為整數(shù)，且，其中機(jī)器編號(hào)1-7為NPM-D 16Nozzle型號(hào),機(jī)器編號(hào)8為NPM-D 8Nozzle型號(hào)，機(jī)器編號(hào)9-10為NPM-D 2Nozzle型號(hào)。表示每臺(tái)機(jī)器的實(shí)際工作時(shí)間，表示產(chǎn)線生產(chǎn)節(jié)拍（已知，由公司每日生產(chǎn)排程給定），表示元件的種類, 為所有的集合，其中表示為機(jī)器貼裝元件種類的集合，表示種元件在基板PCB上

6、的數(shù)量，即基板PCB需要多少個(gè)種元件，表示(biosh)機(jī)器(j q)貼片一個(gè)元件的時(shí)間(shjin)，參數(shù)是由貼片機(jī)廠商提供，其中=0.051s/chip（=1,2,3.7），=0.090s/chip，=0.360s/chip，表示元件，即基板上所有點(diǎn)的元件，為所有的集合，表示吸嘴的種類，為所有的集合，表示第臺(tái)機(jī)器的供料槽（，公司實(shí)際貼片機(jī)料槽最多可放取17個(gè)），表示種元件所占的供料槽，表示若元件種類在編號(hào)為1-7的貼片機(jī)上使用吸嘴，則其值為1，否則為0，表示若元件種類在編號(hào)為8的貼片機(jī)上使用吸嘴，則其值為1，否則為0，表示若元件種類在編號(hào)為9-10的貼片機(jī)上使用吸嘴，則其值為1，否則為0，

7、如果元件安排在工作臺(tái)上，則其值為1，否則為0.其目標(biāo)函數(shù)為， (1)其中， , (2) ， (3), (4), (5), （6）, （7）4 基于DNA遺傳算法的負(fù)荷均衡模型的編碼計(jì)算DNA-GA（DNA遺傳算法）從初始化出發(fā)，通過(guò)一代一代的進(jìn)化與選擇，從而得到優(yōu)秀的群體與個(gè)體(gt)，進(jìn)而找到問(wèn)題的最優(yōu)化解決方法。4.1 編碼(bin m)方式(fngsh)DNA遺傳算法最重要的步驟是采取何種方式進(jìn)行編碼，在初始化時(shí)，待解決問(wèn)題的參數(shù)設(shè)計(jì)是通過(guò)4個(gè)字符集來(lái)編碼以形成染色體，即DNA鏈. DNA-GA以染色體的形式為基本單位進(jìn)行二進(jìn)制編碼，即A(00)、T(01)、C(10)、D(11),然后

8、每次從K顆元件隨機(jī)取出4顆元件，編碼為元件種類和機(jī)器工作臺(tái)吸嘴一一對(duì)應(yīng)的關(guān)系，并組成DNA湯。4.2 計(jì)算適應(yīng)度因?yàn)槟繕?biāo)函數(shù)是求最小化的問(wèn)題，選取適應(yīng)度函數(shù)為式中，c為常數(shù)，為目標(biāo)函數(shù)的保守估計(jì)值。則目標(biāo)函數(shù)值越小，其所對(duì)應(yīng)的適應(yīng)度越大，4.3 選擇按照一定的概率從DNA湯中選取m個(gè)DNA鏈個(gè)體，作為雙親用于繁殖后代，產(chǎn)生新的個(gè)體加入到下一代。4.4 交叉 DNA鏈中的交叉位置是隨機(jī)選取的。在標(biāo)準(zhǔn)交叉中，其后代的個(gè)體是基于一個(gè)隨機(jī)產(chǎn)生的特征碼（交叉特征碼為0和1）對(duì)父代進(jìn)行操作而得到的。如下所示，若某一位置上交叉特征碼為0，則其后代的堿基不變；若某一位置上交叉特征碼為1，則其后代的堿基由雙親互

9、換得到。4.5 倒位以一定(ydng)的概率從DNA湯中隨機(jī)(su j)選取若干個(gè)DNA鏈個(gè)體(gt)，在選中的DNA鏈個(gè)體中，隨機(jī)將某兩個(gè)位置堿基順序進(jìn)行倒位。倒位互換的目的是試圖找到更好的進(jìn)化性的基因順序。4.6 終止條件經(jīng)過(guò)上述過(guò)程，將產(chǎn)生的新一代DNA湯反饋回算法流程的第2步（即計(jì)算適應(yīng)度），再進(jìn)行評(píng)價(jià)、選擇、交叉和倒位操作，如此循環(huán)往復(fù)，使得適應(yīng)度不斷提高，直到適應(yīng)度提高到某一極限值，則算法結(jié)束。5.數(shù)值實(shí)驗(yàn)5.1 數(shù)據(jù)來(lái)源本文以實(shí)際生產(chǎn)現(xiàn)場(chǎng)中一款PCB板的S面（PCB板有兩面，分為S面和C面，是公司人為稱呼，以示區(qū)分）為研究對(duì)象，此PCB板S面總共需要貼裝的元件有512顆。其中貼裝

10、機(jī)有10臺(tái)，編號(hào)為1-7的為16Nozzle的NPM-D的高速機(jī)，編號(hào)為8的是8Nozzle的NPM-D的高速機(jī)，編號(hào)為9-10的為2Nozzle的NPM-D的泛用機(jī)。吸嘴的選擇因元器件種類和貼片機(jī)類型而異, 不同種類的元器件需要采用不同的吸嘴進(jìn)行吸取, 被安排到高速機(jī)上或泛用機(jī)上的同一種元器件可以選擇不同的吸嘴進(jìn)行操作。在本文所研究的模型中，通過(guò)筆者在公司實(shí)踐獲得的相關(guān)數(shù)據(jù)可得，本文所研究的PCB基板所需元件種類總共有16種，元件種類以及對(duì)應(yīng)的種類數(shù)量如表1所示，元件種類0802080412041208160816122412241632123220322444124424442844365

11、624編號(hào)12345678910111213141516種類數(shù)量24615925732311111121211表1 元件種類以及對(duì)應(yīng)的種類數(shù)量一覽表吸嘴型號(hào)L有7種，不同機(jī)型的機(jī)器對(duì)應(yīng)元件種類以及吸嘴種類如表2所示，機(jī)型型號(hào)吸嘴種類16 Nozzle2302358 Nozzle1402352402 Nozzle10021003100424215443544610061192元件種類16 Nozzle080208048 Nozzle08041208161224122 Nozzle161224124412160824163212322032244424442844365624表2 不同(b tn)

12、機(jī)型的機(jī)器對(duì)應(yīng)(duyng)元件種類以及(yj)吸嘴種類一覽表由表1、表2可知，在選取元件時(shí)我們首先要考慮元件種類的特殊性以及貼裝的優(yōu)先關(guān)系，有些元件只能在特定的機(jī)型工作臺(tái)上貼裝，如編號(hào)為0802的元件只能在16Nozzle的機(jī)型上貼裝，1608的元件只能在2Nozzle的機(jī)型上貼裝；有些元件可以在16Nozzle、8Nozzle的機(jī)型上貼裝，如編號(hào)為0804的元件；有些元件可以在8Nozzle、2Nozzle的機(jī)型上貼裝，如1612、2412的元件。由于所吸取的元件種類不同，高速機(jī)和泛用機(jī)吸取一顆元件所需要的時(shí)間不同，表3為貼片機(jī)在理想狀態(tài)下吸取一顆元件所需要的時(shí)間。機(jī)型NPM-D 16No

13、zzleNPM-D 8NozzleNPM-D 2Nozzle時(shí)間（s/chip）0.0510.0900.360表3 貼片機(jī)理想狀態(tài)下吸取一顆元件所需時(shí)間5.2 數(shù)據(jù)結(jié)果說(shuō)明 由公司自帶軟件編入相應(yīng)程序，通過(guò)秒表測(cè)量，獲得貼片機(jī)測(cè)量時(shí)間如下表4所示，機(jī)臺(tái)編號(hào)12345678910機(jī)型16Nozzle16Nozzle16Nozzle16Nozzle16Nozzle16Nozzle16Nozzle8Nozzle2Nozzle2Nozzle時(shí)間（s）9.02258.87759.343759.38259.18759.226259.2259.23259.819.5825表4計(jì)算得=5.21，其平衡率為。通

14、過(guò)(tnggu)導(dǎo)入DNA遺傳算法，模擬(mn)建模流程，經(jīng)編碼、選擇(xunz)、交叉、倒位等計(jì)算方式，計(jì)算適應(yīng)度，然后再重復(fù)上述步驟，重新計(jì)算適應(yīng)度，直至找到最優(yōu)解。仿真程序用Matlab6.0編寫，算法中使用的參數(shù)為交叉概率,變異概率,種群規(guī)模N=100，選取最大遺傳代數(shù)為300.平衡預(yù)算結(jié)果如表5所示，機(jī)臺(tái)編號(hào)12345678910機(jī)型16Nozzle16Nozzle16Nozzle16Nozzle16Nozzle16Nozzle16Nozzle8Nozzle2Nozzle2Nozzle時(shí)間(s)9.3459.2349.4329.4729.2439.4679.5529.5439.2439.367表5由目標(biāo)公式 可得=1.622，其平衡率為。由上述比較可得，通過(guò)DNA遺傳算法對(duì)不同元件重新進(jìn)行調(diào)度分配，使得每臺(tái)貼片機(jī)之間的設(shè)備負(fù)荷得到很大的改善，平衡率也達(dá)到98.30%，6 結(jié)束語(yǔ)本文基于DNA遺傳算法，對(duì)多臺(tái)貼片機(jī)組成的SMT生產(chǎn)線的負(fù)荷均衡問(wèn)題進(jìn)行了理論數(shù)學(xué)建模和算法仿真，通過(guò)對(duì)生產(chǎn)