附帶翻轉(zhuǎn)工位雙邊裝配線蟻群算法優(yōu)化設(shè)計

朱小平，張則強

1.浙江交通職業(yè)技術(shù)學(xué)院機電學(xué)院，杭州 311112

2.西南交通大學(xué)機械工程學(xué)院，成都 610031

附帶翻轉(zhuǎn)工位雙邊裝配線蟻群算法優(yōu)化設(shè)計

朱小平1，張則強2

1.浙江交通職業(yè)技術(shù)學(xué)院機電學(xué)院，杭州 311112

2.西南交通大學(xué)機械工程學(xué)院，成都 610031

雙邊裝配線應(yīng)用廣泛，翻轉(zhuǎn)工位操作能有效降低部分零件裝配難度與操作風(fēng)險，但增加了設(shè)計難度。基于此，研究了附帶翻轉(zhuǎn)工位操作的挖掘機底盤雙邊裝配線規(guī)劃設(shè)計問題，針對該問題提出了一種改進蟻群算法求解。給出了問題求解的啟發(fā)式任務(wù)分配規(guī)則，提出可采用啟發(fā)式任務(wù)選擇規(guī)則以提高算法收斂速率。進而分析某型挖掘機底盤裝配線得出先后約束關(guān)系圖，將問題抽象為雙邊裝配線優(yōu)化設(shè)計問題。隨后，采用兩種蟻群算法進行附帶翻轉(zhuǎn)工位的裝配線優(yōu)化，分析比較了兩種算法因結(jié)構(gòu)差異對優(yōu)化結(jié)果所造成的影響。

蟻群算法；雙邊裝配線；翻轉(zhuǎn)工位；優(yōu)化；群智能

1 引言

在大型機械裝備中，由于多個部件可在兩側(cè)同時裝配，可有效縮短裝配時間，因此對如何有效組織和設(shè)計雙邊裝配線工位提出了要求，雙邊裝配線平衡問題（Two-sided Assembly Lines Balancing Problem，TALBP）也隨之產(chǎn)生。雙邊裝配線與單邊裝配線相比具有很多優(yōu)點：如可壓縮裝配線長度、減少配件運輸距離與工人移動成本、降低工位布置成本等[1-2]，因此被廣泛應(yīng)用于汽車工業(yè)、工程機械、武器裝備等中大型產(chǎn)品的裝配生產(chǎn)過程，具有顯著的經(jīng)濟效益。履帶挖掘機的底盤對稱規(guī)則，行走機構(gòu)、控制、制動系統(tǒng)對稱分布兩側(cè)，非常適合采用雙邊裝配線進行組裝。

雙邊裝配線優(yōu)點眾多，但由于其設(shè)計與布局形式較單邊裝配線復(fù)雜，具體表現(xiàn)在：TALBP裝配線布局需考慮裝配任務(wù)的左右操作方位；更需要注意不同側(cè)裝配任務(wù)之間的先后約束關(guān)系。由于雙邊裝配線的應(yīng)用前景和設(shè)計難度，近年來受到了企業(yè)界和學(xué)術(shù)界的關(guān)注[3-4]。而裝配線平衡問題作為NP-Hard型難題[5]，難以在合理的時間內(nèi)精確求解，因此常采用啟發(fā)式算法求解。目前國際上對標準的TALBP問題，已經(jīng)有Kim等[6]提出的一種遺傳算法；吳爾飛等[7]提出的一種基于任務(wù)序列的改進遺傳算法；?zcan和Toklu[8]提出的禁忌搜索算法等；且近期有逐漸向多目標優(yōu)化方向發(fā)展趨勢[9-10]。而對于貼近實際應(yīng)用的TALBP問題，如附帶區(qū)域約束的TALBP，由于更加復(fù)雜，目前能提供的文獻較少[5，11-12]。由模仿蟻群覓食行為發(fā)展起來的蟻群算法（Ant Colony Optimization，ACO），在求解簡單裝配線平衡問題表現(xiàn)出了優(yōu)異性能[13-14]，且已成功應(yīng)用至含區(qū)域約束問題的TALBP[5]。

