雙邊多工位裝配線平衡問題

張宏林，殷復(fù)鵬，2，吳愛華

0 引言

裝配線是大批量生產(chǎn)的產(chǎn)品經(jīng)常采用的一種生產(chǎn)方式，這種生產(chǎn)方式可以最大限度地縮短生產(chǎn)時間和運輸路線，提高勞動生產(chǎn)率。裝配線平衡是發(fā)揮裝配線優(yōu)勢的關(guān)鍵，與產(chǎn)量、質(zhì)量和成本都有很大的關(guān)系。在我國，由于裝配線不平衡引起的效率低下、成本浪費現(xiàn)象十分嚴重。因此，裝配線平衡問題一直是企業(yè)和學(xué)術(shù)界廣泛關(guān)注的問題。裝配線可以分為單邊裝配線和雙邊裝配線，雙邊裝配線普遍應(yīng)用于汽車、裝載機等大型產(chǎn)品的生產(chǎn)裝配過程中，與單邊裝配線相比，具有能縮短裝配線長度，減少產(chǎn)品的下線時間，降低工具、夾具及物料處理的成本等優(yōu)點。

從1955年Salveson首次提出裝配線平衡問題至今，人們對其進行了大量的研究，針對不同的裝配線類型建立了多種模型，并提出最優(yōu)化方法、啟發(fā)式方法等多種算法。Nils等詳細地對裝配線平衡問題進行了分類和總結(jié)，并對部分文獻進行了歸類和比較［1］；Christian等對一般裝配線平衡問題及其算法進行了較為詳細的總結(jié)，并對裝配線平衡問題在未來的研究提出了建議［2］。目前，大部分研究都集中于單邊裝配線平衡問題，對于雙邊裝配線的平衡問題研究較少。Bartholdi首次提出雙邊裝配線的概念，并提出一種啟發(fā)式算法，此后，Kim，Lee和Lapierre等分別對此問題進行了研究，并各自提出不同的算法［3］。近年來，Uˇgur等針對雙邊裝配線平衡問題，提出了一種禁忌搜索算法［4］；Adil等建立了一種基于啟發(fā)式算法的蟻群模型來解決雙邊裝配線平衡問題［5］；吳爾飛等對雙邊裝配線的平衡問題進行了深入研究，先后提出了基于位置的任務(wù)分配策略的啟發(fā)式算法［3］，并針對雙邊裝配線第二類問題建立了數(shù)學(xué)模型，提出一種基于規(guī)則的啟發(fā)式算法［6］。

以上雙邊裝配線平衡問題的研究只是針對裝配線一個位置左右各有一個工位（伴隨工位）的情況，而實際上裝配線上的每一個位置往往有多個工位，如在重型汽車裝配線上，一個車位（相當于位置）一般有4～6個工位。對于多個工作的并行作業(yè)的裝配線平衡問題，一些學(xué)者也進行了相應(yīng)的研究，如Christian等［7］，但這些研究都沒有考慮裝配線左右方位約束的限制。

本文對雙邊多工位裝配線平衡問題進行分析研究，建立該類問題的數(shù)學(xué)模型，并提出一種有效的啟發(fā)式算法，為此類裝配線平衡提供參考。

1 問題及其描述

雙邊多工位裝配線是在單邊裝配線的基礎(chǔ)上，將原來的工位分為左右多個工位，工人在各自工位上獨立作業(yè)。本文采用文獻［6］中的概念，用位置來表示原單邊裝配線的工位，稱位置左右的工作區(qū)為工位，位置內(nèi)各工位并行作業(yè)。如圖1所示，位置1的左邊和右邊各有2個工位，共4個工位；位置2的左邊有3個工位，右邊有2個工位，共5個工位。

雙邊多工位裝配線一旦投資建成后，很難再進行大的改動，即裝配線的長度和裝配線所擁有的工作的數(shù)量難以變動。因此，與單邊裝配線相比，雙邊裝配線平衡需要考慮的約束和要求較多，在平衡時，除了需要滿足作業(yè)的先后約束關(guān)系外，還應(yīng)該考慮以下影響因素：

