隨機型雙邊混流裝配線平衡問題的兩階段求解方法研究

段移庭， 蘇　平， 鄭晨鳴

(廣東工業(yè)大學 機電工程學院, 廣東 廣州 510006)

?

隨機型雙邊混流裝配線平衡問題的兩階段求解方法研究

段移庭， 蘇平， 鄭晨鳴

(廣東工業(yè)大學 機電工程學院, 廣東 廣州 510006)

摘要：為降低求解隨機型雙邊混流裝配線平衡問題的復雜性，提出了一種遺傳算法與仿真分析相結合的兩階段求解方法。首先建立忽略裝配線同一工作站組的兩工作站之間作業(yè)先后順序約束的隨機型雙邊混流裝配線平衡問題的簡化數(shù)學模型，采用一種基于序列組合編碼方式的遺傳算法對簡化模型進行求解，獲取備選解；在此基礎上，建立考慮所有約束條件的仿真模型，通過系統(tǒng)仿真分析與評價，從備選解中獲得該問題的最優(yōu)解(或次優(yōu)解)。算例研究表明，所提出的兩階段求解方法，在獲得滿意解的同時，可以大幅度降低問題求解的復雜性。

關鍵詞：雙邊裝配線平衡； 隨機； 混流； 遺傳算法； 仿真

裝配線平衡問題(assembly line balancing problem, ALBP)是求解裝配線上作業(yè)元素在各工作站的分配方案，使裝配線在滿足作業(yè)先后順序約束的同時，各工作站單件作業(yè)時間接近,且不超過生產(chǎn)節(jié)拍，達到裝配線利用率最大。裝配線的平衡質(zhì)量直接影響生產(chǎn)效率、生產(chǎn)成本和產(chǎn)品質(zhì)量[1-3]。根據(jù)裝配線上作業(yè)人員的操作方位，裝配線可分為單邊裝配線和雙邊裝配線兩大類。雙邊裝配線主要用于滿足大型產(chǎn)品(例如汽車、冰箱等)的裝配需求，與傳統(tǒng)的單邊裝配線相比，雙邊裝配線具有能縮短裝配線長度，減少產(chǎn)品的下線時間，降低工裝、夾具及物料處理的成本等優(yōu)點[4]。因此，雙邊裝配線平衡問題(two-sided assembly line balancing problem, TALBP)的研究越來越得到學術界和企業(yè)界的關注。

文獻[4]首次提出了雙邊裝配線平衡問題(TALBP)。雙邊裝配線平衡問題比單邊裝配線平衡問題要復雜，因為對于雙邊裝配線，在將作業(yè)元素分配到各工作站時，需要考慮作業(yè)元素在裝配線上的操作方位約束以及裝配線兩側工作站組(裝配線兩側相對的工作站)之間由于作業(yè)先后順序約束所引起的不可避免的等待時間。隨著國內(nèi)外學術界對雙邊裝配線平衡問題研究的不斷深入，涌現(xiàn)出一些有關雙邊裝配線平衡問題的建模與求解方法的研究成果。文獻[5]提出一種基于工位編碼的遺傳算法來解決雙邊裝配線平衡問題，但該方法不能搜索整個可行解空間，只能得到局部最優(yōu)解。文獻[6]針對裝配任務的相關度及任務安排上的松弛度的平衡問題，釆用多個啟發(fā)式算法，以提高任務之間的相關度和不同工作站任務之間的松弛度。文獻[7]提出一種基于“序列組合”(作業(yè)序列和作業(yè)方位組合)編碼方法的遺傳算法，提高了可行解的搜索效率。上述研究成果均是針對單一品種雙邊裝配線平衡問題進行的研究。為了適應市場需求的多樣化，多種產(chǎn)品混流生產(chǎn)成為主要生產(chǎn)模式。為了解決多種產(chǎn)品混流生產(chǎn)的問題，文獻[8]提出了雙邊混流裝配線平衡的第一類問題，以工作站組數(shù)目、生產(chǎn)節(jié)拍、工作站數(shù)目最少為目標，構建了多目標函數(shù)，并對雙邊混流裝配線平衡的多目標優(yōu)化問題進行了研究。文獻[9]針對雙邊混流裝配線平衡問題的特點，提出了一種改進蟻群算法，得到了作業(yè)分配方案。文獻[10]考慮了并發(fā)操作的情況，建立了具有并發(fā)操作約束條件的雙邊混流裝配線數(shù)學模型，并給出了遺傳算法求解過程。文獻[8，10]均假定裝配作業(yè)時間為常數(shù)，而在實際生產(chǎn)環(huán)境下，特別是以手工作業(yè)為主的裝配線，作業(yè)時間具有隨機性，文獻[11]在考慮雙邊裝配線平衡特點的前提下，提出了一種具有操作方位約束的任務優(yōu)先分配的啟發(fā)式算法，得到不同的平衡方案，取得了較好的效果，但該研究是針對單一品種裝配線進行的。

