基于DNA遺傳算法的表面貼裝生產線負荷優化分配

李志剛，吳 浩

(成都理工大學管理科學學院，四川 成都 610059)

?

基于DNA遺傳算法的表面貼裝生產線負荷優化分配

李志剛，吳 浩

(成都理工大學管理科學學院，四川 成都 610059)

印制電路板組裝任務的負荷優化分配包含設備約束、工藝約束等大量約束，是電子行業表面貼裝生產線中的一類重要優化問題。其優化目標是在生產節拍給定和一定約束條件下，使得不同貼裝機負荷均衡，任務分配達到最優。首先，根據不同表面貼裝機、不同吸嘴及多種類型元件匹配的的復雜性，提出貼裝機任務分配組合優化的問題；然后分析設備和元件的參數、組裝可行性、貼裝時間，以及貼裝優化關系等因素，并提出假設條件，建立了平衡率最大化條件下的負荷分配組合優化的數學模型；最后，針對貼裝生產線負荷分配問題的復雜性與特殊性，通過改良編碼方式后的DNA遺傳算法來優化組合數學模型，計算適應度，并借助MATLAB進行仿真求解，進而找到最優解。結果表明：本文提出的貼裝生產線負荷分配方法可以解決帶復雜約束的印制電路板組裝負荷優化分配問題，提高設備的平衡率和生產效率，促進生產線的優化運行。

SMT;DNA遺傳算法;負荷均衡;優化分配

1 引言

表面貼裝技術(SMT，Surface Mount Technology)是將表面貼裝元器件貼焊到印制電路板(PCB，Printed Circuit Board)規定位置上的電子裝聯技術[1]。SMT生產線一般由印刷機、點膠機、貼裝機、回焊爐等設備組成。其中貼裝機是整個SMT生產線的核心設備，其生產效率的高低直接決定整條生產線的效率。近年來，SMT生產線的相關優化問題越來越受到國內外學者的關注和研究。Crama等[2]指出SMT生產線的優化問題可概括為單機單板問題、單機多板問題和多機多板等問題，他提出并構建了幾種情況的數學模型，同時也對每一種問題進行相應的分析。Rogers和Warrington等[3]則對SMT生產線的貼裝調度問題做了比較系統的研究，將其區分為多條生產線的優化方法，單條生產線的優化方法和貼裝機的優化，給出了每一種優化方法的數學模型，并做了一定的優化研究和仿真。但這些研究對包含多種型號、多吸嘴貼裝機組成的生產線在給定節拍的組合優化問題關注較少。為了促進SMT生產線優化運行，使得不同貼裝機負荷均衡，提高生產效率，本文建立了不同貼裝機、不同吸嘴及多種類型元件匹配的負荷優化分配模型。然后，用DNA遺傳算法和改良后的編碼方式來優化組合數學模型，通過仿真計算尋找最優解，驗證模型方法的合理性和有效性。

遺傳算法是目前被認同的解決負荷優化分配問題的一種有效方法，該方法是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。它將問題的求解表示成染色體的適者生存的過程，不直接針對解進行操作，而對編碼后形成的染色體進行選擇、交叉、變異等操作。通過染色體的一代代的遺傳進化，最終收斂到最適應環境的個體，即問題的最優解和滿意解。但遺傳算法也有缺點，如局部搜索能力差，容易早期收斂，而且常用的二進制編碼方法不能表達豐富的遺傳信息,對于一些繁雜的表達方式，會出現編碼長度過長、編碼方式復雜且混亂的情況[4]。因此在其計算模型中沒有反映出遺傳信息對生物體的調控作用。近年來，對遺傳算法的改進，主要是針對交叉算子的改進，Tohka等[5]提出調和交叉算子，Deep和Thakur等[6]則提出拉普拉斯算子。這些改進的遺傳算子對遺傳算法的性能有很大改善。丁永生等[9]從DNA生物學的生物進化過程中得到啟發，將遺傳算法與DNA機理相結合，提出了基于DNA編碼的遺傳算法。由Adelman[7]用實驗證明了DNA計算的可行性，SM Rowers等[8]在此基礎上，提出并建立了一種新的模型——粘貼模型，用來解決最小集合覆蓋等問題。聶書志等針對調度問題提出了基于調度優先級的DNA遺傳算法，解決了常規遺傳算法中編碼方式、收斂及在交叉變異操作中產生非法后代等問題，提高了編碼和搜索的效率[15]。

表1 元件種類以及對應的種類數量一覽表

