乘用車發動機裝配線多目標工藝優化

宓為建， 陳竹青， 舒帆

(上海海事大學 物流工程學院，上海 201306)

0 引 言

隨著現代工業的不斷發展，乘用車的保有量與日俱增，乘用車制造企業在不斷追求高產量的同時，愈加注重管理水平的改善.發動機質量是關系到乘用車整體質量的重要因素，因此發動機裝配線的工藝問題一直是研究熱點.

發動機裝配線工藝問題是如何將生產發動機的總流程合理有效地分配到裝配線的各個工位上.需考慮的因素很多，如發動機工位的負荷平衡、人機效率的綜合平衡、工具工裝的配置等.工藝優化問題實質是組合優化問題，由產品設計、工藝設計和制造過程技術決定的作業元素之間先后關系的多種變化，使工藝問題變得非常復雜.[1]

目前，關于發動機裝配線工藝合理性的研究集中在裝配線平衡問題上，以裝配線各個工作站的閑置時間最接近為目標，但在追求高平衡率的同時，也可能以損失產能和增加成本為代價.因此，迫切需要從多角度綜合評價發動機裝配線工藝的優劣，構建多目標的工藝優化模型并進行求解.

裝配線平衡問題分為兩類.[2]毛凌翔等[3]和范維博等[4]以最小化工位數量為目標研究第一類平衡問題，力求降低生產線的構建成本；魯建廈等[5]針對第二類平衡問題進行分析，旨在最小化生產節拍.

兩類平衡問題從不同角度、以單一目標為考量進行研究.然而乘用車發動機裝配線具有裝配工序繁雜、工位數量多、批量要求大、工裝工具配備數量大等特點.以工裝工具為例，如果工藝設計能減少某些工裝工具的配置，可以節省的成本十分可觀.基于以上原因，發動機裝配線的工藝設計和優化僅考慮平衡問題是不夠的，需要綜合考慮各個影響因素來研究乘用車發動機裝配線的多目標優化問題.

針對裝配線工藝優化這類組合優化問題，KLEIN等[6]利用分支定界法進行求解.分支定界法屬于數學規劃法，僅限于求解小規模問題，對于工序繁多的大規模多目標乘用車發動機裝配線而言，則難以求解.范維博等[4]提出運用遺傳算法(Genetic Algorithm,GA)求解，但由于乘用車發動機工序過多、工序間優先順序多變、GA收斂速度較快等，容易陷入局部最優解.

基于此，結合發動機企業工藝設計和優化的實際需求，考慮產能、平衡、成本3大要素，建立乘用車發動機裝配線多目標數學模型.同時，針對乘用車發動機裝配線的特點，采用結合模擬退火(Simulated Annealing,SA)算法的GASA算法:既可保留GA收斂速度快的特點，又具備SA算法求解能力強的優勢，以提高生產效率、降低生產成本為目標，為解決大規模乘用車發動機裝配線問題提供可行方案.

1 發動機裝配線多目標工藝優化模型構建

1.1 模型假設

1.2 模型建立

模型選取產能、平衡、成本3個指標，構建發動機裝配線多目標工藝優化模型，目標函數為

(1)

工序排列以產品的加工順序為導向，工藝之間的優先關系必須滿足，從而形成發動機裝配線多目標工藝優化模型的約束條件.加工順序可表示成工序優先關系矩陣：

優先關系矩陣說明：(1)方陣的行數為工序個數；(2)方陣中元素

2 發動機裝配線多目標工藝優化模型求解

2.1 GASA算法設計

不少專家學者使用啟發式算法對裝配線問題進行求解，如蟻群算法[3]，GA[9-10]，粒子群算法[11]，SA算法[12-13].GA具有收斂速度較快、并行能力強等優點，但存在“早熟”這一缺陷.由于乘用車發動機裝配線工序繁多，傳統GA會遺漏最優解，因此需要提高其搜索能力.SA算法思想與物理退火思想近似，具有初始解依賴性弱、搜索能力強等特點，但其運行速度慢.[14]根據上述特征，本文將SA算法融入GA中，在保證求解速度的前提下獲取最優解.GASA算法流程見圖1.

圖1 GASA算法流程

在GA中嵌入使用SA算法[15]，可選擇性地拒絕基因不符合要求的后代，確保最優解被保留到最后，其實現步驟如下：