文獻[12]針對混合裝配線存在的不確定性問題，基于數(shù)學模型對不確定性因素進行了分析，并采用eM-Plant建模，通過系統(tǒng)仿真研究不確定性因素對混合裝配線平衡的影響；文獻[13]考慮隨機混流裝配線的特點，提出了一種混合粒子群算法來求解隨機混流裝配線平衡問題；文獻[14]提出了一種基于集束搜索的算法來解決隨機型混流裝配線平衡問題。

文獻[12-14]均是針對單邊混流裝配線平衡所做的研究，目前針對隨機型雙邊混流裝配線平衡問題的研究成果很少，而在企業(yè)生產(chǎn)實際中，雙邊混流裝配線平衡問題普遍存在，特別是作業(yè)時間的不確定性對雙邊混流裝配線平衡的影響不容忽視，因此對于隨機型雙邊混流裝配線平衡問題(stochastic two-sided mixed-model assembly line balancing problem, STMALBP)的研究更具有實際意義和研究價值。

1STMALBP描述與數(shù)學建模

1.1STMALBP描述

雙邊裝配線是指在裝配線的左右兩邊都設有作業(yè)工作站的裝配線，裝配線左右兩邊相對的兩個工作站成對稱分布，這一對工作站稱為工作站組(mated-station)，而同一工作站組中的兩個工作站互稱為對方的伴隨工作站(companion)[4]，如圖1所示，該雙邊裝配線包含5個工作站組。

圖1　雙邊裝配線

在雙邊裝配線中，分配到同一工作站組的兩個工作站中的作業(yè)元素可能由于作業(yè)先后順序關系的約束，導致產(chǎn)生不可避免的“等待時間”，如圖2所示。

圖2　“等待時間”描述

圖2中，如果作業(yè)元素3是7的先行作業(yè)元素，裝配線右邊工作站在完成作業(yè)元素2后不能馬上開始元素7的作業(yè)，而需要等元素3完成后才可以開始，從而產(chǎn)生了與作業(yè)元素3相關的“等待時間”。因此，雙邊裝配線平衡問題與單邊裝配線平衡問題不同，在計算工作站作業(yè)時間時，不可以把分配到該工作站所有作業(yè)元素的作業(yè)時間直接相加，而需要把“等待時間”作為該工作站作業(yè)時間一部分，即工作站的作業(yè)時間等于所有作業(yè)元素時間與該工作站的“等待時間”之和。

在隨機型雙邊混流裝配線平衡問題中，由于不可避免的“等待時間”的存在，增加了問題的建模與求解的復雜性，為此本文提出一種將遺傳算法和仿真分析相結合的兩階段求解方法，以簡化問題的建模與求解過程。遺傳算法具有良好的搜索能力和優(yōu)化特性，能夠有效尋找出裝配線平衡問題的較優(yōu)解。由于遺傳算法是基于簡化模型進行搜索的，搜索方向可以確定，但不能保證解的質(zhì)量，因此，遺傳算法所得到的解只能作為備選解。仿真方法是分析和求解隨機性問題的有效方法，通過仿真分析，對備選解進行篩選，從而獲得滿足約束條件的隨機型雙邊混流裝配線平衡問題的最優(yōu)解(或次優(yōu)解)。