DNA遺傳算法采用基于堿基的編碼方式，在進化的過程中更能表達豐富的遺傳信息，具有更強大全局搜索能力。由于它同時具有遺傳算法與生物學DNA的優點，可使編碼方式實現更靈活的表達，并能使遺傳算法的過程變得更加容易，克服了單一遺傳算法過早收斂以及編碼方式繁雜、不靈活等缺點。在遺傳算法中引入DNA計算，單個DNA可表達為4個字母的集合{A，T，C，G}，DNA串可作為譯碼信息，對DNA可施加分子水平上的操作[17]。可為解決表面貼裝生產線負荷分配問題的參數選擇的苛刻性提供支持。

2 表面貼裝生產線負荷優化模型的建立

2.1 表面貼裝生產線的特性

本文以某電腦代加工企業SMT生產線為背景，生產線貼裝機主要有16吸嘴超高速貼裝機(16 Nozzle)、8吸嘴高速貼裝機(8 Nozzle)、2吸嘴(2 Nozzle)泛用貼裝機三種類型。不同種類的元器件需要采用不同吸嘴的貼裝機進行貼裝,吸嘴的選擇因元器件種類和貼裝機類型而異,吸嘴、貼裝機機型以及電子元器件都是一一對應的關系，被安排到高速貼裝機上或泛用機上的同一種元器件可以選擇不同的吸嘴進行操作[13]。我們研究的PCB基板所需元件種類J共有16種，元器件種類j以及對應的種類數量Dj如表1所示。

吸嘴型號l有12種，不同機型的貼裝機對應元件種類j以及吸嘴種類l如表2所示。

由表1、表2可知，在選取元件時我們要考慮元件種類的特殊性和貼裝的優先關系，有些元件只能在特定的機型上貼裝，如編號為0802的元件只能在16 Nozzle的機型上貼裝，1608的元件只能在2 Nozzle的機型上貼裝?？梢娺@種PCB組裝生產線上的負荷分配優化，主要是通過PCB上的元件的分配來平衡設備的負荷。它包括以下2個子問題：一是不同類型的元器件在不同種類吸嘴的布置問題，可簡稱為元件組裝順序問題；二是不同類型吸嘴在多個組裝設備上的布置問題，可簡稱為吸嘴布置問題。加之在實際生產中，還需要考慮其它問題，如供料器的布置問題等，這些子問題就構成了復雜的組合優化問題。同時也說明PCB組裝負荷分配優化問題具有多目標和約束復雜等特點。

表2 機型i、元件種類j及吸嘴種類l一覽表

2.2 負荷優化分配模型的構建

這里以單品種單批量PCB板的S面(PCB可分為S面和C面兩個面)為研究對象，此PCB板S面總共需要貼裝的元件有512顆，生產線有貼裝機10臺。由于PCB組裝負荷分配優化問題中需要考慮縮短組裝時間，減少延遲，平衡設備工作負荷等多個優化目標。因此，在建立優化模型時，應在生產線節拍給定的前提下，使得不同型號的貼裝機作業時間盡量接近給定的節拍，才能使SMT生產線的平衡率達到最優，提高整條生產線的效率及設備利用率。其次，在建立模型的過程中，考慮主要因素，忽略次要因素，并滿足以下7個假設條件：

條件1：不考慮突發事件的發生，如停電導致的生產線無法生產。

條件2：每臺貼裝機的性能都處在最理想的狀態，且性能值大概相同。

條件3：不考慮換料時間，每臺貼片機都較好的運行。

條件4：員工對貼裝機的操作熟練程度一致。

條件5：所研究的物料元件沒有出現質量因素的任何不良。

條件6：研究對象是單條生產線優化問題。

條件7：研究的是單品種單批量的問題。

設一條表面貼裝生產線由m臺貼裝機組成，有n個獨立的元件分配到m臺機器中去，其中一臺貼裝機可以貼裝ki個元件。

每臺貼裝機的實際工作時間ti應盡可能地接近給定的生產線節拍時間tT，這樣可使得m臺貼裝機作業時間近乎相同，使得各貼裝機負荷均衡，從而提升設備利用率[16]。設每一臺機器的時間為ti，求解目標是尋求一種最優方案，在節拍tT給定以及滿足實際生產現場下的一些約束條件下，使得整條生產線負荷分配達到最優。滿足上述條件的數學模型如下：

i表示貼裝機編號，i為整數，且1≤i≤10，其中機器編號1-7為16吸嘴型號,機器編號8為8吸嘴型號，機器編號9-10為2吸嘴型號。

ti表示每臺機器的實際工作時間，tT表示產線生產節拍(tT已知，由企業每日生產排程給定)。

j表示元件的種類, J為所有j的集合，j∈J，其中Ji表示為機器i貼裝元件種類j的集合。

Dj表示j種元件在基板PCB上的數量，即基板PCB需要多少個j種元件。

wi表示i機器貼片一個元件的時間，wi參數是由貼裝機生產廠商提供，其中wi=0.051s/chip(i=1,2,3，…，7)，w8=0.090 s/chip，w9=w10=0.360s/chip。

