鄭晨鳴，段移庭

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

隨機型混合U型裝配線的平衡研究

鄭晨鳴，段移庭

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

針對混合產(chǎn)品和作業(yè)元素時間隨機的U型裝配線平衡問題，建立了數(shù)學模型并提出一種改進的遺傳算法求解。在給定的節(jié)拍和完工率下，以最小工作站數(shù)和各產(chǎn)品負荷均勻為目標，設計改進的遺傳算法求解作業(yè)元素分配序列。最終結合實例驗證方法是有效的。

混合產(chǎn)品；U型裝配線；作業(yè)時間隨機；遺傳算法

U型裝配線平衡問題是直線型裝配線平衡問題在布局上的一個延伸。因此在考慮U型裝配線平衡問題研究現(xiàn)狀前有必要描述下直線型裝配線平衡的思路發(fā)展。裝配線平衡問題最早由Salveson的文獻[1]中提出，定義為將一系列作業(yè)元素按照一定先后次序分配到裝配線上的各個工作站內，滿足各個工作站內的作業(yè)元素時間總和不超過一定節(jié)拍的同時，使得每個工作站的空閑時間最小，然后用動態(tài)規(guī)劃和最短路徑等方法求解裝配線平衡問題。1966年Arcus A.L在文獻[2]中提出一種COMSOAL(Computer Method of Sequenc?ing Operations for Assembly Line)的方法來解決裝配線平衡問題，這種方法綜合了計算機、隨機抽樣、蒙特卡洛等技術，是啟發(fā)式算法外的另一種有效解決方法。

在裝配線平衡問題發(fā)展了40多年后的1994年，Miltenberg J在文獻[3]中首次提出JIT模式下的U型裝配線平衡問題（U-Line Balancing Prob?lem，ULBP），即U型裝配線在平衡分析時可以從前后雙向搜索作業(yè)元素，在U型裝配線上首尾兩個作業(yè)元素是可以被分配到一個工作站的，這是U型裝配線在作業(yè)分配時和直線型裝配線的明顯區(qū)別。1998年Miltenberg J的學生Sparling D在文獻[4]中率先研究了混合U型裝配線的平衡問題，文章提出將混合裝配線平衡問題通過得出綜合作業(yè)先后順序圖來等效為單一品種裝配線平衡問題，提出裝配線作業(yè)分配和投產(chǎn)排序都會影響到U型混流裝配線的平衡，并在文獻[5]中對U型裝配線平衡理論和實際應用進行了總結。同年Ajen?blit D.A和Wainwright R.L在文獻[6]中用遺傳算法優(yōu)化ULBP的兩個目標：最小化工作站總的空閑時間和均衡工作站負荷，同時提出遺傳算法是求解ULBP問題的優(yōu)良選擇。1999年Scholl A和Klein R在文獻[7]中提出ULO(U-line optimizer)方法，ULO是一種在利用分支定界法設定的程序中高效尋找最優(yōu)解的過程，最多可以求解297個作業(yè)元素的U型裝配線平衡問題。2001年Erel E，Sabuncuoglu I和Aksu B.A在文獻[8]中運用基于模擬退火算法求解ULBP。2005年Agpak K和Gok?cen H在文獻[9]中用最短路徑法求解ULBP，之后于2006年用目標規(guī)劃方法求解了ULBP。