1.2不考慮等待時間的STMALBP數(shù)學建模

雙邊裝配線平衡問題是將產(chǎn)品的作業(yè)元素分別分配到裝配線左、右兩邊工作站中，在滿足作業(yè)元素先后順序關系約束和節(jié)拍要求的前提下，使得工作站組的數(shù)目最小。如前文所述，當考慮同一工作站組左右兩個工作站之間作業(yè)元素先后順序關系約束的情況時，可能產(chǎn)生不可避免的“等待時間”，增加了數(shù)學規(guī)劃模型的復雜性，因此，暫時不考慮“等待時間”。

基于如下假設條件建立問題的簡化數(shù)學規(guī)劃模型：1)問題所有輸入?yún)?shù)均為已知；2)各個作業(yè)元素作業(yè)時間tmi之間互相獨立，各個工作站之間互不影響；3)混合排產(chǎn)生產(chǎn)的產(chǎn)品結構相似，工藝相近；4)不考慮并行操作和作業(yè)“等待時間”的情況。

C 表示裝配線節(jié)拍(指連續(xù)相同的兩個產(chǎn)品的下線時間間隔)；

I 表示雙邊裝配線上所有作業(yè)元素集合，I = {1, 2, …, i}；

P(i) 表示作業(yè)元素i的先行作業(yè)元素的集合；

AL、AR表示分別分配到雙邊裝配線左邊、右邊的作業(yè)元素的集合，AL、AR∈I；

AE表示既可以分配到左邊又可以分配到右邊的作業(yè)元素的集合，AE∈I；

N 表示雙邊裝配線上工作站組數(shù)目；

d(i) 表示作業(yè)元素的作業(yè)方位

(n, d) 表示工作站組n中的一對工作站，且(n, d1)和(n, d2)互為伴隨工作站；

Wind表示分配到工作站(n, d)中的作業(yè)元素集合；

xind表示作業(yè)元素i分配到工作站組n、操作方位為d的工作站中，且當作業(yè)元素i被分配到工作站(n, d)時，xind的值為1，否則為0；

Tkm表示m型號產(chǎn)品被分配到工作站k中的作業(yè)元素的作業(yè)時間，Ikm表示m型號產(chǎn)品被分配到工作站k的作業(yè)元素集合；

xi為決策變量，為作業(yè)元素i所分配的工作站的序號。

當作業(yè)時間為隨機變量時，會導致整個工作站的作業(yè)時間成為隨機變量，理論上，在確定合理的節(jié)拍后，很難保證工作站內(nèi)作業(yè)時間都滿足節(jié)拍的要求；所以，對于作業(yè)時間隨機變化性的裝配線，工作站作業(yè)時間Tkm≤C(m=1,2,3…M)，只能以一定的概率α(0<α<1) 來滿足節(jié)拍的要求，即

在隨機型雙邊混流裝配線平衡問題的第1階段求解中，由于不考慮“等待時間”，在這種情況下，若仍然以給定的節(jié)拍C為工作站時間的約束條件，所求得的備選解可能會在考慮“等待時間”時，成為不可行解(即工作站時間超出節(jié)拍C)，為此，在問題的第一階段求解中，引進一個適當?shù)膮?shù)Δ，將節(jié)拍暫時調(diào)整為C'=C-Δ， STMALBP簡化數(shù)學模型相關表達式如下。

F=min(N)。

(1)

(2)

(3)

∪Wind=I;

(4)

(5)

(6)

式(1)表示目標函數(shù)，以最小化工作站組數(shù)目為目標；式(2)表示作業(yè)先后順序關系約束，在式(2)中，a∈P(i)，b∈I-P(i)；式(3)表示操作方位的約束；式(4)表示所有作業(yè)元素被分配到工作站；式(5)表示每個作業(yè)元素只能分配給一個工作站；式(6)表示各個工作站的作業(yè)時間小于調(diào)整節(jié)拍C'，其中m=1,2,3,…,M，對于任一分配到各個工作站的k的產(chǎn)品的所有作業(yè)元素而言，它們都必須在調(diào)整節(jié)拍內(nèi)完成作業(yè)。

