宓為建， 陳竹青， 舒帆

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

0 引 言

隨著現(xiàn)代工業(yè)的不斷發(fā)展，乘用車的保有量與日俱增，乘用車制造企業(yè)在不斷追求高產(chǎn)量的同時(shí)，愈加注重管理水平的改善.發(fā)動(dòng)機(jī)質(zhì)量是關(guān)系到乘用車整體質(zhì)量的重要因素，因此發(fā)動(dòng)機(jī)裝配線的工藝問(wèn)題一直是研究熱點(diǎn).

發(fā)動(dòng)機(jī)裝配線工藝問(wèn)題是如何將生產(chǎn)發(fā)動(dòng)機(jī)的總流程合理有效地分配到裝配線的各個(gè)工位上.需考慮的因素很多，如發(fā)動(dòng)機(jī)工位的負(fù)荷平衡、人機(jī)效率的綜合平衡、工具工裝的配置等.工藝優(yōu)化問(wèn)題實(shí)質(zhì)是組合優(yōu)化問(wèn)題，由產(chǎn)品設(shè)計(jì)、工藝設(shè)計(jì)和制造過(guò)程技術(shù)決定的作業(yè)元素之間先后關(guān)系的多種變化，使工藝問(wèn)題變得非常復(fù)雜.[1]

目前，關(guān)于發(fā)動(dòng)機(jī)裝配線工藝合理性的研究集中在裝配線平衡問(wèn)題上，以裝配線各個(gè)工作站的閑置時(shí)間最接近為目標(biāo)，但在追求高平衡率的同時(shí)，也可能以損失產(chǎn)能和增加成本為代價(jià).因此，迫切需要從多角度綜合評(píng)價(jià)發(fā)動(dòng)機(jī)裝配線工藝的優(yōu)劣，構(gòu)建多目標(biāo)的工藝優(yōu)化模型并進(jìn)行求解.

裝配線平衡問(wèn)題分為兩類.[2]毛凌翔等[3]和范維博等[4]以最小化工位數(shù)量為目標(biāo)研究第一類平衡問(wèn)題，力求降低生產(chǎn)線的構(gòu)建成本；魯建廈等[5]針對(duì)第二類平衡問(wèn)題進(jìn)行分析，旨在最小化生產(chǎn)節(jié)拍.

兩類平衡問(wèn)題從不同角度、以單一目標(biāo)為考量進(jìn)行研究.然而乘用車發(fā)動(dòng)機(jī)裝配線具有裝配工序繁雜、工位數(shù)量多、批量要求大、工裝工具配備數(shù)量大等特點(diǎn).以工裝工具為例，如果工藝設(shè)計(jì)能減少某些工裝工具的配置，可以節(jié)省的成本十分可觀.基于以上原因，發(fā)動(dòng)機(jī)裝配線的工藝設(shè)計(jì)和優(yōu)化僅考慮平衡問(wèn)題是不夠的，需要綜合考慮各個(gè)影響因素來(lái)研究乘用車發(fā)動(dòng)機(jī)裝配線的多目標(biāo)優(yōu)化問(wèn)題.

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

基于此，結(jié)合發(fā)動(dòng)機(jī)企業(yè)工藝設(shè)計(jì)和優(yōu)化的實(shí)際需求，考慮產(chǎn)能、平衡、成本3大要素，建立乘用車發(fā)動(dòng)機(jī)裝配線多目標(biāo)數(shù)學(xué)模型.同時(shí)，針對(duì)乘用車發(fā)動(dòng)機(jī)裝配線的特點(diǎn)，采用結(jié)合模擬退火(Simulated Annealing,SA)算法的GASA算法:既可保留GA收斂速度快的特點(diǎn)，又具備SA算法求解能力強(qiáng)的優(yōu)勢(shì)，以提高生產(chǎn)效率、降低生產(chǎn)成本為目標(biāo)，為解決大規(guī)模乘用車發(fā)動(dòng)機(jī)裝配線問(wèn)題提供可行方案.