（1）作業(yè)方位的約束 由于受產(chǎn)品結(jié)構(gòu)、裝配線設(shè)施等的限制，某些裝配作業(yè)具有方位約束，即作業(yè)只能在裝配線的左側(cè)或右側(cè)進行。例如由于油箱、空氣過濾器、工具箱等部件位于汽車的一邊，在汽車裝配線上，這些部件的裝配操作應(yīng)安排在與其對應(yīng)的裝配線一側(cè)?？蓪⒎轿患s束分為左方位約束、右方位約束和無方位約束三種情況。

（2）同位置不同工位的優(yōu)先關(guān)系約束 一般同位置內(nèi)各工位并行作業(yè)，但在分配作業(yè)時有可能將具有緊前緊后關(guān)系的兩個作業(yè)要素分配給兩個工位，這樣就有可能使兩個作業(yè)中的緊后作業(yè)產(chǎn)生等待時間，影響平衡。因此，雙邊裝配線平衡時，不僅要考慮其自身作業(yè)時間對平衡的影響，還要考慮其前序作業(yè)是否分配給與該工位同在一個位置內(nèi)的其他工位的影響。

本文研究的雙邊多工位裝配線平衡問題仍然屬于第一類平衡問題，具體可描述為：已知裝配線位置數(shù)及各位置左右兩邊工位數(shù)，給定生產(chǎn)節(jié)拍，一組作業(yè)集在滿足作業(yè)順序優(yōu)先關(guān)系、方位約束的條件下，將作業(yè)盡可能均衡地分配到裝配線兩邊的各個工位上，使裝配線的長度最短（位置數(shù)量最少）、啟用的工位數(shù)量最少。

2 雙邊多工位數(shù)學(xué)模型

2.1 假設(shè)

由于現(xiàn)實中裝配線的復(fù)雜性，本文對裝配線平衡的研究仍然建立在一定的假設(shè)基礎(chǔ)之上。

假設(shè)1 裝配線上工人的技術(shù)水平不存在差異，可以完成任一項作業(yè)。

假設(shè)2 裝配線上同時只生產(chǎn)一種產(chǎn)品。

假設(shè)3 一個作業(yè)元素的作業(yè)時間不依賴于位置和工位。

假設(shè)4 裝配線的節(jié)拍大于作業(yè)元素時間中的最大者。

假設(shè)5 作業(yè)元素可以分配到任何工位，即作業(yè)元素沒有位置約束。

假設(shè)6 一個作業(yè)元素只能分配給一個位置和一個工位。

2.2 參數(shù)設(shè)定

在建立模型之前，首先對模型中出現(xiàn)的參數(shù)及其符號進行說明：

C表示裝配線的節(jié)拍；

Tasks 表 示 作 業(yè) 元 素 集 合，Tasks ＝ ｛1，2，…，n｝；

n表示作業(yè)元素的個數(shù)；

i和j為作業(yè)元素的序號，代表作業(yè)元素i和j，i，j＝1，2，…，n；

ti表示第i個作業(yè)元素的時間，i＝1，2，…，n；

pred表示作業(yè)元素的優(yōu)先關(guān)系集合，pred＝｛（i，j）｜作業(yè)元素i是作業(yè)元素j的緊前作業(yè)｝；

n＋1表示在作業(yè)元素優(yōu)先關(guān)系圖中，作業(yè)元素的唯一歸宿節(jié)點序號；

K表示裝配線擁有的位置數(shù)；

k表示位置的序號，代表第k個位置，k＝1，2，…，K；

mk表示裝配線上第k個位置擁有的工位數(shù)，mk＝＋

l表示位置左邊工位的序號，代表某一位置的第l個工位；

r表示位置左邊工位的序號，代表某一位置的第r個工位；

ail表示左方位約束，ail＝1表示作業(yè)元素i需要安排在裝配線的左側(cè)，否則ail＝0；