2STMALBP簡化模型遺傳算法求解

由于STMALBP問題的復雜性，本文采用兩階段求解方法。第1階段采用遺傳算法求解STMALBP簡化模型。遺傳算法求解裝配線平衡問題主要有3種編碼方式：基于作業(yè)序列號、基于工位號、基于序列組合的編碼。在雙邊裝配線平衡問題中，不僅要考慮作業(yè)元素分配的工作站，還要考慮該元素的作業(yè)方位?；谛蛄刑柕木幋a方式無法滿足雙邊裝配線平衡對作業(yè)元素操作方位的要求，而基于工位號的編碼方式中需要對作業(yè)元素的裝配順序進行排序，增加了問題的復雜性。因此，基于序列組合的編碼方式更適合雙邊裝配線平衡問題。

2.1基于序列組合編碼方式

在基于序列組合的編碼方式中，染色體各個基因由兩部分組成：作業(yè)元素的序列號和相應的作業(yè)方位[7]。即按照作業(yè)元素分配到工作站的先后順序，將作業(yè)元素排成1列，染色體長度等于作業(yè)數(shù)，每個作業(yè)元素對應1個基因，其取值為作業(yè)元素i和其分配的方位d(d=L、R、E)的組合(i,d)。以P16問題[11]為例，一條染色體的編碼形式如圖3所示。

圖3基于序列組合編碼形式

Fig.3Sequence-based combined coding schemes

2.2解碼

解碼時，將染色體從左至右依次進行解碼，具體過程如下。

1) 開啟第1個工作站組n(n=1)，根據(jù)染色體第i個基因代碼d的值，判斷第i個基因位對應的作業(yè)元素的作業(yè)方位，并將作業(yè)元素i分配到相應工作站當中(d=R，即分配到相應位置的右邊工作站；d=L，則分配到左邊工作站；d=E則隨機分配到任意一邊)。

2) 計算當前位置工作站的所有作業(yè)元素的作業(yè)時間Tkm，判斷當前工作站所有作業(yè)元素的作業(yè)時間是否小于或等于C'，如果滿足要求(式(6))，分配到當前位置對應工作站。否則，開啟下一個工作站組(n=n+1)，分配到對應的工作站中。如此重復前面兩個步驟，直到染色體所有的基因解碼完畢。同樣，以P16為例[11]，如果給定節(jié)拍為19，圖3所示的染色體解碼的結果如圖4所示。

圖4　染色體解碼結果圖

2.3初始化

在遺傳算法中，染色體初始化的目的是生成一組可行染色體。采用遺傳算法求解雙邊裝配線平衡問題中，染色體初始化是在保證作業(yè)元素先后順序的前提下，通過隨機方法產(chǎn)生初始種群：可分配的作業(yè)元素和相對應的作業(yè)方位序列。具體步驟如下。

1) 在作業(yè)元素集I中，找出所有無前序元素或前序作業(yè)元素已分配完的作業(yè)元素，并且放到集合Y當中。

2) 從Y中隨機選擇一個作業(yè)元素i，并將其跟該元素i在裝配線上的作業(yè)方位d(L,R,E)相組合，作為染色體的當前基因值(i,d)，例如，(2,R)。

3) 重復前面兩個步驟，直到Y中所有作業(yè)元素都分配完成為止，即完成一條染色體的初始化。

4) 重復步驟(1)、(2)、(3)X次，可以得到X條可行染色體，X就是初始化種群的大小。

2.4適應度函數(shù)

裝配線平衡問題的目的就是使平衡率最大化，因此把裝配線的平衡率作為染色體的適應度函數(shù)(式(7))，Eval值越大，表明該染色體越優(yōu)；采用輪盤賭選擇操作，來進行選擇和淘汰，即適應度值越大的染色體，被選擇的概率越大。

(7)

2.5交叉和變異

