劉儼后，左敦穩(wěn)＋ ，張 丹

（1．南京航空航天大學 機電學院，江蘇 南京 210016；

2．江蘇省精密與微細制造技術重點實驗室，江蘇 南京 210016）

0 引言

裝配在產品生命周期中占有重要地位，裝配質量對保證機械產品的最終使用性能起到了極其重要的作用。據統(tǒng)計，在整個機械制造過程中約有40%的勞動用于裝配作業(yè)，產品裝配成本占總制造成本的50%左右［1－2］。由于裝配作業(yè)的復雜程度較高，目前大部分裝配工作仍然由工人手工完成，工人的操作速度決定了裝配生產流程的進度。不同工人具有不同的技能熟練程度，甚至同一個工人在不同狀態(tài)下（體力、精神狀態(tài)等）的操作速度也會變化［3］，人類勞動的這種特征決定了作業(yè)時間具有隨機性，據統(tǒng)計，這種隨機偏差可達20%左右［4］。除工人的自身因素外，機器設備故障、零部件供應不穩(wěn)定等都將導致作業(yè)時間的波動。

根據作業(yè)時間，裝配線可分為隨機型裝配線（作業(yè)時間隨機波動）和確定型裝配線（作業(yè)時間是一個常量）。造成作業(yè)時間的波動不確定因素在實際生產中是不可避免的，相對于確定型裝配線，對隨機型裝配線的研究具有更加廣泛的現實意義，但是目前這方面的研究較少。文獻［4］以最小化裝配線平衡延遲為目標，在啟發(fā)式算法的搜索過程中適時調整作業(yè)時間允許誤差，在盡量小的誤差范圍內完成裝配作業(yè)的分配；文獻［5］以最小化期望超載時間和最小化超載概率為優(yōu)化目標，對多種產品混流裝配的排產工作進行研究，給出了隨機作業(yè)時間混流組裝線在給定排產下期望超載時間的建模與計算方法；文獻［6］根據作業(yè)時間的隨機變量分布函數計算工位完工率，將完工率作為一個約束條件，并以未完工率的累加和最小作為一項評價指標，建立了優(yōu)化目標模型，進行裝配平衡問題的研究；文獻［7］將停線等待成本和負荷超載成本計入目標函數，以人力成本耗費最省作為生產平衡的優(yōu)化目標；文獻［8］分別研究了在有中間緩存機制和無中間緩存機制條件下，工位作業(yè)時間波動造成的未完工率對固定節(jié)拍生產線生產效率的影響。

裝配線平衡問題是裝配生產中的突出問題，它可分為：①固定生產節(jié)拍，最小化工位數目（第1類平衡問題）；②給出工位數目，最小化生產節(jié)拍（第2類平衡問題）；③已知生產節(jié)拍和工位數目，均衡裝配線的負荷（第3類平衡問題）。解決裝配線平衡問題的方法分為精確方法、啟發(fā)式方法和元啟發(fā)式方法。精確方法求解時間較長，不能很好地解決大規(guī)模復雜的實際問題，人們更多地采用啟發(fā)式方法和元啟發(fā)式方法，特別是稱為智能優(yōu)化算法（如遺傳算法、蟻群算法和粒子群優(yōu)化算法）的元啟發(fā)式方法能夠很好地解決裝配線平衡問題［6］。裝配線平衡是一種基于作業(yè)時間的調度，與確定型裝配線相比，隨機型裝配線平衡問題的求解更加困難，作業(yè)時間的隨機波動會在一定概率下使得求解方法失效，從而最終導致求解結果偏離最優(yōu)解。本文研究分析了隨機作業(yè)時間對元啟發(fā)式方法和啟發(fā)式方法的失效影響，并設計了一種雙染色體遺傳算法，實現了隨機型裝配線的平衡。

1 作業(yè)時間隨機性對求解方法的失效影響

1．1 元啟發(fā)式方法失效分析

元啟發(fā)式方法通常使用亂數搜尋技巧，根據目標函數值等信息，通過個體變異、組合等方法，不斷更新候選解域以進行輪次迭代。一般用均衡指數SI和平衡率E等作為裝配線平衡方案評價指標［4］，下面以SI和E為例，討論隨機作業(yè)時間對元啟發(fā)式方法評價指標失效的影響。