混流裝配線是可以在同一裝配線上混合的、連續(xù)的裝配幾種結構相近、工藝相似產(chǎn)品的裝配線。首次解決混流裝配線平衡問題的是Thomo?Poufos N.T，1967年他在文獻[10]中運用聯(lián)合先后順序圖的概念把混流裝配線轉化為單一品種裝配線來處理，從而把單一品種裝配線的平衡技術和方法運用到混流裝配線后解決了混流裝配線平衡問題。1970年Roberts S.D和Villa C.D在文獻[11]建立了整數(shù)規(guī)劃模型來求解混流裝配線的平衡問題。2001年Korkirnazel T和Meral S在文獻[12]提出了JIT的兩個目標：(1)工作站間的負載均勻；(2)零部件消耗率均勻。重點討論零部件消耗率為目標保證兩個方面：(1)產(chǎn)品生產(chǎn)量與需求相當；(2)制造過程中零部件使用率始終保持穩(wěn)定。2002年Joseph B等在文獻[13]提出用新的啟發(fā)式算法解決在面向訂單情況下的混流裝配線平衡問題。這是因為傳統(tǒng)的裝配線平衡問題只考慮最小化工位數(shù)，但是在實際生產(chǎn)中，生產(chǎn)效率才是企業(yè)最看重的因素。2005年Agpak K和Gokcen H在文獻[14]提出用“0-1整數(shù)規(guī)劃模型”來求解混流裝配線問題。2004年Simaria A.S和Vilarinho P.M在文獻[15]提出用迭代基因算法來求解混流裝配線平衡問題，優(yōu)化目標是給定操作工人數(shù)求得最大化生產(chǎn)率。2007年陸葉、蘇平在文獻[16]中通過改進的遺傳算法和系統(tǒng)實現(xiàn)的方法分析了混合裝配線的平衡問題。2008年于兆勤等在文獻[17]中利用了遺傳算法和仿真分析相結合的方法分析了混合裝配線平衡問題，主要解決的是混合裝配線中由于產(chǎn)品作業(yè)時間的差異帶來的工作站間負荷不均勻的問題。

隨機型裝配線就是作業(yè)時間隨機的裝配線（Stochastic Assembly Line），對應的就是隨機型裝配線平衡問題（Stochastic Assembly Line Balancing Problems）。Moodie C.L和Young H.H于1965年在文獻[18]最早研究不確定作業(yè)時間的裝配線平衡問題，方法還是先假設作業(yè)時間是服從正態(tài)分布的隨機變量來求解的。1995年Nkasu M.M和Leung K.H最早在文獻[19]采用改進的COMSOAL方法分別假設模擬了作業(yè)時間服從正態(tài)分布、指數(shù)分布、伽馬分布、均勻分布和韋布爾分布下的裝配線平衡問題，同時對結果進行了詳細的統(tǒng)計分析。1998年Urban T.L在文獻[20]利用兩階段的線性整數(shù)規(guī)劃方法建立了概率模型對不超過28個作業(yè)元素的裝配線平衡問題求得了最優(yōu)解。2010年黃衛(wèi)平等在文獻[21]中運用集束搜索算法對隨機型混合模式裝配線平衡問題進行了求解。2013年朱華炳等在文獻[22]中研究了隨機型混流裝配線動態(tài)排序問題。2006年Chiang W.C等在文獻[23]提出一種混合啟發(fā)式算法來求解中等規(guī)模的SUAL?BP。2012年Seyed M.K等在文獻[24]中提出了一種求解U型混流裝配線第一類平衡問題的方法，即通過以最小化工作站數(shù)和最大化裝配線完工率來求解。2013年Chun-Hung C等在文獻[25]中提出了用遺傳算法來搜索U型裝配線平衡問題的最優(yōu)解。

到目前為止，關于作業(yè)時間隨機的裝配線論文研究還是相對其他方面的研究較少的，本文在研究作業(yè)隨機的同時，還需要考慮混合產(chǎn)品對混流裝配線平衡結果的影響。而無論是作業(yè)時間隨機、混合產(chǎn)品還是U型布置的裝配線問題都是目前企業(yè)中運用非常廣的元素，本文對于包含這三種元素的裝配線平衡問題進行研究，是符合目前企業(yè)制造生產(chǎn)實際需求的。

1 隨機型混合U型裝配線平衡問題的描述與數(shù)學模型

1.1 隨機型混合U型裝配線平衡問題的描述

在定義模型之前，首先假設：（1）優(yōu)先約束對于所有產(chǎn)品都是一致的（對任一產(chǎn)品，如果作業(yè)i與作業(yè)j存在優(yōu)先關系，則對于其他產(chǎn)品亦是如此）；（2）作業(yè)在工作站內的分配對所有產(chǎn)品都是一致的（假設作業(yè)i被分配到j工作站，則對于所有產(chǎn)品的作業(yè)i都被分配到了j工作站）；（3）忽略工作站中操作人員的行走時間。