k表示元件，即基板上所有點的元件，K為所有k的集合。

表示吸嘴的種類，L為所有l的集合。

mi表示第i臺機器的供料槽(0≤mi≤17，企業實際貼裝機料槽最多可放取17個)，Sj表示j種元件所占的供料槽。

bl1j表示若元件種類j在編號為1-7的貼裝機上使用吸嘴l，則其值為1，否則為0。

這起案件從公訴到開庭再到結案，時間跨度大約有四個多月，在這四個多月里，李凌除去完成其他的日常工作，節省下來的所有時間，基本上全部花在了這起案件的調解工作上。在常人的印象中，法官往往只需要高坐在審判席上，宣布審判結果就行了，完全不需要這么勞心勞力。但是李凌卻沒有這么做，因為她覺得，法院的判決一方面是為了彰顯法律的公平與正義，要讓犯法的人得到應有的處罰。但另一方面，法律不外乎人情，在法律之外，我們還要為當事雙方謀求一個雙方都滿意的結果。

bl2j表示若元件種類j在編號為8的貼裝機上使用吸嘴l，則其值為1，否則為0。

bl3j表示若元件種類j在編號為9-10的貼裝機上使用吸嘴l，則其值為1，否則為0。

zij如果元件j安排在貼裝機i上貼裝，則其值為1，否則為0。

其目標函數為：

(1)

(2)

s.t.

(3)

(4)

(5)

(6)

(7)

其中，為了求出i臺貼裝機的平衡率的最大化，其中目標函數(1)是簡化的，求出每臺貼裝機的實際貼裝時間與i臺貼裝機的貼裝時間的最大差值和的最小值；公式(2)求出的是每臺貼裝機的實際貼裝時間；公式(3)表示的是分配到第i臺貼裝機元件種類j對應的供料槽要小于第i臺機器的供料槽；公式(4)表示的一種電子元件j只能安排到特定的貼裝機i上；公式(5)、(6)、(7)表示的一種電子元件j只能安排到特定的吸嘴種類l上。

3 基于DNA遺傳算法的負荷優化模型編碼計算

DNA-GA(DNA遺傳算法)從初始化出發，通過一代一代的進化與選擇，從而得到優良的群體與個體，進而找到問題的最優化解決方法。

3.1 初始化和編碼

3.2 計算適應度

我們是以貼裝機的貼裝時間與最大時間差值和

表3 不同貼裝機貼裝時間

表4 仿真計算平衡結果的數據

的絕對值的最小化為目標函數，所以我們可以選取適應度函數為:

(8)

3.3 進化終止條件

整個模型計算過程就是一個不斷尋找最優解的過程，在每次得到一個DNA群之后再返回到計算適應度的步驟，然后再進行選擇、交叉、變異以及倒位等相關操作，當計算出的適應度的值不再提高,即達到一個臨界值的時候，則說明尋找到了最優解，計算結束[12]。

4 數據計算及結果分析

由貼裝機自帶軟件編寫相應程序，通過秒表測量，測得貼裝機貼裝時間如表3所示。

由表3中數據計算得出目標函數的最小值為：

計算其平衡率為：

依據上述設計的DNA遺傳算法流程，經過選擇、交叉、變異和倒位等步驟，計算適應度，然后再重復上述步驟，重新計算適應度，直至找到最優解[16]。采用Matlab6.0編寫程序，進行仿真計算，算法中參數設計為交叉概率pc=0.95,變異概率pm=0.10,種群規模N=100，最大遺傳代數為300，仿真計算平衡結果如表4所示。

計算得出優化后目標函數的最小值為：

計算優化后平衡率為：

從表4看出不同種類貼裝機貼裝時間在9.2348—9.5529S之間，與給定的9.5S節拍接近，說明數據是可行的。優化前后的數據如圖1所示(圖中“1”表示優化前,“2”表示優化后)。

圖1 模型算法優化前后數據比較圖

由上述直方圖比較可得，通過DNA遺傳算法對元件組裝任務重新調度優化分配，使得每臺貼裝機之間的負荷得到較大的改善，目標函數的最小值由之前的2.330變為1.625，平衡率也從原先的87.538%提升到98.298%，提高了貼裝生產線的平衡率。

5 結語

本文研究了表面貼裝生產線負荷優化分配問題，在考慮復雜約束條件下，構建了相應的分配優化模型，并利用DNA遺傳算法對模型進行求解，在企業給定9.5S生產節拍和一定約束條件下，通過改良后的編碼方式和適應度計算，進一步優化了數學模型，并借助MATLAB對生產現場的實際數據進行仿真求解，進而找到最優解，驗證了模型及算法的有效性和合理性。結果表明：本文提出的方法可以有效地解決了PCB貼裝任務在多臺貼裝機之間的負荷均衡優化問題，使生產線負荷分配得到優化和改善，提高設備利用率和生產效率。