前述所涉及的問題均集中于研究常規(guī)雙邊裝配線平衡問題，而實際裝配線存在著一類特殊裝配約束。以某挖掘機底盤裝配線為例，該裝配線存在某些特殊裝配任務(wù)，為方便裝配作業(yè)需翻轉(zhuǎn)整個工作臺；因此，要在此任務(wù)裝配前增加翻轉(zhuǎn)作業(yè)時間，而翻轉(zhuǎn)作業(yè)過程需中斷裝配作業(yè)，增加判別翻轉(zhuǎn)時前序裝配任務(wù)是否完畢，同時需增加判別后續(xù)分配任務(wù)是否為非特殊型任務(wù)，是否需要再次翻轉(zhuǎn)作業(yè)。對于此問題，求解關(guān)鍵在于將此特殊型裝配任務(wù)合理聚集，減少翻轉(zhuǎn)作業(yè)時間。而當(dāng)前，對于包含此類特殊裝配任務(wù)的TALBP問題，尚未有相關(guān)求解算法。基于此，本文開展該問題研究。

針對該新問題，結(jié)合TALBP問題特征，提出了一種融合啟發(fā)式選擇和分配規(guī)則的蟻群算法，該算法借鑒文獻[4]的信息素混合搜索機制、信息素積累與耗散規(guī)則；針對所研究的特殊問題，提出了啟發(fā)式任務(wù)分配規(guī)則解決任務(wù)分配問題；為提高算法效率，提出了啟發(fā)式任務(wù)選擇規(guī)則合并特殊操作任務(wù)。最后將算法應(yīng)用于某液壓驅(qū)動挖掘機底盤的裝配線設(shè)計中，說明算法增加改進措施有效性。

2 附帶翻轉(zhuǎn)工位雙邊裝配線平衡問題

2.1 雙邊裝配線與特殊裝配任務(wù)

雙邊裝配線兩側(cè)可同時進行裝配作業(yè)。如圖1所示：兩側(cè)并行運行不同裝配任務(wù)，一對工位處于同一位置的稱為成對工位，如工位1和2都屬于位置1，且互為伴隨工位。任務(wù)按操作方位偏向分三類：左型（L）、右型（R）、無偏向型（E，兩邊皆可），而對于本文研究的特殊任務(wù)，操作前需翻轉(zhuǎn)工作臺，因此需增加操作翻轉(zhuǎn)屬性（F，正面裝配為0，反面裝配為1）。因此求解雙邊裝配線問題需綜合考慮任務(wù)間的先后約束、任務(wù)操作方位約束和特殊操作約束，圖1中任務(wù)2的開始時間為3，任務(wù)2和任務(wù)1之間的等待時間為翻轉(zhuǎn)工位時間，任務(wù)3前面的等待時間為由于任務(wù)先后關(guān)系約束導(dǎo)致的等待時間。圖2樹狀圖標識了任務(wù)之間的操作先后順序，并同時標出了操作方位、特殊操作約束。

圖1 雙邊裝配線甘特圖示例

圖2 先后約束關(guān)系圖

2.2 問題的數(shù)學(xué)模型

帶翻轉(zhuǎn)工位雙邊裝配線第一類平衡問題定義：限定生產(chǎn)節(jié)拍，任務(wù)分配需同時滿足先后約束、操作方位和翻轉(zhuǎn)操作約束，將所有任務(wù)均衡分配到雙邊工位，并使成對工位數(shù)（位置數(shù)）最小，簡稱TALBP-F-I（F：帶翻轉(zhuǎn)操作任務(wù)），模型如下：

