基于改進(jìn)遺傳算法的多目標(biāo)裝配線平衡優(yōu)化研究

李 明，包建軍，袁逸萍

（新疆大學(xué)機(jī)械工程學(xué)院，新疆 烏魯木齊 830047）

1 引言

隨著智能制造以及智慧裝配車間的不斷發(fā)展，離散制造企業(yè)生產(chǎn)模式由單品種大批量向小批量多品種轉(zhuǎn)變。

如今，生產(chǎn)裝配成本、產(chǎn)品質(zhì)量、成品交貨期決定了裝配企業(yè)生死存亡，而這些取決于作業(yè)車間工人是否配置合理、作業(yè)裝配生產(chǎn)線是否平衡、物流運(yùn)輸是否高效，即能否做到生產(chǎn)資源的合理配置和及時優(yōu)化。

對企業(yè)來說更須熟知裝配線平衡方法，裝配線平衡是指在滿足工序間優(yōu)先關(guān)系約束的前提下，將產(chǎn)品切割后的每個工序平均地分配到各個工位上[1]，通過裝配線平衡，有效的利用和分配工人和機(jī)械設(shè)備，使裝配生產(chǎn)線在加工時間上不產(chǎn)生閑置同時達(dá)到生產(chǎn)平衡。

當(dāng)前，國內(nèi)外許多學(xué)者對裝配線平衡優(yōu)化也進(jìn)行了大量研究。

文獻(xiàn)[2]基于改進(jìn)多目標(biāo)灰狼算法的裝配線平衡與預(yù)防維護(hù)集成優(yōu)化，綜合考慮了裝配線平衡和設(shè)備預(yù)防維護(hù)；文獻(xiàn)[3]針對裝配關(guān)系復(fù)雜性影響工人工作效率，進(jìn)而產(chǎn)生瓶頸工位的問題，提出一種考慮裝配關(guān)系復(fù)雜性的改進(jìn)型多目標(biāo)裝配線平衡優(yōu)化方法；文獻(xiàn)[4]為了更有效地減少工作站數(shù)目、提高裝配線效率，提出了一種基于多目標(biāo)混流裝配線平衡問題的方法；文獻(xiàn)[5]提出了多目標(biāo)模擬退火算法，以解決混流裝配線平衡排序優(yōu)化問題，并采用了一種新的接受策略，提高了算法尋優(yōu)能力。

綜上所述，裝配線再平衡問題是典型的多目標(biāo)優(yōu)化問題[6]，現(xiàn)有的處理方法大多采用單目標(biāo)優(yōu)化，此外在求解算法方面，傳統(tǒng)遺傳算法[7]的全局搜索能力不佳。

基于以上分析，為了幫助離散制造企業(yè)管理人員對裝配線進(jìn)行更加高效的平衡規(guī)劃，文章以最小化生產(chǎn)節(jié)拍、最大化產(chǎn)線平衡率和最小化平滑指數(shù)為優(yōu)化目標(biāo)建立裝配線再平衡優(yōu)化模型，采用改進(jìn)的遺傳算法對平衡模型進(jìn)行求解，并引入啟發(fā)式任務(wù)分配規(guī)則，提高了算法尋優(yōu)能力。最后以青貯機(jī)裝配線實(shí)際案例驗(yàn)證算法的可行性和有效性。

2 多目標(biāo)裝配線平衡優(yōu)化數(shù)學(xué)模型

這里研究的問題可簡化為：根據(jù)生產(chǎn)需求確定裝配線生產(chǎn)節(jié)拍的情況下，對于其最優(yōu)工位數(shù)進(jìn)行求解，從各種工序a,b生產(chǎn)組合中判斷的Op(k)總加工時間，進(jìn)行各工位的分配，確定工位k，分配完成時，達(dá)到CT，K和B的最優(yōu)。文章以滿足生產(chǎn)需求的最小節(jié)拍條件下最小化工位數(shù)K、最大平衡率B和最小平滑性指數(shù)為優(yōu)化目標(biāo)對裝配線平衡進(jìn)行優(yōu)化。

（1）優(yōu)化目標(biāo)1：Hmin。

在求解過程中，添加一個目標(biāo)，記為H：

式中：Bmax—平衡率的最大值。

（2）優(yōu)化目標(biāo)2：節(jié)拍時間小于等于生產(chǎn)所需求的節(jié)拍。

