基于蜂群算法的雙邊裝配線平衡問題研究

熊 晶 段曉坤

(常州信息職業(yè)技術學院 智能裝備學院，江蘇 常州213164）

0 引言

在汽車、裝載機等產品的裝配過程中，由于裝配區(qū)域較大，能夠在雙側同時進行裝配工作，因此雙邊裝配線在大型產品的裝配過程中得到了廣泛的應用。相比于單邊裝配線，雙邊裝配線能夠縮短裝配線長度、減少物料搬運、工人移動和減少工具成本等優(yōu)點[1]。

雙邊裝配線操作任務的分配不僅要滿足單邊裝配線的基本分配約束要求，如任務時間約束、優(yōu)先順序約束、時間結束約束和節(jié)拍時間約束等；同時，要滿足特有的操作方位約束和不同操作方位對先序任務的裝配約束等要求[2]，因此，雙邊裝配線平衡問題更復雜，更難得到精確的最優(yōu)分配方案。鑒于雙邊裝配線平衡問題的實際應用價值，越來越多的研究人員對該問題進行了深入研究。

文獻[3-5]針對雙邊裝配線平衡問題的不同優(yōu)化目標，如最大化任務相關性和最小化工作載荷、最小化工位數(shù)量和多目標優(yōu)化等，提供和改進了啟發(fā)式方法、遺傳算法、粒子群算法和蟻群算法等多種群體智能算法。但對于雙邊裝配線在應用中存在的位置約束、區(qū)域約束和同步約束等實際分配約束問題研究較少。

本文為解決以上實際約束問題，針對雙邊裝配線任務分配的特點，設計了一種解碼方法解決多重約束的賦值問題，并結合延遲爬山算法對蜂群算法進行改進，加快了求解過程的收斂速度和求解精度。

1 雙邊裝配線平衡問題

1.1 雙邊裝配線

雙邊裝配線在產品裝配過程中，由于左右兩側同時進行裝配工作，裝配線劃分為左右兩個裝配區(qū)域。左右兩個并行的工位稱為伴隨工位，如工位1和工位2，工位2n-1和工位2n，如圖1所示?？紤]到產品的功能要求，存在只能在產品左側或者右側進行裝配的零部件，此類操作任務具有操作方位約束，稱為左側任務（L型）和右側任務（R型）。在裝配線左右兩側均可進行操作的任務稱為雙側任務（E型）。

雙邊裝配線的所有操作任務分配時，須遵循以下基本原則：每個任務必須分配到唯一的工位上；同一工位上所有任務的結束時間不能超過裝配節(jié)拍時間；所有任務的分配須遵循優(yōu)先順序約束，即該任務的所有先序任務完成后才能進行該任務的操作。由于優(yōu)先順序約束的原因，每個工位上都可能產生空閑時間，如圖1的陰影部分。

圖1 雙邊裝配線

雙邊裝配線平衡問題可以通過先序關系圖表示，如圖2所示。圖中圓圈內的數(shù)字表示任務號，圓圈上方括號內的數(shù)字表示該任務的操作時長，字母表示該任務的操作方位約束（該任務需要在伴隨工位的哪一側進行）。圓圈之間的箭頭表示任務的相互順序約束。例如，任務7需要在任務4和5完成后才能，（3，E）表示任務7其操作時長為3，可以分配到左側或右側工位進行操作。同理L表示任務需要分配到左側工位，R表示任務需要分配到右側工位。

圖2 雙邊裝配線先序關系圖

1.2 第一類雙邊裝配線平衡問題的數(shù)學模型

本文研究第Ⅰ類裝配裝配線平衡問題：已知裝配線的生產節(jié)拍，在滿足任務分配約束的前提下，將所有任務分配到裝配線的各個工位中，并最小化裝配線長度。其數(shù)學模型如下：

設I為任務集，I={1，2，…，I，…，n}；J為伴隨工位集，J={1，2，…，j，…，m}；k為伴隨工位方位，k=1表示左側工位，k=2表示右側工位；SL、SR、SE分別為左側、右側和雙側任務；P0表示無先序任務的任務集合；P（i）為任務i的緊鄰先序任務集合；Pa（i）為任務i的所有先序任務集合；S（i）為任務i的緊鄰后序任務集合；Sa（i）為任務i的所有后序任務集合；ti為任務i的操作時長；fti為任務i的結束時間；Nm為開啟的伴隨工位總數(shù)；Ns為開啟的工位總數(shù)。