裝配線有N個作業(yè)元素，i=1，2，…，N；混合產(chǎn)品的品種數(shù)量為M，m=1，2，…，M；工作站數(shù)量為J，j=1，2，…，Jmax。設在一個計劃期T內，對第m種產(chǎn)品的需求量為Dm，則對M種產(chǎn)品的總需求量第m種產(chǎn)品的需求比平均生產(chǎn)節(jié)拍：

此公式計算的工作站數(shù)是最小值。本文描述的是混合產(chǎn)品隨機時間作業(yè)，在分配作業(yè)的時候，由于不同產(chǎn)品在同一作業(yè)時間的差異性和隨機性的影響，會導致實際所需的工作站數(shù)量大于Jmin。例如裝配線上有較多作業(yè)的平均作業(yè)時間較長甚至接近平均節(jié)拍，在分配這類作業(yè)時對應的工作站內已經(jīng)分配部分作業(yè)，剩余的作業(yè)時間不足以分配這類作業(yè)，按照作業(yè)先后順序約束，該作業(yè)只能分配到下一個工作站中，導致當前工作站的空閑時間很長，裝配線所需工作站數(shù)增加。同時按照平均負荷來計算工作站數(shù)能夠滿足需求，但由于不同品種產(chǎn)品在少數(shù)作業(yè)可能存在比較大的差異，致使個別品種產(chǎn)品在差異相對應的工作站的作業(yè)時間超出根據(jù)計劃量得出的平均節(jié)拍，在這種情況下也會增加實際的工作站數(shù)。對于U型裝配線的作業(yè)分配，以上兩種情況也會對裝配線作業(yè)分配有一定影響。但相對于傳統(tǒng)的直線型裝配線，以上情況對U型線影響較小。因為U型裝配線可以前向、后向和雙向分配，在出現(xiàn)平均作業(yè)時間較長的作業(yè)時分配方法比較靈活。因此本文在對平衡問題進行算法求解時，會根據(jù)作業(yè)分配需求對工作站數(shù)進行調整，初始值為Jmin，在求解過程中會根據(jù)個工作站內的平均負荷和瞬時負荷來對初始值進行修正，下文中提到的Jmax值是修正過程中出現(xiàn)的最大值。

當裝配線開始運行后，各工作站的負荷比較均衡的時候，站間的等待和阻塞時間較短，各工作站的利用率較高，生產(chǎn)效率提高。而當其負荷不均衡時產(chǎn)生的結果就會相反。因此工作站的負荷均衡在裝配線平衡問題中是非常重要的，本文在考慮最小化工作站數(shù)的同時，也把各工作站的負荷均衡設為優(yōu)化目標。描述為：

混合產(chǎn)品在同一作業(yè)元素上的作業(yè)時間可能會存在比較大的差距，這種情況也會使得裝配線工作站利用率和生產(chǎn)效率下降，因此本文也把各工作站第m種產(chǎn)品負荷均衡設為優(yōu)化目標，描述為

1.2 隨機型混合U型裝配線平衡問題的數(shù)學模型

式（1）表示平均生產(chǎn)節(jié)拍；式（2）是工作站的初始值；式（3）、（4）、（5）是目標函數(shù)；式（6）保證每一個作業(yè)元素分配到唯一工作站（xij表示如果作業(yè)元素i被前向即U型線前端分配到工作站j，則xij=1，否則xij=0；yij表示如果作業(yè)元素i被后向即U型線后端分配到工作站j，則yij= 1，否則yij=0）；式（7）和式（8）保證了作業(yè)元素按照U型裝配線分配原則進行分配且不違反作業(yè)間優(yōu)先順序關系，作業(yè)元素優(yōu)先關系集式（9）計算了第m種產(chǎn)品在工作站j內的作業(yè)總時間；式（10）確保了每個工作站的平均負荷不超過給定節(jié)拍C；式（11）是本文的概率約束模型，α代表U型線上的完工率，zα為標準正態(tài)分布的上α分位點，模型代表了在一定完工率α下各工作站的平均負荷不超過給定節(jié)拍。

