熊 晶 段曉坤

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

0 引言

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

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

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

本文為解決以上實(shí)際約束問(wèn)題，針對(duì)雙邊裝配線任務(wù)分配的特點(diǎn)，設(shè)計(jì)了一種解碼方法解決多重約束的賦值問(wèn)題，并結(jié)合延遲爬山算法對(duì)蜂群算法進(jìn)行改進(jìn)，加快了求解過(guò)程的收斂速度和求解精度。

1 雙邊裝配線平衡問(wèn)題

1.1 雙邊裝配線

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

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

圖1 雙邊裝配線

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

圖2 雙邊裝配線先序關(guān)系圖

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

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

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

約束條件為：

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

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

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

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

（7）同步約束：（任務(wù)i，h必須分配到同一伴隨工位且操作開(kāi)始時(shí)間必須相同）：

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

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

2.1 編碼

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

2.2 解碼

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

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

解碼過(guò)程中，E型任務(wù)優(yōu)先分配到最早開(kāi)始操作的一側(cè)工位。如果開(kāi)始時(shí)間相同，則將E型任務(wù)分配到伴隨工位的左側(cè)工位。

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

2.3 雇傭蜂策略

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

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

2.4 跟隨蜂策略

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

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

2.5 偵查蜂策略

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

3 工程實(shí)例應(yīng)用

3.1 工程實(shí)例

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

圖3 65項(xiàng)任務(wù)先序關(guān)系圖

3.2 算法參數(shù)設(shè)計(jì)

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

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

3.3 計(jì)算結(jié)果

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

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

圖4 65項(xiàng)任務(wù)分配方案甘特圖

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

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

4 結(jié)語(yǔ)

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