模型變量：I為包含所有任務(wù)的集合，I={1，2，…，N}s；ID為按任務(wù)操作方位分割I(lǐng)，D=L（左）、R（右）或E（兩邊）；IF為按特殊操作分割I(lǐng)，D=0（正面）、1（反面）；Ij、Ij′為分配到工位j和j′上的任務(wù)集；Tj、DLj為工位j的累計操作時間與累計延遲時間，j′表示伴隨工位；P(i)為任務(wù)i的前序任務(wù)集；AS為此集合中任意任務(wù)i的P(i)為空；W為未分配到位置中的任務(wù)集合；n為裝配線長度，即開啟位置數(shù)量；NS為開啟的工位數(shù)量；tis、tie分別表示任務(wù)i開始與結(jié)束時間；xiuk：若任務(wù)i已分配于位置u，操作方位k也已確定為L或R，則xiuk=1，其余xiuk=0。

式（1）表示任務(wù)先后關(guān)系約束；式（2）表示所有任務(wù)必須且只能在一個位置中出現(xiàn)一次，且只能分配到左或右工位；式（3）Tj、Tj′分別為位置u中工位j與j′的累計操作時間；式（4）表示任意位置的工位時間和必須小于等于節(jié)拍；式（5）表示特殊任務(wù)約束，即正常操作任務(wù)不能和特殊操作任務(wù)同時操作；式（6）目標為求最小裝配線長度。

3 TALBP-F-I的改進蟻群算法

3.1 TALBP-F-I蟻群算法簡介

在TALBP-F-I問題解的構(gòu)造過程中，需按任務(wù)間的先后約束關(guān)系依次選擇任務(wù)置于生產(chǎn)線的相應(yīng)工位，與螞蟻在向目標搜索過程中選擇可選路徑相似。因此蟻群算法的機理與裝配線平衡問題求解機理相似。本文蟻群算法先運用成熟的綜合信息素搜索規(guī)則得到待分配任務(wù)，隨之采用啟發(fā)式任務(wù)分配規(guī)則完成任務(wù)操作方位判別、任務(wù)前序附加操作判別（是否需翻轉(zhuǎn)工位）并根據(jù)前序任務(wù)的結(jié)束時間和當(dāng)前雙邊工位任務(wù)完成時間決定此任務(wù)的開始和結(jié)束時間。完成單個任務(wù)分配后更新局部信息素，完成單個解的構(gòu)造后更新全局信息素。本文借鑒了文獻[4]的綜合信息素搜索和信息素更新規(guī)則。圖3為蟻群算法流程圖。

圖3 蟻群算法流程圖

可供分配的任務(wù)集合AS：考慮先后關(guān)系約束，只有前序任務(wù)集為空或前序任務(wù)均已分配完畢的任務(wù)。改進的信息素搜索規(guī)則增加一個隨機搜索以脫離陷入局部最優(yōu)，綜合考慮了利用信息素搜索和隨機搜索兩種規(guī)則，從集合AS中選擇任務(wù)，是一種混合搜索策略[4]。依次選擇任務(wù)排入工位，直到所有任務(wù)分配完畢，整個過程構(gòu)成圖4任務(wù)鏈。即2.1節(jié)圖2約束關(guān)系的一個任務(wù)排列序列，任務(wù)序號、操作方位、特殊操作信息集成于一格。

圖4 一個完整的任務(wù)排列序列

3.2 啟發(fā)式任務(wù)分配規(guī)則

將蟻群搜索選擇的一個任務(wù)分配到具體工位，為實現(xiàn)特殊型任務(wù)的分配，本文提出改進的分配規(guī)則，規(guī)則的整體框架如圖5。

圖5 啟發(fā)式分配規(guī)則整體框架

規(guī)則1為確認位置雙工位中：（1）此任務(wù)所有前序任務(wù)最晚結(jié)束時間；（2）此工位當(dāng)前結(jié)束時間；（3）伴隨工位末端任務(wù)開始與結(jié)束時間；（4）確定任務(wù)序列前一任務(wù)分配時是否引起翻轉(zhuǎn)操作，并記錄此工位的伴隨工位。若項點4成立且本工位與項點4翻轉(zhuǎn)工位相同，此任務(wù)開始時間為項點3中任務(wù)結(jié)束時間；若項點4成立且本工位與項點4伴隨工位相同，則任務(wù)開始時間為項點3任務(wù)開始時間加翻轉(zhuǎn)操作時間；否則，任務(wù)開始時間為1和2中較大者。

