基于遺傳算法的焊裝線工位平衡問題研究*

孟慶宇，李亮玉，龍　洋，岳建鋒

(天津工業大學 天津市現代機電裝備技術重點實驗室， 天津 300387 )

?

基于遺傳算法的焊裝線工位平衡問題研究*

孟慶宇，李亮玉，龍洋，岳建鋒

(天津工業大學 天津市現代機電裝備技術重點實驗室， 天津 300387 )

在現代化機器人焊裝線生產過程中，大量的作業分配及多工位上焊接工序安排使焊接工位平衡問題表現的尤為突出。針對第二類平衡問題，即在給定工位數和各工序工時情況下，求解最優生產節拍問題進行研究。首先對該問題進行分析并建立節拍優化數學模型，進而提出了一種改進的遺傳算法求解平衡問題。該算法以焊接工序的加工順序優先關系作為約束條件，按種群個體適應度合理選擇交叉概率和變異概率，提高算法搜索效率和解的可靠性。最后通過實例對該算法進行了驗證。

焊裝線；遺傳算法；工位平衡

0　引言

機器人焊裝生產線將多個焊接單元通過輸送線和搬運機器人組合為整條生產線。在對機器人焊裝線進行設計和規劃時，通常做法是沿著焊裝線依次排列各焊接工位，由焊接機器人單元在固定工位上精準、高效的完成焊接任務。焊接件的輸送形式一般采用流水線，對各工位完工時間的同步性要求更高。這需要各工位間的生產節拍保持高度一致，否則會造成某些工位的任務過多無法按時完工，而另外工位由于任務少，已經完工等待上料。這種情況造成設備閑置而降低資源利用率，影響企業生產效率。焊裝線工位間的焊接任務負荷不均會造成在制件積壓，不但使當前工位任務無法按時完成，而且還會對后續生產環節造成很大影響，嚴重的甚至導致整線不能正常運行[1]。在現代化大規模、大批量生產條件下，需對多工位機器人焊裝線上的大量焊接任務進行合理分配，這使得機器人焊裝線平衡問題更顯突出。

在生產平衡問題中，可將平衡問題按照不同的優化目標分為三類[2-4]：①生產節拍已知，求解最優工位數目；②工位數已知，求解最優生產節拍；③生產節拍和工位數已知，求最小平滑指數即負荷均衡指數。目前對于焊裝線平衡問題的主要研究方法有[5-7]: ①目標規劃法; ②啟發式算法; ③人工智能算法。鄧福平等采用自適應蟻群算法對裝配線平衡問題進行求解[8]。張則強等提出帶信息素總和規則的混合搜索機制的蟻群算法求解混流線平衡問題[9]。馬亮采用遺傳算法求解第一類平衡問題[10]，文章按照操作順序優先關系為約束前提，將平衡問題簡化為裝箱問題并對其進行求解，得到最小工位數。但是該方法未考慮種群在不同進化時期的需求，未對交叉、變異概率進行調整。

本文對第二類平衡問題，以焊裝線生產節拍為優化目標，提出在固定工位數目條件下求解機器人焊裝線平衡問題。通過改進的遺傳算法對焊裝線上各焊接工位之間的作業工序的分配問題進行研究，在滿足各工序優先順序的條件下，實現所有工序的合理安排分配，優化焊裝線生產節拍。最終實現各焊接工位作業負荷均衡，提高整線的平衡率。

1　焊裝線平衡問題分類

焊裝線平衡問題按照優化目標的不同可以劃分為以下三類：

(1)已知生產節拍CT和各工序工時Ti，求最優工位數目m(SALBP-1)，其數學模型為：

(1)

maxη取最大值時，焊裝線平衡率達到最優，此時求得最小工位數m。

(2)已知作業工位數m和各作業工序工時Ti，求最優生產節拍CT(SALBP-2)，其數學模型為：

(2)

在作業工位數m、各工位工時T(Sk)已知情況下，maxη表示焊裝線平衡率達到最優，式中maxT(Sk)為所有工序中耗時最大工位工時，即瓶頸工位工時，此時生產節拍CT=maxT(Sk)。所以，在焊裝線的平衡率達到最大時，將得到最優節拍CT。