式中：m表示工位數量；C表示生產節(jié)拍；作業(yè)元素集K＝｛k＝1，2，…，n｝，n為作業(yè)數量，tk表示作業(yè)k的作業(yè)時間；TSr（r＝1，2，…，m）表示工位Sr的作業(yè)時間。在實際生產中，最大作業(yè)時間工位往往成為制約生產線節(jié)拍的瓶頸環(huán)節(jié)，取C＝max（TSr），式（1）和式（2）轉述為：

在考慮作業(yè)時間隨機性時，一般將作業(yè)時間視為一個服從正態(tài)分布的隨機變量，即t～N（μ，σ2）［4］，則Sr的作業(yè)時間TSr～N（μr，σr2）。對于確定型裝配線，參數σ＝0即 max（TSr）＝max（μr）；對于隨機型裝配線，需要同時考慮參數μ和σ才能確定最大作業(yè)時間工位。例如有m＝2的裝配線，S1作業(yè)時間 TS1～N（μ1，σ21），S2作業(yè)時間 TS2～N（μ2，σ22），其中μ1＜μ2。忽略參數σ時，max（TSr）＝max（μr）＝μ2，S2為最大作業(yè)時間工位；而在隨機作業(yè)時間條件下，如圖1所示，TS1將以概率β大于TS2，即在概率β下S1成為最大作業(yè)時間工位。下面計算圖1中重疊區(qū)域的面積β＝P（TS1＞TS2），用變量xr代替TSr。

在實際問題中，對隨機變量x～N（μ，σ2）來說，P（｜x－μ｜＞3σ）≈0．003，這在概率理論中稱為小概率事件，這種近似的說法被一些實際工作者稱為正態(tài)分布的“3σ原則”，根據3σ原則修正式（7）中的積分區(qū)間如式（8）所示。

取TS1～N（50，102），TS2～N（60，122）為例，將式（5）和式（6）代入式（8），計算得P（TS1＞TS2）＝25．84%，即工位S1以25．84%的概率成為最大作業(yè)時間工位，在此概率下式（3）和式（4）所示的評價指標SI和E失效。

當m＝3時，TS1～N（μ1，σ21），TS2～N（μ2，σ22），TS3～N（μ3，σ23），μ1＜μ3，μ2＜μ3。用變量xr代替TSr，計算SI和E的失效率。

以TS1～N（50，112），TS2～N（40，102），TS3～N（60，122）為例，P（TS1＜TS3）＝73．32%，P（TS2＜TS3）＝90．23%，代入計算得P［（t1＞t3）∪（t2＞t3）］＝33．84%。由式（9）可推導一般情況m個工位時，SI和E的失效率如式（10）所示。

式（10）中P（xr＜xm）是小于1的正數，適應度評價規(guī)則失效率對工位數m是敏感的，隨著m的增大，評價指標SI和E因作業(yè)時間隨機波動而失效的概率將顯著增加。

1．2 啟發(fā)式方法失效分析

裝配線平衡中的啟發(fā)式信息一般通過作業(yè)優(yōu)先分配規(guī)則給出，包括最大作業(yè)時間優(yōu)先、最大平均作業(yè)時間優(yōu)先、最大后續(xù)任務數優(yōu)先、最大直接后續(xù)任務數優(yōu)先等［4］。對基于時間的一類啟發(fā)規(guī)則，作業(yè)時間的隨機波動在一定的概率下會導致規(guī)則失效。下面以最大作業(yè)時間規(guī)則為例，討論隨機作業(yè)時間對啟發(fā)規(guī)則失效的影響。

作業(yè)數n＝2的作業(yè)集K＝｛k＝1，2｝，作業(yè)時間t1～N（μ1，σ21），t2～N（μ2，σ22），其中μ1＜μ2。忽略σ時，t1＝μ1＜μ2＝t2；而在考慮隨機性影響時，如圖1所示，t1將以概率β大于t2，即在概率β下t1成為最大作業(yè)時間。啟發(fā)規(guī)則失效率為圖1中重疊區(qū)域的面積β＝P（t1＞t2），用變量xk代替tk，則失效率為：