1)交叉又稱重組，是按較大的概率從群體中選擇兩個個體作為父代，通過交換兩個父代的某些位上的基因，形成兩個不同的子代個體。兩點交叉是指在兩個父代個體的染色體中設置兩個交叉點，根據(jù)指定的交叉概率，交換兩個交叉點之間的部分基因，圖5為兩點交叉示意圖。

圖5　兩點交叉示意圖

2)變異是將染色體中的某些基因進行互相交換，形成一個新的染色體，圖6為變異操作示意圖。

圖6　變異操作示意圖

2.6算法終止條件

通常，當最優(yōu)個體的適應度和群體適應度不再上升時，或者當前進化代數(shù)達到預設的代數(shù)時，算法終止。本文令當前進化代數(shù)達到預設最大遺傳代數(shù)(例如100代)時，遺傳算法終止。

3考慮等待時間的STMALBP仿真方法

上一節(jié)已經(jīng)完成了兩階段求解的第1步，本節(jié)將進行第2步求解，鑒于第1步的結果是在簡化模型下完成求解的，該簡化模型未考慮“等待時間”，因此本節(jié)通過eM-Plant軟件建立考慮“等待時間”的仿真模型，對在簡化模型下求解的備選結果進行仿真評價與分析，求得問題最終解。

在雙邊裝配線中，由于“等待時間”的存在，因此不能把各個工作站中的作業(yè)元素時間之和作為工作站的作業(yè)時間，該等待時間關系可以通過下面的數(shù)學關系來表示，從而滿足節(jié)拍要求。

stmi=max(tl,tr)；l, r ∈P(i), l∈AL, r∈AR。

(8)

stmi+tmi≤C，?i∈I,m=1,2,3，…，M。

(9)

式(8)中stmi表示m型號產(chǎn)品作業(yè)元素i的開始操作時間，其中stmi為m型號產(chǎn)品在工作站(n,d1)中作業(yè)元素i的先行元素l的結束時間tl以及伴隨工作站(n,d2)中作業(yè)元素i的先行元素r的結束時間tr之間的較大值；式(9)表示對于所有作業(yè)元素i都要在節(jié)拍內(nèi)完成(采用一種基于“任務在工位上開始裝配時間”的方法[15])。

eM-Plant軟件是一個面向對象的圖形化的建模和仿真軟件，可以廣泛應用于生產(chǎn)系統(tǒng)的仿真、優(yōu)化[16]。通過eM-Plant建立仿真模型，在模型中把備選解中所有工作站作業(yè)時間相應的“等待時間”考慮進去，圖7為考慮“等待時間”的隨機型雙邊混流裝配線的仿真模型示例圖。

圖7　考慮等待時間的STMALBP仿真模型示例圖

4算例分析

以文獻[10]中的實例問題進行求解分析，該實例是在某冰箱企業(yè)的一條雙邊裝配線上，需要裝配A、B、C、D 4種工藝相似的產(chǎn)品，其中箱體某個部分由20個作業(yè)元素組成，按照最小循環(huán)生產(chǎn)比例投產(chǎn)，設最小循環(huán)生產(chǎn)比例為6∶6∶5∶5，4種產(chǎn)品的綜合作業(yè)先后順序關系如圖8所示。

圖8　4種產(chǎn)品混合作業(yè)先后順序關系圖

A、B、C、D 4種產(chǎn)品的不同作業(yè)元素的作業(yè)時間如表1所示。由于原問題沒有考慮到作業(yè)時間的隨機性，給出的是確定作業(yè)時間；對于一般熟練工而言，作業(yè)時間方差范圍為1.2～2。因此，本文對參考文獻中的作業(yè)時間作一些調(diào)整，取隨機型模型中各個作業(yè)時間的均值為表1中各個作業(yè)時間，方差為1.5(時間單位為s)。

表1　4種產(chǎn)品作業(yè)時間表

