求解雙邊裝配線第二類平衡問題的一種蟻群算法*

胡俊逸， 張則強，金初云

(1.浙江交通職業技術學院 機電與航空學院，杭州 311112；2.西南交通大學，機械工程學院，成都 610031)

?

求解雙邊裝配線第二類平衡問題的一種蟻群算法*

胡俊逸1， 張則強2，金初云1

(1.浙江交通職業技術學院 機電與航空學院，杭州 311112；2.西南交通大學，機械工程學院，成都 610031)

摘要：雙邊裝配線在任務分配過程中，除考慮任務先后關系約束外還需兼顧任務操作方位約束及任務操作的并行性要求。針對雙邊裝配線第二類平衡問題提出了數學模型并構建了一種蟻群算法。此算法采用蟻群綜合搜索規則、啟發式任務分配規則構造一個可行解，對最優解的搜索過程提出了可行的規劃方案。最后，通過為某型裝載機的實例提出多組較好的平衡方案，驗證了此算法的有效性。

關鍵詞：雙邊裝配線; 平衡; 蟻群算法

0引言

在汽車、工程機械產業，因產品尺寸大、裝配復雜，難以采用單邊生產線，故雙邊裝配線得以廣泛應用。雙邊裝配線平衡問題 (Two-sided Assembly Lines Balancing Problem, TALBP) 因此受到較多關注。雙邊裝配線平衡問題分為兩類：第一類平衡問題為在限定節拍時間的前提下，盡量縮減裝配線長度；第二類平衡問題為在限定裝配線成對工位數目的情況下，盡量縮減工位的節拍。生產實際中為降低產品的生產周期，常以第二類問題為優化目標。

對于雙邊裝配線第一類問題，已有較多學者進行過研究：Bartholdi[1]首次提出雙邊裝配線的概念，并針對第一類問題提出了一種基于First Fit規則的啟發式算法；Kim[2]和Lee[3]的團隊針對第一類問題提出了遺傳算法，并加入成組分派策略以優化任務之間的相關性指標；Simaria[4]和Baykasoglu[5]運用蟻群優化算法求解第一類問題，其中Baykasoglu首次引入區域約束的概念，并提出解決附帶此特殊條件的蟻群算法；吳爾飛與胡小鋒提出解決第一類問題的精確解法[6]。

目前，較少有學者對第二類平衡問題(TALBP-Ⅱ)進行研究[7-8]：吳而飛[8]首次提出一種基于任務歸組的遺傳算法，并采用此算法對某裝載機生產線進行節拍優化，取得較好效果；Kim[9]采用類似的遺傳編碼策略，并對目前雙邊裝配線引用較多的算例進行節拍優化，算法適應性較好。可見，目前國內外對此類問題研究中解決方法相似性高。蟻群算法在單邊裝配線的優化問題中通過采用綜合信息素搜索規則[10]或加入自適應搜索策略[11]，都展現較優性能。而目前還未有針對雙邊裝配線第二類平衡問題(TALBP-Ⅱ)的蟻群算法公開文獻。

本文針對制造企業中普遍存在的雙邊裝配線第二類平衡問題，提出一種蟻群算法，采用蟻群綜合搜索規則選擇任務，采取任務分配規則分配任務，對蟻群整體搜索進程提出了可行的規劃方案。引用實際算例進行測試，具有較好效果。

1雙邊裝配線簡介

如圖1所示，在雙邊裝配線中，兩側工位中的不同操作任務可以同時展開。工位1和2由于相互面對，故稱為一對成對工位(mated-station)，同時，工位1又可稱為工位2的伴隨工位(companion)，其余工位關系類似。在雙邊裝配線中，兩個相互之間無任何先后約束關系的操作任務可同時進行作業，從而相比于單邊裝配線更能節約時間。

圖1　雙邊裝配線