(3)已知各工位生產節拍和作業工位數m，求最小平滑指數SI(SALBP-3)，其數學模型為：

(3)

minSI取最小值時表示整線負荷均衡指數最小，此時各工位工時T(Sk)最接近生產節拍CT。

2　焊裝線平衡數學模型

對于第二類平衡問題，在滿足各工序作業優先順序約束條件下，將耗時較大的工位上的若干工序與耗時較短工位上的工序進行合理的調整。通過調整可以實現縮小生產節拍，使各工位的作業負荷達到最大均衡度，從而實現降低焊裝線的平滑指數，提高焊裝線平衡率，提高生產效率。

2.1數學模型假設

(1)焊裝線上各工序的標準作業工時固定。

(2)各道工序為不可分最小單元且工序分配具有唯一性，即一道工序只能分配到一個工位。

(3)各道工序工時不大于其所在工位總工時。

(4)生產節拍不小于耗時最大工位的工時。

(5)焊裝線各設備工作效率保持不變。

(6)焊裝線上無并行工位。

2.2工序優先關系

采用遺傳算法進行交叉、變異操作必須保證調整前后不改變各工序的優先作業順序。對有n道工序的焊裝線，各工序的優先順序為n×n階工序關聯矩陣。矩陣元素為xij，工序間的優先關系約束表達為：

2.3優化方法

2.4優化目標模型

針對第二類平衡問題式(2)，在滿足焊裝線各道工序優先順序的前提下，合理的調整和分配各工位的工序，可實現焊裝線工位平衡率的提高，縮短生產節拍。

3　焊裝線平衡遺傳算法設計

本文采用改進的遺傳算法對焊裝線平衡問題進行求解。傳統遺傳算法有陷入局部最優解的缺點，并且交叉概率、變異概率固定，不能動態反映種群在不同進化時期的需求。對此，在保證種群多樣性和優良基因不被破壞前提下，本文對不同進化時期的種群設計了交叉概率、變異概率與個體適應度之間的函數關系，提高算法的收斂效率，防止產生局部最優解。

3.1編碼

首先對焊裝線各道工序進行編碼，得到所有工序的編碼，然后在滿足作業優先順序的條件下，生成可行的染色體編碼。圖1為各道工序流程前驅圖順序及編號圖。

圖1　工序流程前驅圖及編號

如圖1所示，將各道焊接工序[1 2 3 4 5 6]，按照其所示優先順序分配到染色體基因位上，完成染色體編碼。圖2給出了兩個染色體編碼。

圖2　染色體編碼

通過該方法獲得的染色體編碼對操作算子和目標函數具有良好的適應性，減少算法計算量。

3.2染色體解碼

染色體解碼是將染色體中的編碼轉換為目標函數值的操作，種群中染色體編碼表示可行的工序順序，并未給出各道工序如何分配到不同工位，所以需要進行解碼操作，明確各工序的焊接工位。具體操作為：

(2)按照初始節拍CT0，將焊裝線現有的n道工序按照作業優先順序分配到m個工位上，以T(Sk)(k=1,2,..m)表示各工位上工序工時總數，此時實際生產節拍:

CT′=maxT(Sk)k=1,2,3…m

(4)根據θ值的大小按照已建立的數學模型中的優化方法對工位間的工序進行調整。設經過第一次調整后的節拍為CT1，若CT1

(5)更新調整后的生產節拍，重復步驟(3)、(4)，最終可求得趨于穩定的最優生產節拍。

3.3初始化

為防止遺傳算法陷入局部最優，保證初始種群的多樣性的同時使初始種群分散到解空間，本文采用隨機選擇方法進行種群初始化。

3.4適應度函數

適應度函數是衡量種群中個體性能的指標，是個體是否被選擇復制到下一代的依據。通過適應度函數這一參數可以實現對種群結構的調整，保證群體中個體朝著優化的方向前進。本文根據焊裝線生產節拍的目標函數，建立了如下圖所示的適應度函數：

(5)

f函數是按照焊裝線最優生產節拍建立的適應度函數，函數值越趨近于1表明各工位間綜合工時差最小，生產節拍最優。