約束條件為：

（5）位置約束（任務i必須分配到指定工位）：

（6）區(qū)域約束：

積極區(qū)域約束（任務i，h必須分配到同一工位）：

消極區(qū)域約束（任務i，h不能分配到同一工位）：

（7）同步約束：（任務i，h必須分配到同一伴隨工位且操作開始時間必須相同）：

2 針對雙邊裝配線平衡的混合蜂群算法

蜂群算法中，每一個蜜源代表問題的每一個可行解。雇傭蜂搜索蜜源并將信息分享給跟隨蜂；跟隨蜂根據(jù)適應度在所有的蜜源中選擇一個并進行深度挖掘，以尋找更優(yōu)的可行解；偵察蜂利用隨機策略尋找新的蜜源，增加可行解的多樣性。通過有限次的搜索迭代，收斂得到最優(yōu)解，即最佳分配方案。

2.1 編碼

在混合蜂群算法中，將雙邊裝配線滿足所有分配約束的任務排序編碼為一個字符串的排列序列。根據(jù)隨機原則產生一個1~n（整數(shù)）的權重字符串，n為任務個數(shù)，數(shù)字k在該序列中的位置順序i表示任務i按順序第k次分配該任務。例如包含12個任務的雙邊裝配線，隨機產生的字符串為{2，5，3，7，6，1，12，9，8，11，4，10}，任務6的權重值為1，表示該任務是左右任務中最優(yōu)先分配的。所有任務的分配順序依次為6—1—3—11—2—5—4—9—8—12—10—7。

2.2 解碼

顯而易見，上述編碼序列無法表示任務與分配工位間的關系，而且這種分配序列可能不遵循優(yōu)先順序約束。因此，需要一種解碼方案將該序列編譯為符合分配約束的可行解。

解碼時，采用任務侯選集的方法，將滿足節(jié)拍約束和優(yōu)先順序約束的所有任務放到侯選集中。在任務集中，選擇一個任務，如果滿足節(jié)拍約束、區(qū)域約束和同步約束，則該任務根據(jù)位置約束分配到相應的工位；否則刪除該候選任務及其候選任務，再候選集中選擇其他候選任務，并檢查是否滿足分配約束。當任務集中的所有任務分配均已分配完畢，則開啟新的伴隨工位并更新候選任務集。

解碼過程中，E型任務優(yōu)先分配到最早開始操作的一側工位。如果開始時間相同，則將E型任務分配到伴隨工位的左側工位。

所有任務分配完畢后，檢查最后一個伴隨工位的任務是否均為L型和E型任務或者R型和E型任務。如果符合該條件，在滿足其他分配約束的基礎上，將該伴隨工位的所有任務分配到同一側工位中，減少工位的開啟數(shù)量。

2.3 雇傭蜂策略

延遲爬山算法是一種具有迭代過程和后期接受策略的高效局部搜索算法。該算法在初始解的基礎上，通過鄰域結構對其進行迭代改進，從而加快收斂速度。

在搜索可行解階段，每個雇傭蜂隨機選擇一個現(xiàn)存的可行解。為了尋找更好可行解或者潛在的更好的可行解并保持種群的多樣性，雇傭蜂采用四種鄰域結構（交換算子、插入算子、多交換算子和多插入算子）進行迭代更新。雇傭蜂在四個鄰近結構中隨機選擇一個產生新的可行解。如果新的可行解優(yōu)于現(xiàn)行解，則更新為現(xiàn)行解，否則仍保持原來的可行解。

2.4 跟隨蜂策略

當雇傭蜂得到新的可行解并更新種群后，跟隨蜂在此基礎上使用二進制錦標賽選擇策略在新種群中選擇現(xiàn)行解。為了挖掘更好的可行解，跟隨蜂采用多交換操作和多插入操作的變鄰域結構的延遲爬山算法進行迭代更新現(xiàn)行解。變鄰域結構是指當多插入操作鄰域結構對最佳可行解沒有改進時，使用多交換操作鄰域結構。

如果采用貪婪策略決定跟隨蜂得到的新可行解是否更新為現(xiàn)行解，可能會錯過新解繼續(xù)迭代而產生的更優(yōu)解。因此，將新可行解與現(xiàn)種群中的最差解進行對比，如果新可行解優(yōu)于最差解，則將最差解進行替換，否則舍棄新可行解。通過這種方式，跟隨蜂可以將種群導向搜索空間中最有得到最優(yōu)解的區(qū)域。