（3）優(yōu)化目標(biāo)3：平衡率B最大化。

在裝配過程中，工序數(shù)以及工位都不確定，當(dāng)工序變化時，工位數(shù)也隨之變化，總工位數(shù)也因此變化。目標(biāo)值可由工位數(shù)量K在不同的工序組合下尋找一組最優(yōu)的組裝組合，使工位數(shù)盡可能少，進(jìn)而得到最小的目標(biāo)值，這里生產(chǎn)線平衡率B的計算方式為：

式中：Ik相當(dāng)于k工位的空閑率；

各個工位Ik的平均值。

（4）優(yōu)化目標(biāo)4：平滑性指數(shù)最小化。

在優(yōu)化過程中，平滑性指數(shù)越小，表示裝配線總體狀態(tài)越優(yōu)。

式中：K—工位數(shù)；

k—工位索引，k=1,2,……，n；

a,b—工序索引，a,b=1,2,……，m；

Xak—第a個工序分配到工位k時為1，否則為0；

Yk—第k個工位在利用時為1，否則為0；

Ta—第a個作業(yè)的作業(yè)時間；

Op(k)—k工位可分配的操作集合；

CT—生產(chǎn)線節(jié)拍；

B—生產(chǎn)線平衡率；

Pred—作業(yè)在完成順序上的先后約束關(guān)系的集合。

3 改進(jìn)遺傳算法設(shè)計

3.1 編碼方法

基因串的編碼采用自然數(shù)編碼，編碼是長度為N的數(shù)據(jù)串。每一個基因的序號對應(yīng)作業(yè)工序的編號，基因座上的基因值標(biāo)識的是分配到的各個工位的工序編號，如圖1所示。

圖1 編碼方法示意圖Fig.1 Schematic Diagram of Coding Method

3.2 獲得初始種群的方法

將N個作業(yè)工序分配到K個工位上，需要考慮每個作業(yè)的約束工序和工序組合下的每個工位時間等于或小于生產(chǎn)節(jié)拍。這里使用了基于任務(wù)排序的種群初始化方法。

首先，任取出一個任務(wù)節(jié)點(diǎn)，放入空隊列，然后接下來在剩余節(jié)點(diǎn)中的任一節(jié)點(diǎn)上，按作業(yè)優(yōu)先順序?qū)⑵渌?jié)點(diǎn)放入（只能放在左邊就放在左邊，只能放在右邊就放在右邊，兩邊都能放，就任選一個位置放入），重復(fù)以上操作過程，直到隊列放滿位置。

3.3 交叉和變異

針對問題的特性和編碼方式，這里采用兩點(diǎn)交叉方法，如圖2所示。從原始種群中任意選兩個染色體為父代1和父代2，然后可生成兩個交叉點(diǎn)n1、n（21

圖2 交叉操作示意圖Fig.2 Cross Operation Schematic Diagram

任意產(chǎn)生一個染色體，將其作為變異的父代，然后隨機(jī)找個變異點(diǎn)1 ≤n1≤n。接下來首先根據(jù)作業(yè)優(yōu)先順序找到變異點(diǎn)的前約束工序，保持前約束工序和其前面工序基因排列順序不產(chǎn)生變化，然后找到變異點(diǎn)的后約束工序，保持后約束工序和其后面的工序基因排列順序不產(chǎn)生變化，將變異點(diǎn)放入染色體前約束工序和后約束工序間的任何基因點(diǎn)，最后組合以上三部分基因生成子代染色體排列順序，如圖3所示。

圖3 變異操作示意圖Fig.3 Sketch of Mutation Operation

3.4 適應(yīng)度

這里建立的優(yōu)化模型的目標(biāo)值為越小越好，個體的適應(yīng)度值與種群中個體的目標(biāo)值相悖，即目標(biāo)值越小，其對應(yīng)的適應(yīng)度值越大[8]。

因此，文章提出了如下的適應(yīng)度函數(shù)：

式中：K—個體對應(yīng)的目標(biāo)函數(shù)；u—不小于maxK的常數(shù)。

4 實(shí)例分析

以農(nóng)機(jī)典型產(chǎn)品青貯機(jī)裝配線為研究對象驗(yàn)證算法的可靠性和有效性，首先需要對裝配線參數(shù)進(jìn)行收集，繪制產(chǎn)品的作業(yè)優(yōu)先順序圖并計算理論生產(chǎn)節(jié)拍。