作業(yè)數n＝3的作業(yè)集K＝｛k＝1，2，3｝，作業(yè)時間t1～N（μ1，σ21），t2～N（μ2，σ22），t3～N（μ3，σ23），其中μ1＜μ2＜μ3。事件（x1＞x2），（x1＞x3），（x2＞x3）是非獨立事件，例如在事件（x1＞x2），（x2＞x3）發(fā)生時，事件（x1＞x3）是概率為1的全概率事件。用變量xk代替tk，則失效率為：

推廣到作業(yè)集K＝｛k＝1，2，…，n｝的一般情況下，tk～N（μk，σk2），其中μk＜μk＋1（k＝1，2，…，n－1），即作業(yè)集是按照作業(yè)時間期望值由小到大排序，作業(yè)時間的隨機波動破壞排列的順序時，啟發(fā)規(guī)則失效，用變量xk代替tk，則失效率為：

式（13）與式（10）不盡相同，但基于時間的啟發(fā)規(guī)則失效率對作業(yè)集規(guī)模同樣也是敏感的，隨著n的增大，啟發(fā)規(guī)則因作業(yè)時間隨機波動而失效的概率也將顯著增加。

2 隨機型裝配線平衡問題描述

大多數研究裝配線平衡的文獻都是針對作業(yè)時間期望值μ進行研究的，而忽視了決定作業(yè)時間取值的另一參數σ的影響；或者考慮了隨機性影響，但僅將完工率作為一項評價指標［6，9－10］，沒有針對σ參數進行尋優(yōu)。

例如兩工位裝配線的總作業(yè)時間t～N（μ，σ2），在平衡方案A和B下，工位作業(yè)時間為tA1和tA2以及tB1和tB2，且滿足μA1＝μA2，σ2A1＞σ2A2，μB1＝μB2，σ2B1＝σ2B2，由正態(tài)分布的線性相加性，得μ＝μA1＋μA2＝μB1＋μB2和σ2＝σ2A1＋σ2A2＝σ2B1＋σ2B2，故μA1＝μA2＝μB1＝μB2和σ2A1＞σ2B1＝σ2B2＞σ2A2，即σA1＞σB1＝σB2＞σA2。

定義1 標準正態(tài)分布x～N（0，1）的α分位點為Z（1－α），即 P（x＞Z（1－α））＝1－α，P（x＜Z（1－α））＝α，則作業(yè)時間t～N（μ，σ2）存在概率P［（t－u/σ）＜Z（1－α）］＝α，即 P（t＜u＋Z（1－α）σ）＝α；若以C＝u＋Z（1－α）σ為生產節(jié)拍，則作業(yè)完工率為α，定義Z（1－α）為作業(yè)的α完工率點，記為CR（α）。

CR（α）＝Z（1－α）的取值由標準正態(tài)分布表獲得，只與α相關，為保證各工位的完工率不低于α，方案A的生產節(jié)拍為CA＝max（μA1＋CR（α）σA1，μA2＋CR（α）σA2），方案B的生產節(jié)拍為CB＝max（μB1＋CR（α）σB1，μB2＋CR（α）σB2），則CA＝μA1＋CR（α）σA1＞μB1＋CR（α）σB1＝CB，即在相同的完工率下，方案B能夠獲得更小的生產節(jié)拍。又如圖2所示，在給定某節(jié)拍C′和某完工率α′下，滿足μA1＋CR（α′）σA1＞C′＞μB1＋CR（α′）σB1，則方案A 在α′下將發(fā)生未完工停線事故，方案B在α′下能保證完工。而在確定型裝配線平衡中μA1＝μA2＝μB1＝μB2，方案A 和B是等效的。

在文獻［6］的隨機型裝配線平衡模型中，以各工位完工率作為一個約束條件，并將未完工率之和ΣPr（Pr＝P（TSr＞C），即工位Sr的未完工率）最小作為一項評價指標。方案A和B的未完工率情況為P（tA1＞C′）＞P（tB1＞C′）＝P（tB2＞C′）＞P（tA2＞C′），以文獻［6］模型的評價指標中，未完工率之和（PA1＋PA2）≈（PB1＋PB2），即方案A 和B 是約等效的，與本文比較，文獻［6］模型對于方案A和方案B的優(yōu)劣分辨率不高。

