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

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

(天津工業(yè)大學(xué) 天津市現(xiàn)代機(jī)電裝備技術(shù)重點(diǎn)實(shí)驗(yàn)室， 天津 300387 )

?

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

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

(天津工業(yè)大學(xué) 天津市現(xiàn)代機(jī)電裝備技術(shù)重點(diǎn)實(shí)驗(yàn)室， 天津 300387 )

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

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

0　引言

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

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

本文對第二類平衡問題，以焊裝線生產(chǎn)節(jié)拍為優(yōu)化目標(biāo)，提出在固定工位數(shù)目條件下求解機(jī)器人焊裝線平衡問題。通過改進(jìn)的遺傳算法對焊裝線上各焊接工位之間的作業(yè)工序的分配問題進(jìn)行研究，在滿足各工序優(yōu)先順序的條件下，實(shí)現(xiàn)所有工序的合理安排分配，優(yōu)化焊裝線生產(chǎn)節(jié)拍。最終實(shí)現(xiàn)各焊接工位作業(yè)負(fù)荷均衡，提高整線的平衡率。

1　焊裝線平衡問題分類

焊裝線平衡問題按照優(yōu)化目標(biāo)的不同可以劃分為以下三類：

(1)已知生產(chǎn)節(jié)拍CT和各工序工時(shí)Ti，求最優(yōu)工位數(shù)目m(SALBP-1)，其數(shù)學(xué)模型為：

(1)

maxη取最大值時(shí)，焊裝線平衡率達(dá)到最優(yōu)，此時(shí)求得最小工位數(shù)m。

(2)已知作業(yè)工位數(shù)m和各作業(yè)工序工時(shí)Ti，求最優(yōu)生產(chǎn)節(jié)拍CT(SALBP-2)，其數(shù)學(xué)模型為：

(2)

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

(3)已知各工位生產(chǎn)節(jié)拍和作業(yè)工位數(shù)m，求最小平滑指數(shù)SI(SALBP-3)，其數(shù)學(xué)模型為：

(3)

minSI取最小值時(shí)表示整線負(fù)荷均衡指數(shù)最小，此時(shí)各工位工時(shí)T(Sk)最接近生產(chǎn)節(jié)拍CT。

2　焊裝線平衡數(shù)學(xué)模型

對于第二類平衡問題，在滿足各工序作業(yè)優(yōu)先順序約束條件下，將耗時(shí)較大的工位上的若干工序與耗時(shí)較短工位上的工序進(jìn)行合理的調(diào)整。通過調(diào)整可以實(shí)現(xiàn)縮小生產(chǎn)節(jié)拍，使各工位的作業(yè)負(fù)荷達(dá)到最大均衡度，從而實(shí)現(xiàn)降低焊裝線的平滑指數(shù)，提高焊裝線平衡率，提高生產(chǎn)效率。

2.1數(shù)學(xué)模型假設(shè)

(1)焊裝線上各工序的標(biāo)準(zhǔn)作業(yè)工時(shí)固定。

(2)各道工序?yàn)椴豢煞肿钚卧夜ば蚍峙渚哂形ㄒ恍?，即一道工序只能分配到一個(gè)工位。

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

(4)生產(chǎn)節(jié)拍不小于耗時(shí)最大工位的工時(shí)。

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

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

2.2工序優(yōu)先關(guān)系

采用遺傳算法進(jìn)行交叉、變異操作必須保證調(diào)整前后不改變各工序的優(yōu)先作業(yè)順序。對有n道工序的焊裝線，各工序的優(yōu)先順序?yàn)閚×n階工序關(guān)聯(lián)矩陣。矩陣元素為xij，工序間的優(yōu)先關(guān)系約束表達(dá)為：

2.3優(yōu)化方法

2.4優(yōu)化目標(biāo)模型