2 隨機型混合U型裝配線平衡問題的遺傳算法求解

圖1 改進的遺傳算法流程圖（GEN為當前代數(shù)，Pc為交叉概率，Pm為變異概率）

裝配線平衡問題實際上是作業(yè)元素的分配問題，屬于組合優(yōu)化問題。即在滿足作業(yè)先后順序條件及各工作站的平均負荷不超過平均節(jié)拍這兩個約束條件下，將裝配線的作業(yè)元素分配到裝配線上各個工作站中，并使得目標函數(shù)最小。遺傳算法是解決這類問題的一種有效方法，但是遺傳算法在求解這類問題時容易陷入局部最優(yōu)，因此本文運用一種改進遺傳算法以求解隨機型混合U型裝配線的平衡問題。

2.1 基于序列組合的編碼方式

本文采用序列編碼方式，按照U型裝配線的分配原則將作業(yè)元素先后分配到各工作站。如圖1所示，每個作業(yè)元素對應一個基因位排成一排，當作業(yè)元素被全部分配完成后，一排基因位即對應一條基因串即編碼的染色體，基因串從左向右的順序代表了作業(yè)元素的分配順序。解碼的過程即按照按照染色體中的基因順序分配作業(yè)元素至各工作站，并滿足在給定完工率下分配至各工作站中所有作業(yè)元素的時間和不超過給定的節(jié)拍。

圖2 一組基因串編碼與解碼

2.2 初始種群的產(chǎn)生

初始種群是一組滿足約束條件分配后的作業(yè)序列組成的個體。即前向與后向或者同時前后向分配作業(yè)元素到工作站，同時滿足作業(yè)優(yōu)先關系和個工作站總時間不超過給定節(jié)拍的約束。隨機產(chǎn)生一組可行作業(yè)元素序列并按照上述編碼方式編碼，循環(huán)一定次數(shù)后形成初始種群，循環(huán)的次數(shù)即種群的大?。╬opsize）。初始種群產(chǎn)生的步驟如下。

步驟1 設種群大小計數(shù)器size=1。

步驟2 隨機產(chǎn)生一個可行解：

（1）設作業(yè)元素關系圖形成的作業(yè)優(yōu)先矩陣為W，給定節(jié)拍C，記初始工作站數(shù)l=1，工作站空閑時idle_time=C，記作業(yè)分配循環(huán)次數(shù)。

（2）對矩陣W進行豎列和橫行搜索，如第i列全為0，表明i代表的作業(yè)沒有前序作業(yè)；如第j行全為0，則j代表的作業(yè)沒有后序作業(yè)。將沒有前序和后序作業(yè)的作業(yè)元素記錄到表A中。當表A為空時，表示作業(yè)元素全部分配完畢則程序終止。否則轉（3）。

（4）從表B中隨機選擇一個作業(yè)元素i作為最終分配作業(yè)元素分配到工作站中，記

（5）更新優(yōu)先矩陣W，將分配到表B中的作業(yè)元素i在優(yōu)先矩陣中對應的行和列都去掉并轉（2）。

步驟3 對步驟2生成的可行解進行編碼。

步驟4 size=size+1，如果size≤popsize轉向步驟2，否則轉步驟5。

步驟5 結束。

2.3 適應度函數(shù)設計

本文的目標函數(shù)是求最小值，所以適應度函數(shù)設計為

2.4 遺傳算子選擇

2.4.1 選擇

選擇操作采用最優(yōu)保存策略和輪盤賭選擇相結合的方法。先按照個體對應的適應度值從高到低排序，排位較前的若干個體可以直接復制到下一代種群中，剩余的個體選擇輪盤賭法進行篩選。此方法在保存了種群中優(yōu)良個體的同時也不會降低種群中個體的多樣性。

2.4.2 交叉