圖2為某雙邊裝配線的操作任務之間先后約束關系的網絡圖，圓內標示任務序號，圓外標示任務操作時間。圖3為此簡單問題的所有操作任務在雙邊工位中的排列方案，并可視為甘特圖。黑色部分標示成對工位之間的操作任務由于圖2所示的先后約束關系而產生的延遲與空余。可見雙邊裝配線的規劃問題比單邊裝配線更為復雜。

圖2　操作任務先后約束關系網絡圖

圖3　雙邊裝配線成對工位中的延遲與等待

2雙邊裝配線第二類平衡問題

2.1雙邊裝配線第二類平衡問題的數學模型

為方便表達，首先列出相關變量：I—任務集，I={1, 2, …,i,N}；ID—將任務按其操作方位分割為三類，D=L(左)、R(右)或E(兩邊)，IL/IR/IE分別表示必須在左側、右側裝配的任務集合和可以在任意側操作的任務集合；Ij、Ij′—工位j和j′上所分配的任務集；Tj、Rj—工位j的操作時間累計值及延遲時間累計值,同理Tj′、Rj′則表示工位j′的操作時間及延遲時間累計值；P(i)—任務i的所有前序任務集；S—所有前序任務集P(i)為空的任務i的集合，即可選任務集合；S′—集合S中滿足當前工位節拍約束條件的任務集合，即選擇后就可直接分配的任務集，可見任務集S′是對S的進一步篩選；W—未分配任務集合；n—共開啟的位置數量；NS—共開啟的工位數量；xipk—若任務i分配到位置p上，操作方位為k，k∈{L,R}，則為1，否則為0。

約束條件：

若xipk=1,則xhgk=0

(1)

其中h∈P(i),g、p=1, 2, 3, …,n, 且g>p；

(2)

(3)

(4)

對位置p，Tj+Rj≤C，且Tj′+Rj′≤C；

(5)

目標函數： MinimizeC

(6)

(7)

(8)

式(1)代表任務的分配需符合先后約束關系；式(2)表示任務必須且只能出現在雙邊裝配線的某側一個工位中；式(3)、(4)表示工位j與j′的操作時間累計值；式(5)表示構成任意位置p的雙邊工位中，其累計操作時間與累計延遲時間和必須小于節拍時間；式(6)表示雙邊裝配線第二類問題(TALBP-Ⅱ) 的主要優化目標，即在整體雙邊裝配線開啟位置數量確定條件下盡可能縮減節拍時間；式(7)和式(8)為次要優化目標，LE為平衡率，SI為平滑系數，當LE=1、SI=0時為各工位負荷完全一致的理想平衡狀態。

2.2生產節拍的理論下限

借鑒文獻[8]的節拍下限公式，并參考單邊裝配線平衡問題中節拍時間下限的確定方式，本文提出的節拍下限值為：

Cmin=max{|TSUM/2n|,|TSUML/n|,|TSUMR/n|,tmax}

(9)

其中，TSUM為任務集I中所有任務的操作時間累計總和；TSUML、TSUMR、TSUME分別為任務集IL、IR、IE中所有任務的操作時間累計總和；tmax為所有操作任務中操作時間最長值。

3蟻群算法的構建

3.1蟻群綜合搜索規則

從可供直接分配的任務集合S′中進行篩選：在當前雙邊工位任務安排情況之下可最早被操作的任務具有優先權，并匯集為優選集合FT(FT中包含的任務可在相同的最早時刻被操作)。若集合FT僅含一個元素，則可直接按3.2節的啟發式任務分配規則進行分配；否則，在借鑒了文獻[10]的改進信息素規則基礎上，按以下混合搜索機制進行下一步篩選：

(10)

式中r——由程序隨機產生的(0,1)之間隨機數，

r1——規則選擇參數閥，0≤r1≤1

FT——當前位置j的最早可開始任務集合

α,β——調節信息素強度和啟發式信息在規則I1中相對比例的參數值

ηi——以任務i的位置權重pwi作為其啟發式信息：

(11)

在公式(11)中，Fi表示在優先順序網絡圖中，任務i的后繼任務集合。此啟發式規則綜合衡量了本任務的作業時間以及其后續所有任務數量及作業時間。在該規則之下，后續任務數量多且累計作業時間較長的任務具有更高的被選擇概率。