針對第二類平衡問題式(2)，在滿足焊裝線各道工序優(yōu)先順序的前提下，合理的調(diào)整和分配各工位的工序，可實(shí)現(xiàn)焊裝線工位平衡率的提高，縮短生產(chǎn)節(jié)拍。

3　焊裝線平衡遺傳算法設(shè)計(jì)

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

3.1編碼

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

圖1　工序流程前驅(qū)圖及編號

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

圖2　染色體編碼

通過該方法獲得的染色體編碼對操作算子和目標(biāo)函數(shù)具有良好的適應(yīng)性，減少算法計(jì)算量。

3.2染色體解碼

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

(2)按照初始節(jié)拍CT0，將焊裝線現(xiàn)有的n道工序按照作業(yè)優(yōu)先順序分配到m個(gè)工位上，以T(Sk)(k=1,2,..m)表示各工位上工序工時(shí)總數(shù)，此時(shí)實(shí)際生產(chǎn)節(jié)拍:

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

(4)根據(jù)θ值的大小按照已建立的數(shù)學(xué)模型中的優(yōu)化方法對工位間的工序進(jìn)行調(diào)整。設(shè)經(jīng)過第一次調(diào)整后的節(jié)拍為CT1，若CT1

(5)更新調(diào)整后的生產(chǎn)節(jié)拍，重復(fù)步驟(3)、(4)，最終可求得趨于穩(wěn)定的最優(yōu)生產(chǎn)節(jié)拍。

3.3初始化

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

3.4適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是衡量種群中個(gè)體性能的指標(biāo)，是個(gè)體是否被選擇復(fù)制到下一代的依據(jù)。通過適應(yīng)度函數(shù)這一參數(shù)可以實(shí)現(xiàn)對種群結(jié)構(gòu)的調(diào)整，保證群體中個(gè)體朝著優(yōu)化的方向前進(jìn)。本文根據(jù)焊裝線生產(chǎn)節(jié)拍的目標(biāo)函數(shù)，建立了如下圖所示的適應(yīng)度函數(shù)：

(5)

f函數(shù)是按照焊裝線最優(yōu)生產(chǎn)節(jié)拍建立的適應(yīng)度函數(shù)，函數(shù)值越趨近于1表明各工位間綜合工時(shí)差最小，生產(chǎn)節(jié)拍最優(yōu)。

3.5選擇操作

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

(6)

式中，f(u)為個(gè)體u的適應(yīng)度，f(v)為種群中任意個(gè)體的適應(yīng)度，pop_size為種群個(gè)體數(shù)量。

3.6交叉操作

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

(7)

本文交叉操作采用兩點(diǎn)交叉方式，步驟如下：

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

(3)在[1,N]區(qū)間隨機(jī)生成兩個(gè)整數(shù)作為兩個(gè)交叉點(diǎn)，N為染色體長度(工序總數(shù))，在交叉點(diǎn)之間進(jìn)行染色體兩點(diǎn)交叉操作。示例如圖3所示。

圖3　染色體交叉點(diǎn)

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

圖4　交叉后的子代染色體

3.7變異操作

遺傳算法中同樣存在固定的變異概率不利于種群不同時(shí)期進(jìn)化的現(xiàn)象。種群在不同的進(jìn)化時(shí)期對變異概率有不同的需求。對此，本文考慮個(gè)體適應(yīng)度因素設(shè)計(jì)了變異概率函數(shù)：

(8)

本文變異操作步驟如下：

(1)在[0,1]區(qū)間隨機(jī)生成實(shí)數(shù)α，若α小于當(dāng)前染色體變異概率Pm，則當(dāng)前染色體保持不變，不執(zhí)行變異操作。若α大于等于當(dāng)前變異概率，則對當(dāng)前染色體進(jìn)行變異操作。

(2)對進(jìn)行變異操作的染色體在[1,N-1]區(qū)間隨機(jī)生成一個(gè)變異點(diǎn)，示例如圖5所示。

圖5　染色體變異點(diǎn)

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