交叉操作采用單點順序交叉法，在遺傳過程中保留父代中優(yōu)良作業(yè)序列，避免往后可能產(chǎn)生不可行解，提高遺傳交叉效率。從保留下來的父代種群中任意選取2個基因串，如圖3和4中的基因串ch1與ch2為2條不同的作業(yè)分配序列，隨機在基因串中選取一個點，即交叉點。如圖5所示，在交叉點上將ch1與ch2分成左右兩個部分。取ch1的左邊部分，并在ch2中將ch1左邊部分的基因刪除，剩余的基因按照原來的順序排列。將ch1的左部和以ch2按上述步驟處理后得到的基因位右部，重新組成一個基因串ch1'，同理可得ch2'。ch1'與ch2'的解碼結果如圖6所示。用產(chǎn)生的后代ch1'和ch2'代替ch1與ch2加入新種群中。

圖3 ch1的作業(yè)分配方案

圖4 ch2的作業(yè)分配方案

圖5 ch1和ch2的單點順序交叉

圖6 ch1'和ch2'的解碼過程

2.4.3 變異

按照一定的變異概率Pm，進行變異操作。先在種群中隨機選擇一個個體，在該個體基串上隨機選擇兩個基因座，對這兩個基因座上的基因值以Pm概率進行交換。由于此操作可能會產(chǎn)生無效個體，因此完成操作后需要對變異操作產(chǎn)生的新個體進行有效性檢驗，對于產(chǎn)生的無效個體，需要再次進行任務分配而成為有效個體為止。

圖7 產(chǎn)品1、2、3的聯(lián)合作業(yè)優(yōu)先圖

3 實例分析

如圖所述，某類產(chǎn)品的三種型號在某一時期內的計劃產(chǎn)量分別為D1=100臺，D2=50臺，D3=50臺。在一個生產(chǎn)循環(huán)內，r=50，d1=2臺，d2=1臺，d3=1臺。采用改進后的遺傳算法，參數(shù)設定為：種群規(guī)模為pop_size=60，遺傳代數(shù)為100，變異概率Pm=0.8，交叉概率Pc=0.08。圖7是3種產(chǎn)品的聯(lián)合作業(yè)優(yōu)先圖，表1是三種產(chǎn)品的作業(yè)時間表，其中數(shù)字代表(μmi，σmi) ，單位是min。

表1 產(chǎn)品1、2、3的作業(yè)時間表

由式1可得C=2.2 min（時間利用率設90%），由式2可得Jmin=8（設完工率α=0.95，對應的zα= 1.645），采用上述遺傳算法，并對算法編程后，求得的最優(yōu)解如表2所示。

4 結論

本文針對隨機型混合U型裝配線平衡問題中作業(yè)時間不確定性的問題建立了數(shù)學模型，提出了改進的遺傳算法，系統(tǒng)地描述了混合產(chǎn)品在U型裝配線上的運用。由于約束的增多，當實際情況中產(chǎn)品種類過多時，算法較為復雜，因此針對不同的實際情況需要對其進行系統(tǒng)仿真來輔助算法的運用。其次混合產(chǎn)品的排序也會對工作站負荷產(chǎn)生影響，這些問題將是后續(xù)研究的方向。

表2 最優(yōu)解方案

［1］Salveson M.The assembly line balancing Problem［J］. Journal of Industrial Engineering，1955，6（3）：18-25.

［2］Arcus A.L.COMSOAL—A computer method of sequenc?ing operations for assembly lines［J］.International Jour?nal of Production Research，1966（4）：259-277.

［3］Miltenburg J，Wijingaard J.The U-line balancing prob?lem［J］.Management Science，1994，40（10）：1378-1388.

［4］Sparling D，Miltenburg J.The mixed-model U-line bal?ancing problem［J］.International Journal of Production Research，1998（36）：485-501.

［5］Miltenburg J.U-shaped Production lines：A review of theory and practice［J］.International Journal of Produc?tion Economics，2001，70（3）：201-214.

［6］Ajenblit D.A，Wainwright R.L.Applying genetic algo?rithms to the U-shaped assembly line balancing problem［C］.Proceedings of the 1998 IEEE International Confer?ence on Evolutionary Computation，1998：96-101.

［7］ Scholl A， Klein R.ULINO： Optimally balancing U-shaped JIT assembly lines［J］.International Journal of Production Research，1999，37（4）：721-736.