定義2 在隨機型裝配線中，保證所有節(jié)拍在概率α下完工的最小節(jié)拍為α完工率節(jié)拍，記為C（α）。

工位Sr的作業(yè)時間TSr～N（μr，σ2r），若保證其完工率為α，即工位r在μr＋CR（α）σr時間間隔內的完工率為α，P（TSr＜μr＋CR（α）σr）＝α，則C（α）＝max（μr＋CR（α）σr）。α越大CR（α）值越大，例如α＝50%時CR（α）＝0，即不考慮作業(yè)時間隨機性的影響σ＝0；α＝60%時CR（α）＝0．25；α＝75%時CR（α）＝0．67。

作業(yè)元素集 K＝｛k＝1，2，…，n｝，n為作業(yè)數量，tk表示作業(yè)k的作業(yè)時間；作業(yè)優(yōu)先約束矩陣An×n＝（aij），aij＝1表示作業(yè)j必須在作業(yè)i后完成，aij＝0表示作業(yè)j和作業(yè)i無直接優(yōu)先關系；決策變量為xkr（k＝1，2，…，n；r＝1，2，…，m），xkr＝1表示作業(yè)k被分配到工位Sr?；谏鲜鱿嚓P變量，第2類裝配線平衡問題（ALBP－2）數學模型如下：

其中：目標函數表達式 min（C（α）．SI）表示優(yōu)先最小化C（α），在C（α）相等時最小化SI；約束條件式（15）表示每個作業(yè)只能分配到一個工位，且每個作業(yè)必須被分配；式（16）表示約束優(yōu)先關系被滿足；式（17）表示每個工位必須被使用；式（18）表示每個工位作業(yè)時間滿足節(jié)拍約束。下面用一種雙染色體遺傳算法（Double－Chromosome Genetic Algorithm，DCGA）對上述隨機型裝配線平衡模型進行求解。

3 遺傳算法設計

DCGA的個體擁有兩條染色體Ⅰ和Ⅱ，這兩條染色體均為搜索空間的一個解，其中的較優(yōu)解競爭成為個體的顯性染色體，個體的適應度值由顯性染色體決定。同一個體的Ⅰ、Ⅱ染色體具有同等的參與進化機會，其中顯性染色體保留優(yōu)質基因段，加快算法收斂；隱性染色體保持種群多樣性，避免算法陷入局部最優(yōu)，提高了全局尋優(yōu)的能力。在相等染色體規(guī)模下，DCGA種群規(guī)模是標準遺傳算法的一半，能有效縮短算法時間，提高進化速度。

3．1 編碼和解碼

采用作業(yè)序列編碼方式，按作業(yè)分配至工位的順序進行編碼，每個作業(yè)元素對應于染色體上的一個基因位。如圖3所示，第一次分配作業(yè)1，第二次分配作業(yè)2，…，第9次分配作業(yè)4，最后一次分配作業(yè)3。

ALBP－2問題的生產節(jié)拍C是未知的，在解碼時不能按照C來分配作業(yè)，對于這個問題的解決思路是預估一個C＊，在C＊的基礎上按照一定的增量進行探索求解計算。在實際問題中，C＊的增量是不連續(xù)的，而是以作業(yè)元素的時間作為增量。

下面給出一種針對ALBP－2問題的解碼方法：

步驟1 計算理論最小節(jié)拍Ct＝（Σtk）/m，Σtk為所有作業(yè)元素作業(yè)時間之和，m為給定的工作數量，令C＊＝Ct。

步驟2 以C＊為節(jié)拍，按照染色體編碼作業(yè)序列把n個作業(yè)分配到m個工位中，每個工位的作業(yè)時間分別是TS1，TS2，…，TSr，…，TSm。如果每個工位作業(yè)時間均滿足TSr≤C＊，則C＊就是在這種排序下的最小節(jié)拍，搜索停止；否則轉步驟3。