air表示右方位約束，air＝1表示作業(yè)元素i需要安排在裝配線的右側(cè)，否則air＝0；

aie表示無方位約束，aie＝1表示作業(yè)元素i沒有方位約束，即可以分配給裝配線任何一側(cè)工位，否則aie＝0；

Tk表示位置k上分配的作業(yè)集合。

2.3 決策變量

裝配線平衡是一個決策過程，決策變量表示各作業(yè)元素的具體分配情況和工作地占用情況，符號說明如下：

xik為0－1變量，當作業(yè)元素i被分配至第k個位置時，xik＝1，否則xik＝0；

Ak為位置k的指示變量，即

2.4 數(shù)學(xué)模型

建立如下整數(shù)規(guī)劃模型：

目標函數(shù)（1）表示啟用的位置數(shù)最少；目標函數(shù)（2）表示啟用的工位數(shù)最少。

約束條件（3）表示作業(yè)元素只能被分配到一個位置；約束條件（4）表示作業(yè)元素只能被分配到一個工位；約束條件（5）表示每一個作業(yè)元素只有一個方位約束；約束條件（6）表示每個位置內(nèi)的作業(yè)時間不能超過該位置的可用時間，位置可用時間的多少與該位置所包含的工位數(shù)量有關(guān)，其值是位置內(nèi)工位數(shù)與節(jié)拍的乘積；約束條件（7）表示每個位置內(nèi)具有左方位約束的作業(yè)時間不能超過該位置左邊工位的可用時間，位置左邊工位的可用時間指該位置內(nèi)處于裝配線左邊的工位數(shù)與節(jié)拍的乘積；約束條件（8）表示每個位置內(nèi)具有右方位約束的作業(yè)時間不能超過該位置右邊工位的可用時間，位置右邊工位的可用時間指該位置內(nèi)處于裝配線右邊的工位數(shù)與節(jié)拍的乘積；約束條件（9）表示位置內(nèi)作業(yè)元素在滿足順序優(yōu)先關(guān)系的前提下，各工位的作業(yè)時間不超過節(jié)拍時間；約束條件（10）保證不違反作業(yè)元素之間的優(yōu)先關(guān)系；約束條件（11）表示具有左方位約束的作業(yè)不能分配給右邊工位，具有右方位約束的作業(yè)不能分配給左邊工位；約束條件（12）表示如果某個位置中有作業(yè)元素分派進去，則無論作業(yè)元素有多少個，該位置的指示值都為1；約束條件（13）表示如果位置k的左工位中有作業(yè)元素分派進去，則無論作業(yè)元素有多少個，該工位的指示值都為1；約束條件（14）表示如果位置k的右工位中有作業(yè)元素分派進去，則無論作業(yè)元素有多少個，該工位的指示值都為1。

3 啟發(fā)式算法

3.1 算法的整體思路

雙邊多工位裝配線平衡問題是典型的NP問題，很難求得最優(yōu)解，本文提出一種有效的啟發(fā)式算法，能夠得到較優(yōu)可行解。算法整體思路分為兩個階段：

階段1 開啟位置k，分配作業(yè)元素。從未分配的作業(yè)元素中找出可以分配給位置k的作業(yè)元素，構(gòu)成可行作業(yè)元素集合W。

階段2 分配位置k內(nèi)的各工位。按照不違背作業(yè)優(yōu)先關(guān)系、方位約束和工位時間不超過節(jié)拍的原則，把W 中的部分或全部作業(yè)元素分配到位置k內(nèi)的各工位上。當位置k所有的工位都啟動并無法再分配作業(yè)，或W 中的作業(yè)元素都已分配給各工位時，開啟下一個位置（k＝k＋1），返回階段Ⅰ。

3.2 階段1的啟發(fā)式算法

符號說明：W 為可分配給當前位置的作業(yè)元素集；E和S為過程中用到的作業(yè)元素集合；Tefi為作業(yè)元素i在當前位置上可能的最早完成時間；p為已分配給工位的作業(yè)元素個數(shù)。