規(guī)則2為確認位置雙工位中：（1）此任務(wù)所有前序任務(wù)中最晚結(jié)束時間；（2）此操作方位工位末端任務(wù)結(jié)束時間。此任務(wù)開始時間為1和2中較大者。

規(guī)則3確認：（1）雙邊工位中此任務(wù)所有前序任務(wù)的最晚結(jié)束時間；（2）雙工位末端任務(wù)開始與結(jié)束時間；（3）確定任務(wù)序列前一任務(wù)分配時是否引起翻轉(zhuǎn)操作，并記錄此工位的伴隨工位。分為如下幾種情形：①項點1時間均小于等于項點2中結(jié)束時間：若項點3不成立，則任務(wù)開始時間為項點2中較小時間，否則為項點2中翻轉(zhuǎn)任務(wù)開始時間加上翻轉(zhuǎn)操作時間；②項點1時間介于項點2兩項結(jié)束時間之間（不含相等），若項點3不成立，則任務(wù)開始時間為項點1時間，否則為項點2中翻轉(zhuǎn)任務(wù)開始時間加上翻轉(zhuǎn)操作時間；③項點1時間等于項點2中最晚結(jié)束時間：則任務(wù)開始時間項點1時間，此任務(wù)可隨機選擇一邊放入。

規(guī)則4確認：（1）雙工位末端任務(wù)結(jié)束時間。任務(wù)開始時間為項點1中較大時間，若項點1中兩結(jié)束時間相等，可隨機選擇一邊。規(guī)則5確認此任務(wù)是否滿足節(jié)拍約束，若滿足約束則將任務(wù)放入對應(yīng)工位，重新生成AS；否則將其從AS中剔除。規(guī)則6確認此任務(wù)是否滿足節(jié)拍約束，若滿足約束則將任務(wù)放入對應(yīng)工位，并在此工位標注翻轉(zhuǎn)操作標示，重新生成AS；否則將其從AS中剔除。

3.3 啟發(fā)式任務(wù)選擇規(guī)則

為提高算法求解的速度，考慮將特殊操作任務(wù)合理聚集，使得特殊任務(wù)在集合AS中集中選擇分配，增加了以下規(guī)則：

（1）若集合AS中同時包含特殊任務(wù)屬性0和1的任務(wù)，則將屬性與當(dāng)前工位狀態(tài)相反的任務(wù)放入暫時禁忌集合，進入步驟（3）；（2）若集合AS中僅含特殊任務(wù)屬性0或僅包含1的任務(wù)，進入步驟（3）；（3）采用文獻[4]的混合搜索機制選擇任務(wù)。

4 挖掘機底盤裝配關(guān)系分析

某型挖掘機底盤裝配線特點：（1）底盤裝配可按照雙邊裝配線形式布局，兩邊可同時進行裝配任務(wù)；（2）針對翻轉(zhuǎn)操作需配備底盤翻轉(zhuǎn)設(shè)備；（3）為提高裝配效率，采用助力機械手臂、自動扭矩擰緊機、抓取機等設(shè)備；（4）所有噴漆配件均噴漆后裝配，對于裝配過程中對漆層磕碰、劃傷，在裝配線末端設(shè)置補漆工序。

生產(chǎn)線的年產(chǎn)量規(guī)劃為11 500臺，按單班工作制規(guī)劃，每班工作8 h計，全年工作300 d，則生產(chǎn)線節(jié)拍時間需小于13 min。表1為任務(wù)操作信息匯總表，包含任務(wù)時間t，操作方位d，是否為特殊型任務(wù)f。圖6為任務(wù)之間先后約束關(guān)系圖。

5 裝配線優(yōu)化設(shè)計實例

