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

鄭晨鳴，段移庭

（廣東工業大學機電工程學院，廣東廣州 510006）

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

鄭晨鳴，段移庭

（廣東工業大學機電工程學院，廣東廣州 510006）

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

混合產品；U型裝配線；作業時間隨機；遺傳算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 初始種群的產生

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

步驟1 設種群大小計數器size=1。

步驟2 隨機產生一個可行解：

（1）設作業元素關系圖形成的作業優先矩陣為W，給定節拍C，記初始工作站數l=1，工作站空閑時idle_time=C，記作業分配循環次數。

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

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

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

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

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

步驟5 結束。

2.3 適應度函數設計

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

2.4 遺傳算子選擇

2.4.1 選擇

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

2.4.2 交叉

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

圖3 ch1的作業分配方案

圖4 ch2的作業分配方案

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

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

2.4.3 變異

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

圖7 產品1、2、3的聯合作業優先圖

3 實例分析

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

表1 產品1、2、3的作業時間表

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

4 結論

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

表2 最優解方案

［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］.機電產品開發與創新，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］黃衛平，張健，周支立.隨機型混合模式裝配線平衡問題的集束搜索算法［J］.運籌與管理，2010，19（6）：20-26.

［22］朱華炳，王龍，涂學明，等.隨機型混流裝配線動態排序問題研究［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年生，江西景德鎮人，碩士研究生。研究領域：生產計劃與調度（工業工程）。

(編輯：阮 毅)

2015－04－14