步驟1初始化.設定初始溫度、終止溫度、終止次數等參數.

步驟2變異[16].可隨機產生一個變異點，把父代染色體分成兩部分.保留前部分，將后部分的染色體根據優先矩陣重新排列組合，得到子代染色體.因為后半部分染色體的產生取決于優先矩陣，所以可以保證染色體的可行性.

步驟3判斷.分別計算父代及子代染色體的能量值，記為E1和E2.若E2-E1<0，轉步驟6；否則，轉步驟4.

步驟4概率計算.根據Metropolis準則，粒子在溫度T時趨于平衡的概率為P=e-ΔE/(KT)，其中E為溫度T時的內能，ΔE為內能改變量，k為Boltzmann常數.

步驟5判斷.隨機產生一個范圍在0～1之間的數，若大于上述概率，轉步驟7；否則，轉步驟6.

步驟6接受變異后的子代染色體取代父代染色體，轉步驟2，達到內循環終止條件后轉步驟8.

步驟7拒絕變異后的子代染色體，轉步驟2，達到內循環終止條件后轉步驟8.

步驟8根據降溫幅度產生新溫度，循環上述步驟，到達外循環終止條件后停止.

2.2 基于GASA算法的模型求解過程

2.2.1 編碼與譯碼

首先針對工藝優化對象進行遺傳算法的編碼.工藝優化主要解決兩方面問題：排列工序及分配工位.編碼用于解決工序排列的表達方式.考慮到乘用車發動機工序數量多，為了便于表達，本文采用自然數編碼[17]：將每個工序唯一對應一個自然數，則自然數的排列順序(稱為染色體)為加工工序的先后次序.例：“1 3 2 4 6 8 7 5”即為一條染色體，表示先完成工序1，然后依次完成工序3，2，4，6，8，7，最后完成工序5.根據編碼方式及關系矩陣，計算機隨機產生一組群體，群體中每條染色體都是問題的可行解.

譯碼用于處理工位分配，譯碼方式如下：

步驟1計算平均加工時間Tavg，取Tavg及maxti中的較大值為最小理論節拍,

(2)

式中：m為工序數量；ti為第i個工序的耗時；n為工位數量.

步驟2以最小理論節拍為依據，將工序分配到n-1個工位，剩余工位全部分配至第n個工位.

步驟3計算每個工位的耗時Tj1(j1=1,2,…,n)以及經過增量處理的耗時Tj2=Tj1+tj1+1(j1=1,2,…,n;tj1+1為分配至第j1+1個工位的第1個工序的時間).

步驟4計算maxTj1以及minTj2，若maxTj1≤minTj2，那么minTj2為最小節拍，此分配方案為最優分配；否則以minTj2為最小理論節拍，返回步驟2.

2.2.2 適應度計算及染色體選擇

適應度函數的建立取決于目標函數，根據前文所述，目標函數由3部分組成，因此適應度函數也相應分為3塊,

(3)

式中：φ1，φ2，φ3與式(1)目標函數一致；α1，β1，γ1分別為各部分適應值的權重，與目標函數一樣，采用自適應權重法.

本文采用輪盤賭方法[17]進行染色體的選擇.根據個體的適應度值計算其選擇概率

式中：Pi為適應度值選擇概率；fi為某個染色體的適應度值；N為種群規模.

2.2.3 交叉與變異

交叉的目的在于產生更優良的染色體，其關鍵之處在于如何保持染色體的可行性，即交叉后工序的排列仍然符合工序優先關系矩陣.

本文采用兩點交叉法，交叉過程如下：

步驟1隨機產生兩條父代染色體.

步驟2隨機產生兩個交叉點，將每條父代染色體分成3段.

步驟3保留第1段和第3段染色體，將一條父代染色體中間部分的工序按其在另一條父代染色體中的順序進行排列，形成子代染色體.

從步驟3可以發現，由于交叉后子代染色體中間部分的排列順序來源于交叉前父代染色體，子代染色體為可行染色體.

接著，按照上文算法設計所述，結合SA算法進行染色體的變異操作，其中內循環終止條件為迭代到一定的次數，外循環終止條件為達到設定的最低溫度.經過上述步驟，新種群將取代舊種群.