4.1 作業(yè)優(yōu)先順序圖

繪制青貯機(jī)裝配線的作業(yè)優(yōu)先圖需要兩個不可缺的因素，第一需要對工位進(jìn)行編號，并將工位切割為多個工序；第二需要收集各工序的實(shí)際作業(yè)時間[9]。

運(yùn)用工業(yè)工程中的秒表法測量青貯機(jī)裝配線各工序工時，進(jìn)行裝配線平衡分析，結(jié)果，如表1所示。

表1 青貯機(jī)裝配線時間分析Tab.1 Time Analysis of Y1 Production Line

由此繪制青貯機(jī)裝配的作業(yè)優(yōu)先順序圖，如圖4 所示。其中，圓圈代表每個工序，圓圈上的數(shù)字表示各工序的標(biāo)準(zhǔn)作業(yè)時間，箭頭則表示作業(yè)的先后約束關(guān)系。

圖4 青貯機(jī)作業(yè)優(yōu)先順序圖Fig.4 Priority Chart of Silage Harvester Operation

由表1計算出當(dāng)前裝配線平衡率B：

根據(jù)過去歷史銷售數(shù)據(jù)和銷售預(yù)測，目前實(shí)際每天需要生產(chǎn)數(shù)量為10件/shift，由此計算出理論生產(chǎn)節(jié)拍：

4.2 平衡方案求解

基于上述算法思路和流程，首先采用通用仿真工具M(jìn)AT‐LAB 進(jìn)行了算法實(shí)現(xiàn)，在程序中取生產(chǎn)節(jié)拍TT=54min，樣本數(shù)（種群大?。﹕=100，進(jìn)化代數(shù)G=300，選擇的最優(yōu)個體數(shù)目K=15，交叉的概率Pc=0.8，變異的概率Pm=0.06。迭代結(jié)果和工位甘特圖，如圖5~圖6所示。

圖5 迭代次數(shù)Fig.5 Number of Iterations

圖6 青貯機(jī)裝配工位Gantt圖Fig.6 Gantt Diagram of Silage Harvester Assembly Station

4.3 仿真結(jié)果分析

根據(jù)上述優(yōu)化結(jié)果，工位數(shù)為15時的青貯機(jī)裝配線平衡方案，如表2所示。

表2 工位數(shù)為15的裝配線平衡方案（節(jié)拍時間=52min）Tab.2 Balancing Scheme with Working Number 15 of Assembly Line（TT = 52 min）

從計算結(jié)果可以得出：優(yōu)化后青貯機(jī)裝配線工位數(shù)為15時的生產(chǎn)節(jié)拍CT、裝配線平衡率B、Hmin、最小平滑性指數(shù)分別為：

優(yōu)化后實(shí)際節(jié)拍小于理論生產(chǎn)節(jié)拍，可以滿足生產(chǎn)的需求。通過優(yōu)化，青貯機(jī)裝配線總平衡率為由64.4%提高到90.6%，提高了26.2%，同時優(yōu)化目標(biāo)Hmin和平滑指數(shù)均為最小，裝配線平衡優(yōu)化的同時提高了整體的生產(chǎn)效率。

5 結(jié)束語

對于離散裝配企業(yè)，裝配線平衡的優(yōu)化可以有效提高生產(chǎn)效率以及產(chǎn)品質(zhì)量。文章以最小化生產(chǎn)節(jié)拍、最大化產(chǎn)線平衡率和最小化平滑指數(shù)為優(yōu)化目標(biāo)建立裝配線再平衡優(yōu)化模型，并采用改進(jìn)的遺傳算法對平衡模型進(jìn)行求解，并引入啟發(fā)式任務(wù)分配規(guī)則，提高了算法尋優(yōu)能力。最后以青貯機(jī)裝配線為實(shí)例驗(yàn)證算法的可行性和有效性。

通過優(yōu)化，青貯機(jī)裝配線平衡率由64.4%提高到90.6%，提高了26.2%，同時各裝配工位負(fù)荷更加均衡，提升了作業(yè)人員積極性，也極大減少了在制品堆積。結(jié)果表明，運(yùn)用改進(jìn)遺傳算法可有效解決農(nóng)機(jī)企業(yè)裝配線平衡問題。