公式(10)中的兩項概率選擇規則：

(1)利用信息素和啟發式信息的規則：若產生的隨機數r符合0≤r≤r1，以概率pij從集合FT中選擇任務。

(2)隨機搜索的規則：若隨機數r符合r1

3.2啟發式任務分配規則

規則1：首先判斷任務的操作方位，若為L(或R)，則按其操作方位特性放入左側(或右側)工位；規則2：若此任務的操作方位為兩邊均可的E型，則放入能使其最早進行操作的一側工位；若放入兩側工位能使之同時開始操作，隨機選擇一側工位。

3.3蟻群算法可行解的構造

圖4　蟻群算法構造可行解流程

可行解的構造流程如圖4所示。針對第二類平衡問題，為限定開啟的位置數量n，且在此條件下優化節拍時間。為保證所有任務都能分配完畢，在前n-1個位置處，采用當前迭代時刻最優節拍時間進行節拍時間約束；當處于第n個位置時，在忽略節拍約束條件下選擇剩余未分配任務并形成可行解。最后統計此可行解所有工位中的最長操作時間，作為此節的節拍時間。

3.4信息素更新規則

局部信息素更新：由于螞蟻會在沿途釋放信息素從而吸引其余螞蟻，為減弱這種作用從而減少已選的方案對后來的螞蟻對未知方案探索的干擾，增強蟻群對未知方案的探索能力。當螞蟻將任務i分配到排列序列位置j處，則信息素矩陣τij上的值按下式更新：

τij←(1-ρ1)+ρ1τ0

(12)

ρ1—蒸發控制系數，0<ρ1<1；

τ0—信息素初始值；

全局信息素更新：每代螞蟻的最優解搜索結果將建立最優解集合，集合中每個解都對路徑釋放信息素。為降低算法搜索陷入局部最優的概率，在每代最優搜索結果釋放信息素時，限定各最優解的同一任務只在同一位置之間釋放一次信息素：

τij←(1-ρ1)τij+ρ1Δτij

(13)

Δτij=

ρ2為信息素蒸發控制系數，0<ρ2<1。

3.5蟻群整體搜索規劃

最優解的搜索從理論最小節拍Cmin開始，首代螞蟻從理論最小節拍Ct=Cmin處搜索，若未找到滿足此條件的可行解，則進行下一代螞蟻群搜索，并將搜索的節拍值更新為Ct=Ct+1；若某代蟻群所得最優解的節拍時間恰好等于當前的節拍時間限定值Ct，則在下一代搜索時縮小節拍時間標準，令Ct=Ct-1；整體搜索按此規則進行，直到達到最大搜索代數或找到理論最優停止。

4實例驗證

采用MATLAB7.8編制算法程序，程序運行時從記事本中讀取任務先后約束條件、任務操作適應方位條件、任務操作時間條件，并設置搜索代數、開啟位置數目n便可得到節拍時間優化結果，同時可得到任務分配甘特圖。

圖5　某裝載機任務先后約束關系圖

圖5為適合采用雙邊裝配線規劃的某型裝載機的任務先后約束關系網絡圖[12]。經設置4種開啟位置數目n；得到表1所示4種優化方案。圖6和表2為方案2工位任務安排甘特圖和分配情況統計，均由MATLAB生成。

圖6　MATLAB輸出的方案2工位安排甘特圖

方案(位置數目)C(s)LE(%)SI(s)方案1(5)102194.079.73方案2(6)86093.070.22方案3(7)77189.0152.47方案4(8)66091.081.01

表2　方案2任務分配

表1中算法計算所得的4種優化方案的平衡率均達到89%以上。而分配方案的雙邊工位任務分配甘特圖顯示模塊更增加了算法的實用性與優化結果的直觀性。在圖6的任務甘特圖中，操作時間長度體現于進度條長短，任務的操作開始和結束時間在進度條上方標示；橫軸和縱軸分別表示時間和工位，左右工位分別以奇偶數表示。在伴隨工位之間，由于任務之間的先后約束關系所形成的等待與延遲均可直觀顯示，較為實用。