3 發動機裝配線多目標工藝優化案例

以B企業乘用車發動機裝配線的核心部分為例，現有5個工位，共需經過38道工序，其先后順序、工序時間、配備設備數見圖2.

圖2中，圓圈內的數字表示工序編號，圓圈外的數字表示工序時間，灰色填充表示該工序需要耗資設備才能完成.

在MATLAB環境下，分別用GA和GASA算法進行求解，程序運行圖見圖3和4.

圖2 加工工序

圖3 GA運行結果 圖4 GASA算法運行結果

圖3和4中每根柱子表示每個工位的耗時.對比兩張圖可以發現GASA算法得到的柱狀圖的平衡性更佳.

案例結果見表1.從表1可以發現：GASA算法得到的生產節拍小于GA，因而產能增加2.04%；均衡率(方差)下降3.46，能有效平衡工位間的負荷.從而可以證明，由于結合SA算法，GASA算法可避免GA“早熟”的缺陷，跳出局部最優解找到全局最優解.

GASA算法的迭代圖見圖5.

圖5表明，當迭代到一定次數時，適應度值趨于一個值，GASA算法具有很好的收斂性.

表1 案例結果

圖5 GASA算法的迭代圖

4 結束語

鑒于乘用車發動機裝配線平衡所涉及的多個目標之間常常相互沖突，單獨優化某一目標往往會造成其他目標的劣化，本文構建考慮產能、平衡、成本的乘用車發動機裝配線多目標工藝優化數學模型，并采用GASA算法進行求解.實例驗證表明，該模型及算法能在一定程度上優化大規模乘用車發動機裝配線的工藝，提高工藝的綜合性能.

參考文獻：

[1] 彭慧, 徐克林, 侶占華. 采用遺傳算法的混流裝配線平衡多目標優化[J]. 現代制造工程, 2011(11): 49-55.

[2] 肖中華. 基于改進遺傳算法的汽車裝配線平衡問題研究[D]. 武漢: 武漢科技大學, 2010.

[3] 毛凌翔, 鄭永前. 蟻群算法求解裝配線平衡第一類問題[J]. 計算機系統應用, 2010, 19(1): 140-143.

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

[5] 魯建廈, 蔣玲玲, 李修琳. 基于混合粒子群算法求解裝配線第二類平衡問題[J]. 中國機械工程, 2010, 21(4): 420-424.

[6] KLEIN R, SCHOLL A. Maximizing the production rate in simple line balancing: a branch and bound procedure[J]. Eur J Operational Res, 1996, 91(2): 367-385.

[7] 玄光男, 程潤偉. 遺傳算法與工程優化[M]. 北京: 清華大學出版社, 2004: 97-100.

[8] 陳星宇. 基于改進遺傳算法的裝配生產線平衡技術研究[D]. 上海: 上海交通大學, 2011.

[9] 宋華明, 韓玉啟. 基于遺傳算法的裝配線平衡[J]. 系統工程, 2002, 20(1): 87-91.

[10] 王紅軍, 張懷存. 基于遺傳的變速箱裝配線平衡研究[J]. 微計算機信息, 2009, 25(1): 306-308.

[11] 陳永卿. 基于混合進化算法的裝配線平衡問題研究[D]. 杭州: 浙江大學, 2008.

[12] SURESH G, SAHU S. Stochastic assembly line balancing using simulated annealing[J]. Int J Production Res, 1994, 32(8): 1801-1810.

[13] 徐天. 裝配生產線平衡分析與研究[D]. 上海: 上海交通大學, 2011.

[14] 王蕓鳳, 劉明周, 于寶證. 求解裝配線平衡問題的混合遺傳算法[J]. 合肥: 合肥工業大學學報, 2005, 28(6): 616-619.

[15] 李莉, 丁以中. 軸輻式快遞網絡的樞紐選址和分配優化[J]. 上海海事大學學報, 2012, 33(2): 33-41.

[16] 郭貝貝, 靳志宏. 現實約束條件下的集裝箱多箱裝載優化[J]. 上海海事大學學報, 2009, 30(2): 8-15.

[17] 何軍良, 宓為建. 基于分布式混合遺傳算法的動態泊位分配策略與仿真[J]. 上海海事大學學報, 2012, 33(2): 52-58.