2.5 偵查蜂策略

如果一個可行解經過多次迭代后，仍沒有得到更新改進，則相應的雇傭蜂轉變?yōu)閭刹榉洳⒎艞壴摤F(xiàn)行解。如果偵查蜂利用隨機原則產生一個新的可行解，那么隨機解很可能是一個較差的解，它無法為種群迭代更新提供更好的信息，這種策略可能會降低搜索效率。因此，為了找到新的更好的解，避免陷入局部最優(yōu)，偵察蜂對現(xiàn)種群中的一個隨機解進行多次鄰域搜索，產生的解作為新的可行解。

3 工程實例應用

3.1 工程實例

隨著精益生產的推入，某公司對雙邊裝配線進行重新規(guī)劃設計，以期達到改善生產現(xiàn)狀，提高產能的目的。經實際調研，該公司的雙邊裝配線包括65項操作任務，各任務的先序關系圖，如圖3所示。由于產品的工藝復雜性，65項任務之間存在位置約束、區(qū)域約束和同步約束等分配約束條件。具體為：位置約束{任務，（伴隨工位，工位）}：{8，12，（3，2）}{9，10，（3，1）}、{16，17，（4，1）}{55，56，（4，2）}，積極區(qū)域約束{任務…任務}：{3，23，24}{31，32}{36，37}；消極區(qū)域約束：{10，30}{46，56}；同步約束{任務，任務}：{9，12}{51，52}。

圖3 65項任務先序關系圖

3.2 算法參數(shù)設計

為更好地優(yōu)化雙邊裝配線，得到更好的分配方案，本文的混合蜂群算法參數(shù)設置為：

蜂群數(shù)量Np=100，其中雇傭蜂、跟隨蜂和偵查蜂的數(shù)量分別為50、50和1；可行解最大更新迭代次數(shù)為limit=20；延遲爬山算法中可行解最多為20個；算法的終止條件為CPU計算時間Ts=n×n×15 ms，其中n=65。

3.3 計算結果

考慮新裝配線規(guī)劃設計過程中的工藝問題、生產實際條件，以及產品裝配過程中的位置約束、區(qū)域約束和同步約束等分配約束條件，該雙邊裝配線可以有5種設計方案。在裝配節(jié)拍CT=325時，能夠求解得到的最優(yōu)解為9[17]，即開啟9個伴隨工位，17個工位。當生產節(jié)拍CT=380、435、490、545時，能夠求解得到的最優(yōu)解分別為8[15]、7[13]、6[11]、6[11]。

結合生產區(qū)域面積、工人數(shù)量、生產效率以及訂單量的實際需求，最終的雙邊裝配線設計選用CT=490，開啟6個伴隨工位，11個工位的分配方案。此方案的具體任務分配甘特圖，如圖4所示。

圖4 65項任務分配方案甘特圖

圖中，X軸表示操作時間，Y軸表示伴隨工位和工位，“1L”表示伴隨工位1的左側工位。矩形框中的數(shù)字表示任務序號，矩形框的順序表示該工位中各任務的優(yōu)先順序。例如“6R”工位中的任務分配順序為：35—54—50—61—65。深色的矩形框表示具有位置約束、區(qū)域約束或同步約束的任務，如同步約束任務{51，52}。

矩形框右上側的數(shù)字表示該任務的操作結束時間，最后一個任務的結束時間為該工位的操作時間。例如任務65的結束時間為471，表示“6R”工位的操作時間為471。所有工位的最大操作時間為裝配節(jié)拍時間，例如該方案的最大節(jié)拍為CT=489。

4 結語

本文針對雙邊裝配線平衡問題中存在的實際應用約束，如位置約束、區(qū)域約束和同步約束等，提出了一種結合延遲爬山局部搜索策略的混合蜂群算法。該算法中針對雙邊裝配線任務分配的特點，設計了一種解碼方法解決多重約束的賦值問題。搜索求解過程，雇傭蜂使用四種鄰域結構探索新的可行解，跟隨蜂使用變鄰域結構的延遲爬山算法挖掘更優(yōu)的可行解。應用混合蜂群算法求解雙邊裝配線工程實例，得到了裝配線平衡的最優(yōu)解，驗證了該模型與算法對求解裝配線平衡問題有實際意義。