3.5選擇操作

在種群進化到下一代過程中，必須保證種群染色體優良性，提高算法的運算性能。本文采取保優策略，使種群中具有較高適應度的優良個體更容易被選中，有更大的概率被選中進入下一代。本文根據個體適應度值設計了個體選擇概率P:

(6)

式中，f(u)為個體u的適應度，f(v)為種群中任意個體的適應度，pop_size為種群個體數量。

3.6交叉操作

傳統的遺傳算法中按照固定的交叉概率對染色體是否進行交叉操作進行評價，這種固定參數不能及時的反應出種群在不同時期的進化需求，進而影響了算法的搜索效率和性能。在種群進化初期，個體適應度普遍不高，種群需要較大的交叉概率產生優良基因。種群進化后期，個體適應度普遍提高，為防止種群優良性被破壞，種群需要較小的交叉概率。為此，本文根據個體適應度設計了交叉概率函數：

(7)

本文交叉操作采用兩點交叉方式，步驟如下：

(2)對各配對染色體進行交叉操作，隨機生成[0,1]區間實數ω。若ω大于等于交叉概率Pc則進行交叉操作，否則該組染色體保持不變。

(3)在[1,N]區間隨機生成兩個整數作為兩個交叉點，N為染色體長度(工序總數)，在交叉點之間進行染色體兩點交叉操作。示例如圖3所示。

圖3　染色體交叉點

隨機產生的交叉點為3、5，在染色體1中對應基因片段為[3、5、2]，該基因片段在染色體2中的可行順序為[3、2、5]，將其替代染色體1中交叉點之間的基因片段得到交叉后的子代染色體，同理得到染色體2交叉操作后的子代染色體。父代染色體經交叉操作后的子代染色體如圖4所示。

圖4　交叉后的子代染色體

3.7變異操作

遺傳算法中同樣存在固定的變異概率不利于種群不同時期進化的現象。種群在不同的進化時期對變異概率有不同的需求。對此，本文考慮個體適應度因素設計了變異概率函數：

(8)

本文變異操作步驟如下：

(1)在[0,1]區間隨機生成實數α，若α小于當前染色體變異概率Pm，則當前染色體保持不變，不執行變異操作。若α大于等于當前變異概率，則對當前染色體進行變異操作。

(2)對進行變異操作的染色體在[1,N-1]區間隨機生成一個變異點，示例如圖5所示。

圖5　染色體變異點

(3)將變異點前的基因片段保留到子代染色體，變異點后的基因片段按照工序優先關聯矩陣重新排列,經過重新組合獲得變異后的染色體。對于上圖示例染色體，基因片段[1、4]保持不變，將變異點后的基因片段[3、5、2、6]按照工序優先順序進行重新排列為[2、3、5、6]，兩段基因片段重新組合獲得變異后的染色體，如圖6所示。

圖6　變異后的子代染色體

4　焊接工位平衡規劃實例

為驗證本文方法的可行性，以某殼體焊裝生產線工位平衡規劃問題為例，運用本文算法進行SALBP-2問題求解。

4.1殼體焊裝線任務描述

該殼體機器人焊裝線由4個焊接工位組成，各工位工時及工序如表1所示，各工序及優先作業順序如圖7工序前趨圖所示。該焊裝線共有24道生產工序，所有工序的標準作業工時及各工序的緊前工序如表2所示。

圖7　焊裝線工序前趨圖

工位編號1234安排工序1-910-1718-2122-24工位工時550600660530

該焊裝線調整前工位數m=4，各工位工時分別為550s、600s、660s、530s，此時生產節拍CT=660s。

表2　殼體焊裝線作業工時及緊前工序

4.2平衡求解

基于MATLAB軟件環境，在工位數為4時，通過對工序合理調整，提高焊裝線平衡率，實現工位負荷均衡，求解最優生產節拍。結果如圖8所示。

圖8　m=4時焊裝線平衡圖

在上圖中，橫軸為工位，縱軸為各工位上工序工時總數，即各工位作業工時。由上可知，調整后各工位工時分別為：590s,595s,590s,565s，生產節拍和焊裝線平衡率得到很大提高。