本文采用MATLAB7.8對本文算法編寫了實驗程序，稱同時采用了兩種啟發(fā)式方法的蟻群算法為改進蟻群算法（pro-ACO），稱僅采用啟發(fā)式任務(wù)分配規(guī)則的為蟻群算法（ACO）。設(shè)定的實驗條件為螞蟻數(shù)20、迭代次數(shù)10，參數(shù)設(shè)置：α=1，β=2，ρ1=0.1，ρ2=0.9，r=0.9。在Intel core i3-2120計算平臺上，進行測試，所有問題均在不到6 s內(nèi)即求得較優(yōu)解。將節(jié)拍時間分為8 min、9 min、10 min、11 min、12 min五種情況，所得的分配結(jié)果見表2。表2中，m1代表計算得到的開啟位置數(shù)量，n1代表運算10次的平均收斂代數(shù)；LB代表計算得到的最優(yōu)平衡率（注：表2中，計算平衡率時，將翻轉(zhuǎn)操作時間也累計為裝配時間，因此針對開啟相同位置數(shù)的結(jié)果，平衡率越低，則特殊操作時間越少，即所需投入底盤翻轉(zhuǎn)設(shè)備也越少，更具優(yōu)越性）。分析表2數(shù)據(jù)可知，由于采用了更多的約束條件，所以使得算法在每次選擇時剔除了更多選擇，提高了改進蟻群算法的迭代收斂性。而未采用此規(guī)則的蟻群算法之探索能力更好（相同位置數(shù)目下能得出更優(yōu)的平衡方案），因算法每次可選擇任務(wù)更多，因此也增加了算法搜索時間。節(jié)拍為660的分配方案見表3。

表1 任務(wù)操作時間及操作方位

圖6 任務(wù)優(yōu)先關(guān)系圖

表2 五種節(jié)拍時間優(yōu)化結(jié)果對比

表3為當(dāng)節(jié)拍時間為660時所得的優(yōu)化結(jié)果，此優(yōu)化結(jié)果的平衡率為83.26%。

6 結(jié)束語

挖掘機底盤是典型的可兩側(cè)同時裝配的產(chǎn)品，同時為方便裝配作業(yè)而附加翻轉(zhuǎn)工位操作，但以往雙邊裝配線規(guī)劃設(shè)計算法未將需翻轉(zhuǎn)工位任務(wù)納入研究范圍。翻轉(zhuǎn)工位操作增加了雙邊裝配線規(guī)劃設(shè)計的難度，在原有雙邊裝配線平衡問題工位內(nèi)部任務(wù)先后約束、雙邊工位任務(wù)交叉影響、任務(wù)操作方位選擇等基礎(chǔ)約束條件上，附加任務(wù)的翻轉(zhuǎn)操作判斷，因此本文作了以下工作：（1）提出了啟發(fā)式任務(wù)分配規(guī)則解決需翻轉(zhuǎn)工位任務(wù)的分配問題。（2）為提高算法求解速度，提出了啟發(fā)式任務(wù)選擇規(guī)則。（3）將兩種規(guī)則融入蟻群算法，并將所提算法應(yīng)用至某挖掘機底盤總裝線中，通過對比分析兩種蟻群算法優(yōu)化結(jié)果，取得了良好成效。

表3 雙邊裝配線實例優(yōu)化結(jié)果

[1]Lee T O，Kim Y，Kim Y K.Two-sided assembly line balancing to maximize work relatedness and slackness[J].Computers and Industrial Engineering，2001，40（3）：273-292.

[2]?zcan U，Toklu B.Multiple-criteria decision-making in twosided assembly line balancing：a goal programming anda fuzzy goal programming models[J].Computers&Operations Research，2009，36（6）：1955-1965.

[3]童科娜，徐克林，鄭永前.基于結(jié)構(gòu)式譯碼遺傳算法平衡多人共站裝配線[J].計算機工程與應(yīng)用，2013，49（6）：267-270.

[4]張則強，胡俊逸，程文明.求解帶區(qū)域約束的雙邊裝配線平衡問題的一種改進蟻群算法[J].現(xiàn)代制造工程，2013（4）：19-25.

