基于改進遺傳算法的多目標裝配線平衡優化研究

李 明，包建軍，袁逸萍

（新疆大學機械工程學院，新疆 烏魯木齊 830047）

1 引言

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

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

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

當前，國內外許多學者對裝配線平衡優化也進行了大量研究。

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

綜上所述，裝配線再平衡問題是典型的多目標優化問題[6]，現有的處理方法大多采用單目標優化，此外在求解算法方面，傳統遺傳算法[7]的全局搜索能力不佳。

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

2 多目標裝配線平衡優化數學模型

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

（1）優化目標1：Hmin。

在求解過程中，添加一個目標，記為H：

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

（2）優化目標2：節拍時間小于等于生產所需求的節拍。

（3）優化目標3：平衡率B最大化。

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

式中：Ik相當于k工位的空閑率；

各個工位Ik的平均值。

（4）優化目標4：平滑性指數最小化。

在優化過程中，平滑性指數越小，表示裝配線總體狀態越優。

式中：K—工位數；

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

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

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

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

Ta—第a個作業的作業時間；

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

CT—生產線節拍；

B—生產線平衡率；

Pred—作業在完成順序上的先后約束關系的集合。

3 改進遺傳算法設計

3.1 編碼方法

基因串的編碼采用自然數編碼，編碼是長度為N的數據串。每一個基因的序號對應作業工序的編號，基因座上的基因值標識的是分配到的各個工位的工序編號，如圖1所示。

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

3.2 獲得初始種群的方法

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

首先，任取出一個任務節點，放入空隊列，然后接下來在剩余節點中的任一節點上，按作業優先順序將其他節點放入（只能放在左邊就放在左邊，只能放在右邊就放在右邊，兩邊都能放，就任選一個位置放入），重復以上操作過程，直到隊列放滿位置。

3.3 交叉和變異

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

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

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

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

3.4 適應度

這里建立的優化模型的目標值為越小越好，個體的適應度值與種群中個體的目標值相悖，即目標值越小，其對應的適應度值越大[8]。

因此，文章提出了如下的適應度函數：

式中：K—個體對應的目標函數；u—不小于maxK的常數。

4 實例分析

以農機典型產品青貯機裝配線為研究對象驗證算法的可靠性和有效性，首先需要對裝配線參數進行收集，繪制產品的作業優先順序圖并計算理論生產節拍。

4.1 作業優先順序圖

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

運用工業工程中的秒表法測量青貯機裝配線各工序工時，進行裝配線平衡分析，結果，如表1所示。

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

由此繪制青貯機裝配的作業優先順序圖，如圖4 所示。其中，圓圈代表每個工序，圓圈上的數字表示各工序的標準作業時間，箭頭則表示作業的先后約束關系。

圖4 青貯機作業優先順序圖Fig.4 Priority Chart of Silage Harvester Operation

由表1計算出當前裝配線平衡率B：

根據過去歷史銷售數據和銷售預測，目前實際每天需要生產數量為10件/shift，由此計算出理論生產節拍：

4.2 平衡方案求解

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

圖5 迭代次數Fig.5 Number of Iterations

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

4.3 仿真結果分析

根據上述優化結果，工位數為15時的青貯機裝配線平衡方案，如表2所示。

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

從計算結果可以得出：優化后青貯機裝配線工位數為15時的生產節拍CT、裝配線平衡率B、Hmin、最小平滑性指數分別為：

優化后實際節拍小于理論生產節拍，可以滿足生產的需求。通過優化，青貯機裝配線總平衡率為由64.4%提高到90.6%，提高了26.2%，同時優化目標Hmin和平滑指數均為最小，裝配線平衡優化的同時提高了整體的生產效率。

5 結束語

對于離散裝配企業，裝配線平衡的優化可以有效提高生產效率以及產品質量。文章以最小化生產節拍、最大化產線平衡率和最小化平滑指數為優化目標建立裝配線再平衡優化模型，并采用改進的遺傳算法對平衡模型進行求解，并引入啟發式任務分配規則，提高了算法尋優能力。最后以青貯機裝配線為實例驗證算法的可行性和有效性。

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