鑒于遺傳算法求解的是備選解，因此需要求得多組解，下面通過改變不同遺傳代數(shù)來求一組(求解10次)備選解。在隨機型模型中，預設概率與Φ-1(α)的取值有關，如果Φ-1(α)=1.280，則不超過節(jié)拍的概率為90%；如果Φ-1(α)=1.960，則不超過節(jié)拍的概率為97.5%。根據(jù)以上條件，采用前面的STMALBP簡化模型和遺傳算法在Matlab中來尋找一組較優(yōu)解。算法輸入?yún)?shù)為，預設種群大小X=50，交叉概率Pc=0.7，變異率Mu=0.1，輸入不同的最大遺傳代數(shù)(取50～100之間)，當節(jié)拍C=20，Δ=0.1×C=2，在Φ-1(α)=1.960時，求得結果如表2所示。

表2　一組較優(yōu)分配結果

為了進一步從上述分配結果中篩選出最優(yōu)解，通過eM-Plant軟件對上述備選解進行建模仿真分析。在仿真模型中，考慮作業(yè)“等待時間”，對10組備選分配結果進行仿真，通過修改模型中的隨機數(shù)流，多次運行(每組運行10次)，得到的各個備選方案的平均平衡率如表2所示。以第1個解為例，1{1L2E5L;3R4R11E}表示第1組工作站，工作站組1的左邊分配的作業(yè)元素為：1、2、5，右邊的作業(yè)元素為3、4、11。從表2中可以看出，當不考慮作業(yè)等待時，第1個解的平衡率79%最高，工作站組數(shù)目4也是最小，理論上為最優(yōu)解。通過eM-Plant建模，加入“等待時間”之后運行結果如圖9所示，第4個工作站組作業(yè)時間超過了節(jié)拍20，故而該解對應的分配方案淘汰。通過對所有的候選解進行多次仿真之后，各個備選解的平均平衡率統(tǒng)計結果如表2所示，比較各個備選解在仿真模型多次運行下的平均平衡率，可知最優(yōu)解為第6個，該解對應的工作站組數(shù)目為5，平均平衡率為92.7%。

圖9　仿真模型運行示例圖

(10)

(11)

圖10　不同隨機數(shù)流下運行結果

驗證所輸出的數(shù)據(jù)是否以一定的置信度(90%)在式(10)、(11)所計算的置信區(qū)間內(nèi)，通過計算，結果如表3所示，在α=0.1時，可以認為仿真模型輸出結果以置信度為90%位于置信區(qū)間[0.891，0.963]上。

表3　仿真模型可信性驗證表

通過以上實例表明，本文所提出的基于遺傳算法和仿真分析相結合的兩階段求解方法能夠有效解決隨機型雙邊混流裝配線第1類平衡問題。

5結論

本文針對雙邊混流裝配線平衡問題，提出了基于遺傳算法和仿真分析相結合的隨機型雙邊混流裝配線平衡問題的兩階段求解方法，并通過算例分析表明，該方法可以降低問題建模與求解的復雜性。本文只是對隨機型雙邊混流裝配線第1類平衡問題進行了研究，可以進一步研究第2類平衡問題；其次，在混流裝配線中，往往不能以最小循環(huán)生產(chǎn)比例投產(chǎn)，還需要考慮投產(chǎn)排序給生產(chǎn)帶來的影響，這些都將是后續(xù)研究的方向。

參考文獻：

[1]SALVESON M. The assembly line balancing Problem[J]. Journal of Industrial Engineering, 1955, 6(3):18-25.

[2]陳心德，吳忠. 生產(chǎn)運營管理[M]. 北京：清華大學出版社，2005.

[3]ARMIN S, CHRISTIAN B. State-of-the-art exact and heuristic solution procedures for simple assembly line balancing[J]. European Journal of Operational Research, 2006, 168(6):666-693.

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

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

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

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

WU Erfei, JING Ye, XU Aimin, et al. Two-sided assembly line balancing based on modified genetic algorithm[J]. Computer Integrated Manufacturing Systems, 2007, 13(2):268-274.

[8]?ZCAN U.Multiple-criteria decision-making in two-sided assembly line balancing: a goal programming and a fuzzy goal programming models[J]. Computers & Operations Research, 2009, 36(6): 1955-1965.