[5]Scholl A，Becker C.State-of-the-art exact and heuristic solution procedures for simple assembly line balancing[J]. European Journal of Operational Research，2006，168（3）：666-693.

[6]Kim Y K，Song W S，Kim J H.A mathematical model and a genetic algorithm for two-sided assembly line balancing[J].Computers&Operations Research，2009，36（3）：853-865.

[7]吳爾飛，金燁，續(xù)愛民，等.基于改進遺傳算法的雙邊裝配線平衡[J].計算機集成制造系統(tǒng)，2007，13（2）：268-274.

[8]?Zcan U，Toklu B.A tabu search algorithm for two-sided assembly line balancing[J].The International Journal of Advanced Manufacturing Technology，2009，43（7/8）：822-829.

[9]Roshani A，F(xiàn)attahi P，Roshani A，et al.Cost-oriented twosided assembly line balancing problem：a simulated annealing approach[J].International Journal of Computer Integrated Manufacturing，2012，25（8）：689-715.

[10]Chutima P，Chimklai P.Multi-objective two-sided mixedmodel assembly line balancing using particle swarm optimisation with negative knowledge[J].Computersand Industrial Engineering，2012，62（1）：39-55.

[11]Tapkan P，Ozbakir L，Baykasoglu A.Modeling and solving constrained two-sided assembly line balancing problem via bee algorithms[J].Applied Soft Computing，2012，12（11）：3343-3355.

[12]Tapkan P，Ozbakir L，Baykasoglu A.Bees algorithm for constrained fuzzy multi-objective two-sided assembly line balancing problem[J].Optimization Letters，2012，6（6）：1039-1049.

[13]張則強，程文明，鐘斌，等.求解裝配線平衡問題的一種改進蟻群算法[J].計算機集成制造系統(tǒng)，2007，13（8）：1632-1638.

[14]張則強，程文明，鐘斌，等.混合品種裝配線平衡問題的一種混合搜索機制的蟻群算法[J].機械工程學(xué)報，2009，45（5）：95-101.

[15]Dorigo M，Blum C.Ant colony optimization theory：a survey[J].Theoretical Computer Science，2005，344（2/3）：243-278.

ZHU Xiaoping1,ZHANG Zeqiang2

1.School of Mechanical and Electrical Engineering,Zhejiang Institute of Communications,Hangzhou 311112,China
2.School of Mechanical Engineering,Southwest Jiaotong University,Chengdu 610031,China

An improved ant colony optimization is proposed for solving the two sided excavator chassis’s assembly lines with station flipping tasks.The flipping task can decrease the assembly difficulty and operational risk but will greatly increase the planning and design difficulty.A heuristic task assignment method is presented for solving distributing the station flipping tasks.The heuristic task selection method is used to accelerate to find a feasible solution.The tasks’priority diagram is proposed after studying the assembly relationship between the tasks and the problem is abstracted into two sided assembly line balancing problem.The standard and improved ant colony algorithms are used for contradistinction on solving this problem.And this paper studies the inference brought by the inner structure of this two algorithms.

Ant Colony Optimization（ACO）;two-sided assembly lines;station flipping task;optimization;swarm intelligence

A

TP301.6；TH165

10.3778/j.issn.1002-8331.1310-0291

ZHU Xiaoping,ZHANG Zeqiang.Ant Colony Optimization for two sided assembly line balancing with station flipping task.Computer Engineering and Applications,2014,50（6）：240-245.

國家自然科學(xué)基金（No.51205328）；高等學(xué)校博士學(xué)科點專項科研基金資助課題（No.200806131014）；教育部人文社會科學(xué)研究青年基金項目（No.12YJCZH296）；中央高校基本科研業(yè)務(wù)費專項資金資助項目（No.SWJTU09CX022）。

朱小平（1957—），男，副教授，研究方向：制造裝備機械設(shè)計；張則強（1978—），通訊作者，男，博士，副教授，研究方向：制造系統(tǒng)與智能優(yōu)化等。E-mail：zhangzeqiang@gmail.com

2013-10-23

2013-12-09

1002-8331（2014）06-0240-06