[1] 郭姝娟,靳志宏.表面組裝技術生產線貼片機負荷均衡優化[J].計算機集成制造系統，2009，15(4):817-822.

[2] Crama R,Klunder C. Production planning for surface mount technology lines[J].International Journal of Production Research,2004，42(13)：2693-2718.

[3] Rogers P, Warrington R. Production planning for surface mount technology lines[J].Discrete Applied Mathematics,2002,123(1):339-341.

[4] 蔣騰旭,謝楓.遺傳算法中防止早熟收斂的幾種措施[J].計算機與現代化,2006，136(12):54-56.

[5] Tohka J， Krestyannikov E， Toga AW. Genetic algorithms for finite mixture model based voxel classification in neuroimaging[J].IEEE Transactions on Medical Imaging,2007,26(5):696-711.

[6] Deep K,Thakur M.A new crossover operator for real coded genetic algorithms[J].Applied Mathematics and Computation，2007，188(1):895-901.

[7] Adelman L M. Molecular computation of solutions to combinatorial problems [J]. Science，1994，266(5187):1021-1024.

[8] Roweis S, Winfree E, Burgoyne R, et al. A sticker-based model for DNA computation [J].Journal of Computational Biology，1998，5(4):615-629.

[9] 丁永生,任立紅,邵世煌. DNA遺傳算法及其函數尋優應用[C].張嗣贏，王福利：中國控制與決策學術年會論文集.沈陽：控制與決策編輯部,昆明，5月1日，2000：235-239.

[10] 王雷,蔣愛平.基于DNA編碼的遺傳神經網絡算法及應用[J].電子測量與儀器學報,2009，22(6):23-26.

[11] 何洋林,葉春明,馬明.裝配生產線平衡問題DNA遺傳算法研究[J].機械設計與制造，2008,45(3):68-70.

[12] 張友鵬,顏晨陽.一種基于DNA計算的多模態函數求解模型[J].鐵道學報，2005,27(6):112-116.

[13] 陳貞.多品種印刷電路板表面貼裝生產線優化[D].大連：大連海事大學，2009.

[14] 周開樂，沈超，丁帥，等.基于遺傳算法的微電網負荷優化分配[J].中國管理科學，2014，22(3)：68-73

[15] 聶書志，葉邦彥. DNA遺傳算法在Job Shop調度優化中的應用[J].機械設計與制造，2010,47(5):43-45.

[16] 劉穎,靳志宏.多品種小批量生產環境下表面貼裝生產線的平衡優化[J].大連海事大學學報，2012,38(2):87-90.

[17] 李巖.制造系統復雜調度中混合遺傳算法的應用[D].上海：上海交通大學，2000

[18] 申哲巍,張樹芳,孫東海.改進云遺傳算法在負荷優化分配中的應用[J].陜西電力，2012,41(12):43-46.

Optimization of Load Distribution on Surface Mount Production Line Based on DNA Genetic Algorithm

LI Zhi-Gang , WU Hao

(College of Management Science, Chengdu University of Technology , Chengdu 610059，China)

The PCB assembly in the load distribution between the different assembly equipments in SMT production line is an important class of optimization problems in the electronics industry. Given the takt time and the actual production process constraints,its optimization objective is to make different placers load balanced and task allocation optimal ,so that improving production efficiency and equipment utilization. Firstly, in order to balance the workload among different placers, based on a variety of different types of the surface mounters, nozzles and component matching particularity, the problem of task allocation optimization of placement machines is proposed; Secondly, the actual production line design information factor parameter components, assembly feasibility, the actual placement time, as well as the placement relationship optimization are analyzed, the mathematical model of load distribution combinatorial optimization is set up given optimization maximizing equilibrium conditions; Finally, aiming at the complexity and particularity of load distribution problems in SMT production line, the mathematical models are optimized through the combination of improved encoding of DNA genetic algorithm to calculate the fitness,and the problem is solved by using MATLAB, and then the optimal solution is found. The results show that: the load distribution optimization method proposed in this paper can effectively solve the problems in load optimization distribution of printed circuit board(PCB)assembly,advance the utilization and equilibrium of equipment,and promote the operation optimization of the production line.

SMT；DNA genetic algorithm；load balancing；optimal allocation

2014-06-29；

2015-05-03

四川省科技支撐計劃項目(2011Z00011)；成都理工大學科研創新團隊資助計劃(KYTD201101)

簡介：李志剛(1962-)，男(漢族)，四川宜賓人，成都理工大學管理學院，教授，博士，研究方向：工業工程，E-mail:cdlglzg@163.com.

1003-207(2016)10-0171-06

10.16381/j.cnki.issn1003-207x.2016.10.020

F406.2

A