5結束語

本文針對雙邊裝配線第二類平衡問題進行了研究，構建了數學模型并設計了一種蟻群算法求解。以蟻群綜合搜索規則、啟發式任務分配規則構建出算法的關鍵模塊，用于可行解的構造，采用蟻群整體搜索規劃探索最優解。針對某大型裝載機進行規劃計算，所得分配方案均具有較高的平衡率，說明算法求解有效性。更通過設計了甘特圖的顯示模塊從而增加了算法的實用性。

[參考文獻]

[1] BARTHODI J J.Balancing two-sided assembly lines:a case study[J].International Journal of Production Research,1993,31(10):2447-2461.

[2] KIM Y K, KIM Y H, KIM Y J. Two-sided assembly line balancing: a genetic algorithm approach[J]. Production Planning & Control, 2000, 11(1): 44-53.

[3] LEE T O, Kim Y, & Kim Y K. Two-sided assembly line balancing to maximize work relatedness and slackness[J]. Computers & Industrial Engineering, 2001, 40(3):273-292.

[4] SIMARIA A S, VILARINHO P M. 2-ANTBAL: An ant colony optimisation algorithm for balancing two-sided assembly lines[J]. Computers & Industrial Engineering, 2009, 56(2): 489-506.

[5] BAYKASOGLU A, DERELI T. Two-sided assembly line balancing using an ant-colony-based heuristic[J]. The International Journal of Advanced Manufacturing Technology, 2008, 36(5-6): 582-588.

[6] WU E F, JIN Y, BAO J S, et al. A branch-and-bound algorithm for two-sided assembly line balancing[J]. The International Journal of Advanced Manufacturing Technology, 2008, 39(9): 1009-1015.

[7] 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.

[8] 吳爾飛, 金燁, 汪崢.雙邊裝配線第二類平衡問題研究 [J].計算機集成制造系統, 2005, 11(11): 1604-1608.

[9] 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.

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

[11] 鄧福平, 張超勇, 連坤雷, 等. 基于自適應蟻群算法的裝配線平衡問題研究[J]. 中國機械工程, 2011,22(16): 1949-1953.

[12] 吳爾飛. 雙邊裝配線平衡技術的研究[D]. 上海:上海交通大學, 2009.

(編輯趙蓉)

Ant Algorithm for Two-sided Assembly Line Balancing of Type-2

HU Jun-yi1, ZHANG Ze-qiang2, JIN Chu-yun1

(1. School of Mechanics and Electronics, Zhejiang Institute of Communications, Hangzhou 311112,China;2.School of Mechanical Engineering,Southwest Jiaotong University, Chengdu 610031,China)

Abstract：Two-sided assembly line problem is more difficult than one-sided assembly line problem as the task distribution procedure. In this problem, besides the precedence constraints among tasks, the operation directions constraints of tasks and the requirement of parallel work should also be taken into consideration. The mathematical model and an ant colony algorithm were constructed to solve the Two-sided Assembly Line Balancing Problem of type-2(TALBP-Ⅱ). A hybrid ant-based search rule and a heuristic task distribution rule were used in order to establish a feasible solution, global pheromone trail update and the optimum solution search strategy were considered. The feasibility of this algorithm was indicated by a case of a loader final assembly line.

Key words：two-sided assembly lines; balancing; ant colony algorithm

中圖分類號：TH165; TG506

文獻標識碼：A

作者簡介：胡俊逸(1986—)，男，浙江金華人，研究方向為制造系統優化仿真，(E-mail)hujunyi_jt@zjvtit.edu.cn。

*基金項目：國家自然科學基金項目(51205328)；中央高校基本科研業務費專項資金資助項目(SWJTU09CX022; 2010ZT03)

收稿日期：2015-04-13

文章編號：1001-2265(2016)02-0149-04

DOI:10.13462/j.cnki.mmtamt.2016.02.042