步驟1 讀入相關(guān)參數(shù)，包括裝配線節(jié)拍C；待平衡的作業(yè)元素集Tasks及相關(guān)參數(shù)n，ti，pred，ail，air和aie；裝配線參數(shù)K和等。

步驟2 開啟裝配線上的第1個位置（k＝1，Ak＝1）；令p＝0。

步驟3 令W ＝ ?，E＝ ?，Tefi＝0（i＝1，2，…，n）。

步驟4 在Tasks中未分配的作業(yè)元素中，找出沒有緊前作業(yè)或緊前作業(yè)已經(jīng)分配給W 的元素，存于集合E。

步驟5 在E中任選一個ti最小的作業(yè)元素j。該元素如果有已經(jīng)分配給W 的緊前作業(yè)i，則計算Tefj＝ max（Tefi）＋tj；否則直接進入步驟6。

步驟6 比較Tefj與C。如果Tefj≤C，則將作業(yè)元素j保存在集合S中，并從集合E中將其刪除；如果Tefj＞C，則直接從集合E中刪除元素j。此時，如果E不是空集，則返回步驟5；否則，直接進入步驟7。

步驟7 判斷集合S是否為空集。如果S不是空集，則將S中的元素存入集合W，并令S＝?，返回步驟4，否則直接進入階段2。

3.3 階段2的啟發(fā)式算法

符號說明：Tesi為作業(yè)元素i在當前位置上可能的最早開始時間；Tlsi為作業(yè)元素i在當前位置上可能的最晚開始時間；Tefi為作業(yè)元素i在當前位置上可能的最早完成時間；A和B為過程中用到的作業(yè)元素集合；STm為當前工位上已分配作業(yè)元素的時間和。

Tesi，Tlsi和Tefi計算說明：

（1）如果W 中的作業(yè)元素j沒有緊前作業(yè)，則Tesj＝0，Tefj＝tj。

（2）如果W 中的作業(yè)元素j有緊前作業(yè)，則Tesj＝max（Tefi）。

（3）如果W 中的作業(yè)元素i沒有緊后作業(yè)，則Tlsi＝C－ti，Tlfi＝C。

（4）如果W 中的作業(yè)元素i有緊后作業(yè)，則Tlsi＝max（Tlsj）－ti。

本階段啟發(fā)式算法步驟如下。

首先從階段1獲取W。

步驟1 初始化ml＝0，mr＝0。

步驟2 令A(yù)＝?，B＝?。在W 中找出沒有緊前作業(yè)或緊前作業(yè)已經(jīng)分配完的作業(yè)元素，存于集合A。如果A為空集，則開啟下一個位置，即k＝k＋1，Ak＋1＝1，轉(zhuǎn)階段1中的步驟3；否則，從A中選取Tlsi最小的作業(yè)元素，存于集合B。

如果B中有具有方位約束的作業(yè)元素，則按以下規(guī)則從B中選取一個作業(yè)元素。若所選作業(yè)具有左邊約束，則直接進入步驟3，否則轉(zhuǎn)步驟4。

如果B中沒有具有方位約束的作業(yè)元素，則按以下規(guī)則從B中選取一個作業(yè)元素，并直接進入步驟5。

規(guī)則1 選取Tesi最小的作業(yè)元素。

規(guī)則2 如果有多個Tesi最小的元素，則從中選取ti最大的元素。

步驟3 如果當前位置k有已開啟的左邊工位，則從開啟的工位中選取STm≤Tlsi的工位：

（1）如果有STm≤Tlsi的工位，則從中任選STm最大的一個工位作為當前工位，轉(zhuǎn)步驟6。

（2）如果沒有STm≤Tlsi的工位，則分兩種情況：①當前位置的左邊工位都已開啟時，從W 中刪除當前作業(yè)元素j，返回步驟2；②當前位置的左邊工位沒有都開啟或沒有開啟時，新開啟一個左邊工位作為當前工位，轉(zhuǎn)步驟7。