圖6　變異后的子代染色體

4　焊接工位平衡規(guī)劃實(shí)例

為驗(yàn)證本文方法的可行性，以某殼體焊裝生產(chǎn)線工位平衡規(guī)劃問題為例，運(yùn)用本文算法進(jìn)行SALBP-2問題求解。

4.1殼體焊裝線任務(wù)描述

該殼體機(jī)器人焊裝線由4個(gè)焊接工位組成，各工位工時(shí)及工序如表1所示，各工序及優(yōu)先作業(yè)順序如圖7工序前趨圖所示。該焊裝線共有24道生產(chǎn)工序，所有工序的標(biāo)準(zhǔn)作業(yè)工時(shí)及各工序的緊前工序如表2所示。

圖7　焊裝線工序前趨圖

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

該焊裝線調(diào)整前工位數(shù)m=4，各工位工時(shí)分別為550s、600s、660s、530s，此時(shí)生產(chǎn)節(jié)拍CT=660s。

表2　殼體焊裝線作業(yè)工時(shí)及緊前工序

4.2平衡求解

基于MATLAB軟件環(huán)境，在工位數(shù)為4時(shí)，通過對工序合理調(diào)整，提高焊裝線平衡率，實(shí)現(xiàn)工位負(fù)荷均衡，求解最優(yōu)生產(chǎn)節(jié)拍。結(jié)果如圖8所示。

圖8　m=4時(shí)焊裝線平衡圖

在上圖中，橫軸為工位，縱軸為各工位上工序工時(shí)總數(shù)，即各工位作業(yè)工時(shí)。由上可知，調(diào)整后各工位工時(shí)分別為：590s,595s,590s,565s，生產(chǎn)節(jié)拍和焊裝線平衡率得到很大提高。

4.3結(jié)果對比

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

表3 結(jié)果對比

經(jīng)過調(diào)整，該殼體焊裝線生產(chǎn)節(jié)拍縮短65s，平衡率提高9.7%，平滑指數(shù)減小59.46，該殼體焊裝線的平衡率得到很大提高，工位間負(fù)荷均衡度得到很大改善，生產(chǎn)節(jié)拍得到有效提升。

5　結(jié)論

(1)本文對第二類平衡問題建立了以生產(chǎn)節(jié)拍為優(yōu)化目標(biāo)的焊裝線平衡問題優(yōu)化模型；并通過改進(jìn)的遺傳算法對該問題進(jìn)行求解。

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

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

[1] 唐秋華，席忠民，陳平和，等.混裝線投產(chǎn)序列和工位任務(wù)的協(xié)同調(diào)度機(jī)理[J].工業(yè)工程,2008,11(1):19-24.

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

[3] 劉海江,湯偉,張含葉.基于改進(jìn)粒子群算法求解第二類裝配平衡問題[J].中國工程機(jī)械學(xué)報(bào)，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] 衛(wèi)東.給定序列的混合品種裝配生產(chǎn)線平衡算法[J].機(jī)械工程學(xué)報(bào),2004,40(4):135-138.

[6] 楊玉珍.基于元啟發(fā)式算法的帶生產(chǎn)約束作業(yè)車間調(diào)度問題若干研究[D].上海:華東理工大學(xué)，2014.

[7] 李尚健.應(yīng)用改進(jìn)的人工魚群算法求解混合流水車間調(diào)度問題[D]．重慶:重慶大學(xué)，2013.

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

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

[10] 馬亮，張廣明.基于遺傳算法的焊接生產(chǎn)線工位平衡規(guī)劃算法[J].自動化應(yīng)用,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

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

孟慶宇(1988—)，男，河北衡水人，天津工業(yè)大學(xué)碩士研究生，研究方向?yàn)闄C(jī)器人焊裝線控制方法及節(jié)拍優(yōu)化,(E-mail)mqy2007@163.com。

TH136;TG506

A