步驟3 計算工位作業(yè)時間TSr的潛在增量d1，d2，…，dr，…，dm，其中dr表示第r＋1個工位的第一個作業(yè)元素作業(yè)時間。

步驟4 令C＝max｛TSr｝，C＊＝min｛TSr＋dr｝，如果C≤C＊，則C就是該染色體編碼排序下的最小節(jié)拍，搜索停止；否則轉步驟2。

3．2 適應度評價

適應度評價函數是區(qū)分種群個體優(yōu)劣的標準，是進化中優(yōu)勝劣汰的唯一依據。ALBP－2的優(yōu)化目標是生產節(jié)拍C最小化，由式（14）可得：

第一評價指標為生產節(jié)拍C（α）（精確到小數點后1位），如式（19）所示；在染色體的第一評價指標水平相等時，進行第二評價指標的計算，如式（20）所示。隨著作業(yè)集K規(guī)模的增加，每個工位Sr的作業(yè)時間TSr～N（μr，σ2r）的隨機分布參數μr和σr也將相應增大，由定義2，C（α）＝max（μr＋CR（α）σr），則C（α）有增大的趨勢。即在保證求解方法有效性和完工率的條件下，隨著作業(yè)集規(guī)模的增加，算法求解結果將得到更大的生產節(jié)拍。

3．3 交叉算子

個體具有兩條染色體Ⅰ、Ⅱ，隨機選擇其中的一條進行交叉操作，如圖1所示。交叉算子采用兩點交叉法，如圖4所示，隨機產生兩個交叉點，在父代2中搜索父代1基因段的排列方式，進行交叉替換獲得子代1，同樣的交叉過程獲得子代2，如圖5所示。這種交叉操作能夠保證子代個體為可行解，減少計算量，提高算法效率。

3．4 變異算子

個體的兩條染色體進行獨立的變異，隨機產生變異點，對變異點后面的基因段進行重新排列。即根據優(yōu)先關系矩陣，對變異后的作業(yè)進行重新分配。獲得新的子代，如圖6所示。

4 算例

Kilbridge問題是一個10工位裝配線平衡測試問題［11］，工位數m＝10，作業(yè)數量n＝45。Kilbridge問題作業(yè)優(yōu)先關系如圖7所示，作業(yè)時間如表1所示。

表1 Kilbridge問題作業(yè)時間

用DCGA對式（14）～式（18）所示的隨機型裝配線平衡模型進行求解，方案A取完工率α＝50%，CR（α）＝0（忽略隨機性影響）；方案B取α＝60%，CR（α）＝0．25（考慮完工率不低于60%）；方案C取α＝75%時，CR（α）＝0．67（考慮完工率不低于75%），求解結果如表2所示。

A B C工位作業(yè)元素 μ_σ 作業(yè)元素 μ_σ 作業(yè)元素 μ σ_1 1，2，7，11，12，37 56 17．8 1，2，11，12，13，37，39 54 18．8 2，11，12，13，15，18，37 54 17．7 2 6，13，15，16，18 56 14．1 3，5，6，15 55 16 1，8，24，39 56 15．6 3 8，14，17，19 54 15．3 7，8，18，23 56 15．3 7，14，17，27，32 56 15．6 4 4，20，23，27，29，43 56 17．8 14，16，19，20，29 56 15．0 3，4，23，31 54 18．2 5 21 55 16．3 21 55 16．3 5，25，26，43 55 17．1 6 24，33，34，36 56 16．7 9，17，22，30，32 55 17．1 6，9，16 56 14．3 7 3，22，31，32，10 55 16．0 10，24，31 56 14．3 19，20，29，30，33，35，36，40 55 16．8 8 5，28，35，38 55 16．8 25，27，33，34，43 55 17．6 10，34，41，42 56 15．0 9 9，25，26，40 56 17．8 26，35，40，41，42，45 55 14．9 21 55 16．3_10 30，41，42，44，45，39 53 15．2 4，28，36，38，44 55 18．5 22，28，38，44，45 55 17．2

在保證完工率α＝60%的條件下比較方案A和B，在保證完工率α＝75%的條件下比較方案A和C，即按照公式C（α）＝max（μr＋CR（α）σr）計算各方案的α完工率節(jié)拍及均衡指數，如表3所示。