步驟4 如果當前位置k有已開啟的右邊工位，則從開啟的工位中選取STm≤Tlsi的工位：

（1）如果有STm≤Tlsi的工位，則從中任選STm最大的一個工位作為當前工位，轉(zhuǎn)步驟6。

（2）如果沒有STm≤Tlsi的工位，則分兩種情況：①當前位置的右邊工位都已開啟時，從W 中刪除當前作業(yè)元素j，返回步驟2；②當前位置的右邊工位沒有都開啟或沒有開啟時，新開啟一個右邊工位作為當前工位，轉(zhuǎn)步驟8。

步驟5 如果當前位置k還沒有開啟工位，則開啟左邊第一個工位或右邊第一個工位，作為當前工位；如果開啟的是左邊的工位，則轉(zhuǎn)步驟7；如果開啟的是右邊的工位，則轉(zhuǎn)步驟8。

如果該位置有已經(jīng)開啟的工位，則從中選擇STm≤Tlsi的工位：

（1）如果有STm≤Tlsi的工位，則從中任選STm最大的一個工位作為當前工位，轉(zhuǎn)步驟6。

（2）如果沒有STm≤Tlsi的工位，則分四種情況：①ml＜mkl且mr＝mkr，開啟左邊一個工位，作為當前工位，轉(zhuǎn)步驟7。②ml＝mkl且mr＜mkr，開啟右邊一個工位，作為當前工位，轉(zhuǎn)步驟8。③ml＜mkl且mr＜mkr，任意開啟左邊或右邊的一個工位，若開啟的是左邊工位，則直接進入步驟7；若開啟的是右邊工位，則轉(zhuǎn)步驟8。④ml＝mkl且mr＝mkr，從W中刪除作業(yè)元素j及其所有的后續(xù)作業(yè)，轉(zhuǎn)步驟9。

步驟6 將當前的作業(yè)元素分配給當前的工位，且p＝p＋1，STm＝max（STm，Tesj）＋tj，從W中刪除該作業(yè)元素，轉(zhuǎn)步驟9。

步驟7 將當前的作業(yè)元素分配給當前的工位，且ml＝ml＋1，p＝p＋1，STm＝STm＋tj；從W 中刪除該作業(yè)元素，轉(zhuǎn)步驟9。

步驟8 將當前的作業(yè)元素分配給當前的工位，mr＝mr＋1，p＝p＋1，STm＝STm＋tj；從W中刪除該作業(yè)元素，進入步驟9。

步驟9 若W不為空集，則返回步驟2；若W為空集，則分兩種情況：①如果p＜n，則新開啟一個位置，即k＝k＋1，Ak＋1＝1，轉(zhuǎn)階段1中的步驟3；②如果p＝n，則線平衡結(jié)束。

4 算例

本文以某重型汽車裝配線翻車前的裝配線平衡為例，對其進行雙邊裝配線平衡。已知生產(chǎn)某種型號汽車的作業(yè)優(yōu)先關(guān)系如圖2所示，圖中節(jié)點上方括號內(nèi)的符號表示方位約束（L為左方位約束，R為右方位約束，E為無方位約束），數(shù)字表示作業(yè)時間。已知裝配線的情況如表1所示。裝配線節(jié)拍定為360s。該企業(yè)裝配線（翻轉(zhuǎn)前）左右工位的數(shù)量如表1所示。

表1 某企業(yè)裝配線現(xiàn)狀

應(yīng)用本文提出的啟發(fā)式算法進行平衡的一種平衡結(jié)果如表2所示。