4.3結果對比

將本文算法得到的生產節拍CT、平衡率LE、平滑指數SI與原焊裝線對比結果如表2所示。

表3 結果對比

經過調整，該殼體焊裝線生產節拍縮短65s，平衡率提高9.7%，平滑指數減小59.46，該殼體焊裝線的平衡率得到很大提高，工位間負荷均衡度得到很大改善，生產節拍得到有效提升。

5　結論

(1)本文對第二類平衡問題建立了以生產節拍為優化目標的焊裝線平衡問題優化模型；并通過改進的遺傳算法對該問題進行求解。

(2)該算法以工序間優先作業關系為約束隨機生成初始種群，用本文提出的選擇、交叉、變異方法，提高了種群搜索性能，提升種群個體多樣性、優良性，有效的避免局部最優解產生。

(3)本文通過某殼體焊裝線平衡問題實例求解，驗證了模型和算法的可行性與有效性。前后結果對比表明算法能很好的解決焊裝線平衡問題，提升了焊裝線平衡率，降低了平滑指數，實現了生產節拍的優化。

[1] 唐秋華，席忠民，陳平和，等.混裝線投產序列和工位任務的協同調度機理[J].工業工程,2008,11(1):19-24.

[2] 范維博,周俊,許正良.應用遺傳算法求解第一類裝配線平衡問題[J].計算機技術與發展,2010,20(2):194-196，201.

[3] 劉海江,湯偉,張含葉.基于改進粒子群算法求解第二類裝配平衡問題[J].中國工程機械學報，2014,12(6):508-513.

[4] Arimin S,Christian B.Stata-of-the-art exacl and heuristic solution procedures for simple assembly line balancing[J].European Journal of Operational Research,2006,168(3):666-693.

[5] 衛東.給定序列的混合品種裝配生產線平衡算法[J].機械工程學報,2004,40(4):135-138.

[6] 楊玉珍.基于元啟發式算法的帶生產約束作業車間調度問題若干研究[D].上海:華東理工大學，2014.

[7] 李尚健.應用改進的人工魚群算法求解混合流水車間調度問題[D]．重慶:重慶大學，2013.

[8] 鄧福平.基于蟻群算法的裝配線平衡問題研究[D]．武漢:華中科技大學，2014.

[9] 張則強，程文明，鐘斌，等.混合品種裝配線平衡問題的一種混合搜索機制的蟻群算法[J].機械工程學報，2009,45(5):95-101.

[10] 馬亮，張廣明.基于遺傳算法的焊接生產線工位平衡規劃算法[J].自動化應用,2011(8):9-13.

(編輯李秀敏)

Research of Work-station Balancing Problem of Welding Line Based on the Genetic Algorithm

MENG Qing-yu,LI Liang-yu,LONG Yang,YUE Jian-feng

(Tianjin Key Laboratory of Advanced Mechatronics Equipment Technology，Tianjin Polytechnic University， Tianjin 300387，China)

In the prodution process of modern robot welding line,the reasonable arrangement of lots of task allocation and the welding process of work-stations makes the problem of welding station balancing more important.According to the second category of balancing problem,namely finding the best takt time under the condition of a given work-stat number and working hours in each process,firstly analyze the problem and establish the mathematical modle,then puts forward an improved genetic algorithm to solve the balancing problem.This paper uses the priorities of all the welding processes order as constraint conditions,the cross probability and mutation probability are selected according to the population individual fitness rational,improved the searching efficiency of algorthm and the reliability of the solution.Finally the algorithm is verified by an example.

welding line;the genetic algorithm;work-station balance

1001-2265(2016)07-0127-04DOI:10.13462/j.cnki.mmtamt.2016.07.036

2015-09-08

國家自然科學基金資助項目(U1333128)；天津市科技計劃項目(14ZCDZGX00802)；天津市科技特派員項目(15JCTPJC58400)

孟慶宇(1988—)，男，河北衡水人，天津工業大學碩士研究生，研究方向為機器人焊裝線控制方法及節拍優化,(E-mail)mqy2007@163.com。

TH136;TG506

A