1 發(fā)動(dòng)機(jī)裝配線多目標(biāo)工藝優(yōu)化模型構(gòu)建

1.1 模型假設(shè)

1.2 模型建立

模型選取產(chǎn)能、平衡、成本3個(gè)指標(biāo)，構(gòu)建發(fā)動(dòng)機(jī)裝配線多目標(biāo)工藝優(yōu)化模型，目標(biāo)函數(shù)為

(1)

工序排列以產(chǎn)品的加工順序?yàn)閷?dǎo)向，工藝之間的優(yōu)先關(guān)系必須滿足，從而形成發(fā)動(dòng)機(jī)裝配線多目標(biāo)工藝優(yōu)化模型的約束條件.加工順序可表示成工序優(yōu)先關(guān)系矩陣：

優(yōu)先關(guān)系矩陣說(shuō)明：(1)方陣的行數(shù)為工序個(gè)數(shù)；(2)方陣中元素

2 發(fā)動(dòng)機(jī)裝配線多目標(biāo)工藝優(yōu)化模型求解

2.1 GASA算法設(shè)計(jì)

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

圖1 GASA算法流程

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

步驟1初始化.設(shè)定初始溫度、終止溫度、終止次數(shù)等參數(shù).

步驟2變異[16].可隨機(jī)產(chǎn)生一個(gè)變異點(diǎn)，把父代染色體分成兩部分.保留前部分，將后部分的染色體根據(jù)優(yōu)先矩陣重新排列組合，得到子代染色體.因?yàn)楹蟀氩糠秩旧w的產(chǎn)生取決于優(yōu)先矩陣，所以可以保證染色體的可行性.

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

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

步驟5判斷.隨機(jī)產(chǎn)生一個(gè)范圍在0～1之間的數(shù)，若大于上述概率，轉(zhuǎn)步驟7；否則，轉(zhuǎn)步驟6.

步驟6接受變異后的子代染色體取代父代染色體，轉(zhuǎn)步驟2，達(dá)到內(nèi)循環(huán)終止條件后轉(zhuǎn)步驟8.

步驟7拒絕變異后的子代染色體，轉(zhuǎn)步驟2，達(dá)到內(nèi)循環(huán)終止條件后轉(zhuǎn)步驟8.

步驟8根據(jù)降溫幅度產(chǎn)生新溫度，循環(huán)上述步驟，到達(dá)外循環(huán)終止條件后停止.

2.2 基于GASA算法的模型求解過(guò)程

2.2.1 編碼與譯碼

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

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

步驟1計(jì)算平均加工時(shí)間Tavg，取Tavg及maxti中的較大值為最小理論節(jié)拍,

(2)

式中：m為工序數(shù)量；ti為第i個(gè)工序的耗時(shí)；n為工位數(shù)量.

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

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

步驟4計(jì)算maxTj1以及minTj2，若maxTj1≤minTj2，那么minTj2為最小節(jié)拍，此分配方案為最優(yōu)分配；否則以minTj2為最小理論節(jié)拍，返回步驟2.

2.2.2 適應(yīng)度計(jì)算及染色體選擇

適應(yīng)度函數(shù)的建立取決于目標(biāo)函數(shù)，根據(jù)前文所述，目標(biāo)函數(shù)由3部分組成，因此適應(yīng)度函數(shù)也相應(yīng)分為3塊,

(3)

式中：φ1，φ2，φ3與式(1)目標(biāo)函數(shù)一致；α1，β1，γ1分別為各部分適應(yīng)值的權(quán)重，與目標(biāo)函數(shù)一樣，采用自適應(yīng)權(quán)重法.

本文采用輪盤賭方法[17]進(jìn)行染色體的選擇.根據(jù)個(gè)體的適應(yīng)度值計(jì)算其選擇概率

式中：Pi為適應(yīng)度值選擇概率；fi為某個(gè)染色體的適應(yīng)度值；N為種群規(guī)模.

2.2.3 交叉與變異

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

本文采用兩點(diǎn)交叉法，交叉過(guò)程如下：

步驟1隨機(jī)產(chǎn)生兩條父代染色體.