表3 Kilbridge問題作業(yè)時間

續(xù)表3

由表3可以看出，考慮了CR（α）的模型求解結果，在相應的完工率α的條件下，生產節(jié)拍和均衡指數均優(yōu)于忽略隨機性影響的模型求解結果，式（14）～式（18）所示的隨機型裝配線平衡模型是有效的。

5 結束語

裝配線平衡是一種基于時間的調度，受設備運轉、原材料供應、工人操作速度等不穩(wěn)定因素的影響，作業(yè)時間是個隨機變量。本文針對隨機型裝配線平衡問題，分析了作業(yè)時間的隨機波動對元啟發(fā)式方法和啟發(fā)式方法的失效影響，以各個工位在給定完工率下的最小投產間隔作為生產節(jié)拍，并以此為優(yōu)化目標，建立了隨機作業(yè)時間條件下的第2類裝配線平衡優(yōu)化模型，為隨機型裝配線平衡問題的解決提供了一種新的思路，為下一步展開隨機型混流裝配線平衡及排序問題研究奠定了良好的基礎。

［1］ CAO Zhenxin，ZHU Yunlong，LI Fuming．Research on dynamic planning ＆simulation optimization of mixed model general automobile assembly lines［J］．Computer Integrated Manufacturing Systems，2006，12（4）：526－532（in Chinese）．［曹振新，朱云龍，李富明．混流轎車總裝配線的動態(tài)規(guī)劃與仿真優(yōu)化研究［J］．計算機集成制造系統(tǒng)，2006，12（4）：526－532．］

［2］ PENG Shangxian，GUO Dong，ZHANG Ping．The study of the flexible assembly system design［J］．China Mechanical Engineering，1996，7（3）：37－40（in Chinese）．［彭商賢，郭 東，張

平．柔性裝配系統(tǒng)設計的研究［J］．中國機械工程，1996，7（3）：37－40．］

［3］ ZHANG Bixi，LIU Yongqing．Dynamic scheduling of stochas

tic operation schemes［J］．Journal of South China University of Technology：Natural Science Edition，2000，28（1）：122－129（in Chinese）．［張畢西，劉永清．隨機型作業(yè)計劃動態(tài)排序方法研究［J］．華 南 理 工 大 學 學 報：自 然 科 學 版，2000，28（1）：122－129．］

［4］ JIA Dalong，WANG Honglei．Simulation modeling for stochastic assembly line balancing［J］．Journal of Industrial Engineering and Engineering Management，1994，8（4）：232－237（in Chinese）．［賈大龍，王紅蕾．隨機裝配線平衡的仿真模型［J］．管理工程學報，1994，8（4）：232－237．］

［5］ ZHAO X，LIU J，OHNO K，et al．Modeling and analysis of a mixed－model assembly line with stochastic operation times［J］．Naval Research Logistics，2007，54（6）：681－691．

［6］ DENG Fuping．Ant colony optimization for solving the assembly line balancing problem［D］．Wuhan：Huazhong University of Science and Technology，2011（in Chinese）．［鄧福平．基于蟻群算法的裝配線平衡問題研究［D］．武漢：華中科技大學，2011．］

［7］ SARIN S C，EREL E，DAR－EL E M．A methodology for solving single－model，stochastic assembly line balancing problem［J］．The International Journal of Management Science，1999，27（5）：525－535．

［8］ GOKCEN H，BAYKOC O F．A new line remedial policy for the paced lines with stochastic task times［J］．The International Journal of Production Economics，1999，58（2）：191－197．

［9］ SIEWMUN H．Continuous processes can be lean（lean manufacturing and six sigma for continuous process manufacturing）［J］．Manufacturing Engineering，2007，138（6）：103－109．

［10］ KOTTAS J F，LAU H S．A stochastic line balancing procedure［J］．International Journal of Production Research，1981，19（2）：177－193．

［11］ KILBRIDGE M D，WEST L．A heuristic method of assembly line balancing［J］．Journal of Industrial Engineering，1961，12（4）：292－298．