[9]陳建行, 張其松. 蟻群算法在裝配線平衡問題中的應用[J]. 計算機時代, 2008(12):20-22.

CHEN Jianhang, ZHANG Qisong. Ant colony algorithm in the application of the assembly line balancing problem[J]. Computer Era, 2008(12):20-22.

[10]楊濤, 魯建廈, 孔令革. 具有并發(fā)操作的雙邊裝配線平衡問題研究[J]. 浙江工業(yè)大學學報, 2011, 39(4): 440-444.

YANG Tao, LU Jiansha, KONG Lingge. Study on balancing problem of two sided assembly line with concurrent operation[J]. Journal of Zhe Jiang University of Technology, 2011, 39(4): 440-444.

[11]宋林, 張則強, 程文明,等.隨機型雙邊裝配線平衡問題的一種啟發(fā)式算法[J]. 工業(yè)工程, 2011, 14(4):129-134.

SONG Lin，ZHANG Zeqiang, CHEN Wenming, et al. Heuristic for two-sided stochastic assembly line balancing[J]. Industrial Engineering Journal, 2011, 14(4):129-134.

[12]于兆勤. 混合型裝配線平衡問題的不確定性仿真研究[J]. 中國機械工程, 2008, 19(11): 1297-1302.

YU Zhaoqin. Simulation of uncertainty for mixed-model assembly line balancing problem[J].China Mechanical Engineering, 2008, 19(11): 1297-1302.

[13]張則強, 余慶良, 胡俊逸,等. 隨機混流裝配線平衡問題的一種混合粒子群算法[J]. 機械設計與研究, 2013, 29(2): 60-63.

ZHANG Zeqiang, YU Qingliang, HU Junyi, et al. Hybrid particle swarm optimization algorithm for balancing problem of stochastic mixed-model assembly line[J].Machine Design and Research, 2013, 29(2): 60-63.

[14]黃衛(wèi)平, 張健, 周支立. 隨機型混合模式裝配線平衡問題的集束搜索算法[J]. 運籌與管理, 2010, 19(6): 20-26.

HUANG Weiping, ZHANG Jian, ZHOU Zhili. A beam search approach to stochastic mixed-model assembly line balancing problem[J]. Operations Research and Management Science, 2010, 19(6): 20-26.

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

WU Erfei. Research on balancing two-sided assembly line[D]. shanghai: Shanghai Jiao Tong University,2009.

[16]施於人. eM-Plant仿真技術教程[M]. 北京：科學出版社, 2009.

[17]肖田元，范文慧. 系統(tǒng)仿真導論[M]. 北京：清華大學出版社, 2010.

A Two-stage Method for Solving the Stochastic Two-sided Mixed-model Assembly Line Balancing Problem

DUAN Yiting, SU Ping, ZHENG Chenming

(School of Electro-mechanical Engineering, Guangdong University of Technology, Guangzhou 510006, China)

Abstract：To reduce the complexity of solving the stochastic two-sided mixed model assembly line balancing problem, a two-stage procedure of combining a genetic algorithm with simulation analysis is proposed. Firstly, a simplified mathematical programming model is formulated ignoring the constraint of precedence relation between the tasks assigned to the same mated-station, and a set of solutions is obtained by using a genetic algorithm based on a sequence combined encoding. Based on the set of solutions, a simulation model that takes all the constraints of the problem into account is developed. The optimal solution (or suboptimal solution) of the problem is obtained through simulation analysis and evaluation. The analysis of an illustrative example shows that the complexity of solving the problem can be greatly reduced and a satisfactory solution can be obtained with the proposed method.

Key words：two-sided assembly line balancing; stochastic; mixed-model; genetic algorithms; simulation

收稿日期：2015- 03- 06

作者簡介：段移庭(1989-)，男，湖南省人，碩士研究生，主要研究方向為離散事件系統(tǒng)仿真、裝配線平衡問題.

doi:10.3969/j.issn.1007- 7375.2016.02.020

中圖分類號：TP205；TP301.6；N945.13

文獻標志碼：A

文章編號：1007-7375(2016)02- 0134- 09