步驟2隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)，將每條父代染色體分成3段.

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

從步驟3可以發(fā)現(xiàn)，由于交叉后子代染色體中間部分的排列順序來(lái)源于交叉前父代染色體，子代染色體為可行染色體.

接著，按照上文算法設(shè)計(jì)所述，結(jié)合SA算法進(jìn)行染色體的變異操作，其中內(nèi)循環(huán)終止條件為迭代到一定的次數(shù)，外循環(huán)終止條件為達(dá)到設(shè)定的最低溫度.經(jīng)過(guò)上述步驟，新種群將取代舊種群.

3 發(fā)動(dòng)機(jī)裝配線多目標(biāo)工藝優(yōu)化案例

以B企業(yè)乘用車發(fā)動(dòng)機(jī)裝配線的核心部分為例，現(xiàn)有5個(gè)工位，共需經(jīng)過(guò)38道工序，其先后順序、工序時(shí)間、配備設(shè)備數(shù)見(jiàn)圖2.

圖2中，圓圈內(nèi)的數(shù)字表示工序編號(hào)，圓圈外的數(shù)字表示工序時(shí)間，灰色填充表示該工序需要耗資設(shè)備才能完成.

在MATLAB環(huán)境下，分別用GA和GASA算法進(jìn)行求解，程序運(yùn)行圖見(jiàn)圖3和4.

圖2 加工工序

圖3 GA運(yùn)行結(jié)果 圖4 GASA算法運(yùn)行結(jié)果

圖3和4中每根柱子表示每個(gè)工位的耗時(shí).對(duì)比兩張圖可以發(fā)現(xiàn)GASA算法得到的柱狀圖的平衡性更佳.

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

GASA算法的迭代圖見(jiàn)圖5.

圖5表明，當(dāng)?shù)揭欢ù螖?shù)時(shí)，適應(yīng)度值趨于一個(gè)值，GASA算法具有很好的收斂性.

表1 案例結(jié)果

圖5 GASA算法的迭代圖

4 結(jié)束語(yǔ)

鑒于乘用車發(fā)動(dòng)機(jī)裝配線平衡所涉及的多個(gè)目標(biāo)之間常常相互沖突，單獨(dú)優(yōu)化某一目標(biāo)往往會(huì)造成其他目標(biāo)的劣化，本文構(gòu)建考慮產(chǎn)能、平衡、成本的乘用車發(fā)動(dòng)機(jī)裝配線多目標(biāo)工藝優(yōu)化數(shù)學(xué)模型，并采用GASA算法進(jìn)行求解.實(shí)例驗(yàn)證表明，該模型及算法能在一定程度上優(yōu)化大規(guī)模乘用車發(fā)動(dòng)機(jī)裝配線的工藝，提高工藝的綜合性能.

參考文獻(xiàn)：

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

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

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

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

[5] 魯建廈, 蔣玲玲, 李修琳. 基于混合粒子群算法求解裝配線第二類平衡問(wèn)題[J]. 中國(guó)機(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] 玄光男, 程潤(rùn)偉. 遺傳算法與工程優(yōu)化[M]. 北京: 清華大學(xué)出版社, 2004: 97-100.

[8] 陳星宇. 基于改進(jìn)遺傳算法的裝配生產(chǎn)線平衡技術(shù)研究[D]. 上海: 上海交通大學(xué), 2011.

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

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

[11] 陳永卿. 基于混合進(jìn)化算法的裝配線平衡問(wèn)題研究[D]. 杭州: 浙江大學(xué), 2008.

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

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

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

[15] 李莉, 丁以中. 軸輻式快遞網(wǎng)絡(luò)的樞紐選址和分配優(yōu)化[J]. 上海海事大學(xué)學(xué)報(bào), 2012, 33(2): 33-41.

[16] 郭貝貝, 靳志宏. 現(xiàn)實(shí)約束條件下的集裝箱多箱裝載優(yōu)化[J]. 上海海事大學(xué)學(xué)報(bào), 2009, 30(2): 8-15.

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