［8］Erel E，Sabuncuoglu I，Aksu B.A.Balancing of U-type assembly systems using simulated annealing［J］.Inter?national Journal of Production Research，2001（39）：3003-3015.

［9］Agpak K，Gokcen H.A shortest route formulation of sim?ple U-type assembly line balancing problem［J］.Ap?plied Mathematical Modeling，2005（29）：373-380.

［10］ ThomopoulosN.T.LineBalancing-sequencingfor Mixed-model Assembly Line［J］.Management Sci?ence，1967（14）：859-875.

［11］Roberts S.D，Villa C.D.On a Multi-Product Assembly Line balancing Problem ［J］.AIIE Transactions，1970（2）：361-364.［12］Korkmazel T，Meral S.Bicriteria Sequencing Methods for the Mixed-model Assembly Line in Just-in Time Pro?duction Systems［J］.European Journal of Operational Research，2001（131）：188-207.

［13］Joseph B，Ezey M.D，Jacob R.Mixed Model Assembly Line Design in a Make-to-order Environment［J］. Computers&Industrial Engineering， 2002（41）：405-421.

［14］Agpak K，Gokcen H.Assembly Line Balancing：Two Resource Constrained Cases［J］.Production Econom?ics，2005（96）：129-140.

［15］ Simaria A.S，Vilarinho P.M.A Genetic Algorithm Based Approach to the Mixed-model Assembly Line Bal?ancing Problem of Type II［J］.Computers&Industrial Engineering，2004（47）：391-407.

［16］陸葉，蘇平.混合裝配線平衡問題的建模與分析［J］.機電產(chǎn)品開發(fā)與創(chuàng)新，2007（5）：110-113.

［17］于兆勤.混合型裝配線平衡問題的不確定性仿真研究［J］.中國機械工程，2008，19（11）：1297-1302.

［18］Moodie C.L，Young H.H.A heuristic method of assem?bly line balancing for assumptions of constant or variable work element times［J］.Journal of Industrial Engineer?ing，1965，16（1）：23-29.

［19］Nkasu M.M，Leung K.H.A stochastic approach to as?sembly line balancing［J］.International Journal of Pro?duction Research，1995，33（4）：975-991.

［20］ Urban T.L.Optimal balancing of U-shaped assembly lines［J］.Management Science， 1998（44）：738-741.

［21］黃衛(wèi)平，張健，周支立.隨機型混合模式裝配線平衡問題的集束搜索算法［J］.運籌與管理，2010，19（6）：20-26.

［22］朱華炳，王龍，涂學明，等.隨機型混流裝配線動態(tài)排序問題研究［J］.組合機床與自動化加工技術，2013，11（4）：114-118.

［23］Chiang W.C，Urban T.L.The stochastic U-line balanc?ing problem： A heuristic procedure［J］.European Journal of Operational Research，2006，175（3）：1767-1781.

［24］Seyed M.K，Neda M，Masoud R.Mixed model U-line balancing type-1 problem： A new approach［J］. Journal of Manufacturing Systems，2012，31（2）：131-138.

［25］Chun-Hung C，Angappa G，Kin-Chuen H.Genetic search and the U-line balancing problem［J］.Interna?tional journal of industrial and systems engineering，2013，14（2）：414-440.

Stochastic Mixed-Model U-Shaped Assembly Line Balancing Problem

ZHENG Chen-ming，DUAN Yi-ting
（Guangdong University of Technology，Guangzhou510006，China）

For the U-shaped assembly line balancing problem of mixed products and stochastic work elements，established the mathematical model and an improved genetic algorithm is put forward.Under the given production tact time and completion rate，with the minimum number of workstations and uniform load between each product as the goal，design the improved genetic algorithm to solve allocation sequence question of the work elements.Finally combine instance to verify the effective.

mixed products；U-line balancing；stochastic；genetic algorithms

TH163

A

1009－9492(2015)10－0027－06

10.3969/j.issn.1009-9492.2015.10.007

鄭晨鳴，男，1991年生，江西景德鎮(zhèn)人，碩士研究生。研究領域：生產(chǎn)計劃與調度（工業(yè)工程）。

(編輯：阮 毅)

2015－04－14