表2中“作業(yè)元素”一列中有數(shù)字表示該工位被啟用，且數(shù)字表示分配到該工位的作業(yè)元素編號，“無”表示該工位沒有被啟用。結(jié)果顯示，共啟用6個位置和17個工位。從平衡結(jié)果可以看出，大部分工位的作業(yè)時間基本接近節(jié)拍，且空閑時間較少，只有個別的工位空閑時間較大，這時可以對其進行調(diào)整。調(diào)整原則根據(jù)實際情況較為靈活，調(diào)整時從空閑時間較大的工位入手，在不違背作業(yè)元素優(yōu)先關(guān)系的前提下，可以對作業(yè)元素進行重新組合，以減少工位空閑時間或減少工位數(shù)量，優(yōu)化平衡結(jié)果。如本例中，車位4中工位4－4的空閑時間為246s，工位空閑率達到了68.3%，因此需要進行優(yōu)化調(diào)整，可以取消該工位，將其所包含的作業(yè)55，37，46調(diào)整到車位5，此時車位五中的作業(yè)包括55，37，46，40，49，44，41，47，42，39和48，其中具有右方位約束的作業(yè)總時間為375s，所有作業(yè)的總時間為637s，都沒有超出車位5的可用時間。因此，可以對這些作業(yè)按照階段2的啟發(fā)式算法重新進行組合。調(diào)整后車位4、車位5和車位6的作業(yè)分配情況如表3所示。調(diào)整后，減少了一個工位（工位4－4）。

表2 一種平衡結(jié)果

表3 調(diào)整后部分位置作業(yè)分配情況

5 結(jié)束語

裝配線平衡問題提出以來，人們對該問題的研究一直沒有中斷過，并產(chǎn)生了大量的研究成果。但大部分研究都是建立在較為理想的假設(shè)基礎(chǔ)上，與實際應(yīng)用之間存在很大差距。作為重型汽車、裝載機等大型產(chǎn)品常用的雙邊裝配線的平衡問題，只有少數(shù)學(xué)者進行了相應(yīng)的研究，但仍然只是較為簡單的兩邊各有一個工位的情況。本文針對實際裝配線一個位置兩邊通常各有多個工位的情況，對雙邊多工位裝配線平衡問題進行了研究，并建立了該類平衡問題的數(shù)學(xué)模型，提出一種有效的啟發(fā)式算法。應(yīng)用該方法雖然不能得到最優(yōu)解，但可以較容易地得到一種較優(yōu)的可行解，仍然能夠為解決該類平衡問題提供參考，并能夠在企業(yè)中應(yīng)用。

［1］ BOYSEN N，F(xiàn)LIEDNER M，SCHOLL A.A classification of assembly line balancing problems［J］.European Journal of Operational Research，2007，183（2）：674－693.

［2］ BECKER C，SCHOLL A.A survey on problems and methods in generalized assembly line balancing［J］.European Journal of Operational Research，2006，168（3）：694－715.

［3］ WU Erfei，JIN Ye，SHEN Jian，et al.A heuristic algorithm for two－sided assembly line balancing［J］.Journal of Shanghai Jiaotong University，2007，41（11）：1484－1487（in Chinese）.［吳爾飛，金 燁，沈 健，等.雙邊裝配線平衡的啟發(fā)式算法［J］.上海交通大學(xué)學(xué)報，2007，41（11）：1484－1487.］

［4］ ?ZCAN U，TOKLU B.A tabu search algorithm for two－sided assembly line balancing［J］.International Journal of Advanced Manufacturing Technology，2009，43（7／8）：822－829.

［5］ BAYKASOGLU A.Two－sided assembly line balancing using an ant－colony－based heuristic［J］.International Journal of Advanced Manufacturing Technology，2008，36（5／6）：582－588.

［6］ WU Erfei，JIN Ye，WANG Zheng.Research on balancing problem of typeⅡ of two－sided assembly line［J］.Computer Integrated Manufacturing Systems，2005，11（11）：1604－1608（in Chinese）.［吳爾飛，金 燁，汪 崢.雙邊裝配線第二類平衡問題研究［J］.計算機集成制造系統(tǒng)，2005，11（11）：1604－1608.］

［7］ BECKER C，SCHOLL A.Balancing assembly lines with variable parallel workplaces：Problem definition and effective solution procedure［J］.European Journal of Operational Research，2009，199（2）：1－16.