多人共站第一類混流裝配線平衡問題的優(yōu)化

楊武成，程文明

（西南交通大學(xué)機(jī)械工程學(xué)院，四川 成都 610031）

與傳統(tǒng)的裝配線相比，多人共站裝配線（multimanned assembly line，MAL）具有線長短、工具共享、操作人員交流頻繁、在制品低和柔性高等特點[1].MAL 已廣泛應(yīng)用于工業(yè)生產(chǎn)中，主要用于生產(chǎn)汽車、火車、裝載機(jī)和飛機(jī)[2]等大型產(chǎn)品.該類裝配線的投產(chǎn)成本很大，因此，在正式投產(chǎn)之前，如何設(shè)計一條高效、低成本的裝配線是節(jié)約成本的有效措施之一.當(dāng)前的研究集中于求解簡單的裝配線平衡問題（simple assembly line balancing problem，SALBP），相對而言，一般裝配線平衡問題（general assembly line balancing problem，GALBP）的研究較少[3].一般裝配線平衡問題會考慮更多實際的因素和約束，如：作業(yè)時間不確定、U 型/并行裝配線、混流裝配線、多人共站或其他約束等[4-6].

在實際生產(chǎn)中，尤其是在生產(chǎn)大型產(chǎn)品時，同一工位可能需要多個工人同時作業(yè)，這就引出了多人共站裝配線平衡問題（multi-manned assembly line balancing problem，MALBP）.相 比SALBP，針 對MALBP 的研究在近年來才引起關(guān)注[7].SALBP 已被證明為（non-deterministic polynomial-hard，NP-hard）問題，而MALBP 比SALBP 更復(fù)雜，求解難度更高.MALBP 目前研究主要集中在利用數(shù)學(xué)模型[8]、精確算法[9-10]和元啟發(fā)式算法[11-12]來求解.

近年來，為了滿足個性化、多樣化和定制化的客戶需求，混流裝配線逐漸取代了傳統(tǒng)的單一型號的產(chǎn)品裝配線.該模式已廣泛應(yīng)用于各大工業(yè)生產(chǎn)產(chǎn)業(yè)中.而混流多人共站裝配線平衡問題（mixedmodel multi-manned assembly line balancing problem，MMALBP）的研究非常有限：僅文獻(xiàn)[13]提出混合整數(shù)模型和模擬退火算法來求解第一類MMALBP（MMALBP-I，即給定節(jié)拍下，最小化工人/工位數(shù)量）；文獻(xiàn)[14]求解了一個基于MMALBP 特定的實際問題.

基于此，本文在文獻(xiàn)[13]的基礎(chǔ)上提出一個改進(jìn)的數(shù)學(xué)模型，以工人/工位數(shù)量為首要目標(biāo)，平滑指標(biāo)為次要目標(biāo)設(shè)計了一個改進(jìn)的雞群算法（improved chicken swarm optimization，ICSO）求解MMALBP-I.

1 問題描述和數(shù)學(xué)模型

本文研究的MMALBP-I 問題描述為：多種相似產(chǎn)品在一條混流直線型同步裝配線上生產(chǎn)，在不違背作業(yè)之間優(yōu)先關(guān)系約束和節(jié)拍約束前提下，將作業(yè)分配給工位中的工人，使得開啟的工位數(shù)量最小，分配的工人數(shù)也最小.同時，還需要滿足以下假設(shè)：1）作業(yè)時間是確定并提前給定的；2）不同模型產(chǎn)品的作業(yè)優(yōu)先關(guān)系是確定的，且可以匯總；3）由于工位的資源和空間等有限，每個工位分配的總工人數(shù)有上限；4）工位和工人都假定為同質(zhì)，即工位和工人理論上能處理任一作業(yè).

此外，工位之間的負(fù)荷均衡程度直接與在制品數(shù)量相關(guān)，因此本文以平滑系數(shù)作為輔助的目標(biāo).本文提出模型涉及的符號如表1 所示.

表1 符號含義Tab.1 Meaning of the notations

本文提出的數(shù)學(xué)模型表示如下：

目標(biāo)函數(shù)如式（1），以最小化工人數(shù)量為第一目標(biāo)，最小化工位數(shù)量為第二目標(biāo).式（2）～（4）、（10）確保變量之間的關(guān)系；式（5）、（6）確定每個作業(yè)開始時間的范圍；式（7）、（8）使得每個作業(yè)僅分配給一個工位的一個工人；式（9）確定存在優(yōu)先關(guān)系約束的作業(yè)之間的開始時間的關(guān)系；式（11）、（12）確定其他不存在優(yōu)先作業(yè)約束作業(yè)之間的開始時間關(guān)系.該模型的變量復(fù)雜度為Omax(Smaxn,Mmaxn,Mmaxn，SmaxWmax))，而原模型變量的復(fù)雜度為O(SmaxWmaxn)；此外，原模型約束總個數(shù)為 2n2SmaxWmaxMmax+n2SmaxMmax+nSmaxWmaxMmax+(n+3)SmaxWmax+2nMmax+n2+3Smax+n，而改進(jìn)后的模型的約束總個數(shù)為2n2Mmax+(n+2)SmaxWmax+(n+3)Smax+n2+2n+5nMm ax+nWmax.因此，改進(jìn)模型優(yōu)于原模型.

2 算法設(shè)計

2.1 算法原理

CSO（chicken swarm optimization）算法是Meng等[15]通過模擬雞群中不同等級秩序下不同群體行為提出的一種生物啟發(fā)式算法.每個種群分為3 個子群體即公雞群、母雞群和小雞群.NR、NHNC、NM分別為公雞群、母雞群、小雞群和有小雞的母雞群的個體的數(shù)量.其中適應(yīng)函數(shù)最佳的前NR個個體為公雞群，適應(yīng)值最差的后NC個個體為小雞群，其余為母雞群.總的個體數(shù)量為N.每個個體當(dāng)前（時間t）的位置為為最大的維度數(shù)量.每個子群體的行為方式均不一樣，其中公雞的更新方式如式（13）所示.

式中：fp為當(dāng)前被更新公雞的函數(shù)值；fq為當(dāng)前公雞群中除公雞p之外隨機(jī)選擇一只公雞的函數(shù)值q∈P,q≠p；ε 為一個很小的數(shù)，防止分母為0.

式（14）更新的核心思想為適應(yīng)值較好的公雞獲取食物的能力高于較差者，即適應(yīng)值越好的公雞可以在更廣的搜索空間內(nèi)進(jìn)行搜索.

母雞的更新方式如式（15）所示.式（15）表示當(dāng)前母雞p有S1rand 的概率朝公雞r1的方向覓食，也有S2rand 的概率朝其他個體r2的方向覓食.

式中：rand 為[0，1]區(qū)間符合均勻分布的隨機(jī)數(shù)；r1為母雞p對應(yīng)公雞的編號；r2為公雞群或母雞群中隨機(jī)選擇的一個個體的編號且

小雞的更新方式如式（16）所示，小雞會朝著其母親對應(yīng)的母雞的方向覓食.

式中：r3為小雞p對應(yīng)的母雞編號；FL為在(0,2)區(qū)間內(nèi)的一個參數(shù).

以上提及的CSO 算法是為求解連續(xù)優(yōu)化問題設(shè)計的一種啟發(fā)式算法，而本文求解的MMALBI 問題為離散組合優(yōu)化問題，因此需要對CSO 算法重新設(shè)計.

2.2 編碼解碼

針對MMALBP-I 問題，文獻(xiàn)[13]提出了基于優(yōu)先權(quán)值序列的編碼方式，同樣的編碼方式應(yīng)用在ICSO算法中.即在[bl,bu]區(qū)間內(nèi)隨機(jī)生成一個共N個值的序列，序列中第i個位置的值代表作業(yè)i對應(yīng)的優(yōu)先權(quán)值，如圖1所示.其中：bl和bu分 別為優(yōu)先權(quán)值的下界和上界，本文分別設(shè)定為?100、100.

圖1 編碼方法示例Fig.1 An example of the coding method

為了獲得一個可行的初始解，在可分配的作業(yè)集合中選擇優(yōu)先權(quán)值最小的作業(yè)優(yōu)先分配給開啟的工位和工人.如圖1 所示，每個圓圈代表一個作業(yè)，圓圈右上角的數(shù)字表示當(dāng)前作業(yè)的操作時間，箭頭則表示作業(yè)之間的優(yōu)先關(guān)系順序.如果作業(yè)1、2 已經(jīng)被分配，此時可分配作業(yè)集合包括作業(yè)3、4 和作業(yè)5.其中作業(yè)5 對應(yīng)的優(yōu)先權(quán)值最小，因此作業(yè)5被選中來分配.

步驟1開啟新的工位Ns=1，初始化當(dāng)前工位分配的工人數(shù)量為Nw=0，同時嘗試分配L=Wmax個工人給當(dāng)前工位；

步驟2確定可分配作業(yè)集合（集合內(nèi)每一個作業(yè)應(yīng)滿足無前序作業(yè)或者前序作業(yè)已經(jīng)被分配）.

步驟3若可分配作業(yè)集合不為空，轉(zhuǎn)步驟4，否則轉(zhuǎn)步驟7.

步驟4根據(jù)優(yōu)先權(quán)值序列，選擇一個作業(yè)i.

步驟5依次計算作業(yè)i分配給當(dāng)前工位的工人（1-L）對應(yīng)的完成時間，如果有一個或者多個滿足節(jié)拍約束，則選擇開始時間最早的工人l進(jìn)行分配，轉(zhuǎn)步驟6；否則，從可分配作業(yè)集合中剔除作業(yè)i，轉(zhuǎn)步驟2.

步驟6將作業(yè)i分配給當(dāng)前工位選中的工人l，更新相關(guān)的參數(shù)，轉(zhuǎn)步驟2.

步驟7如果所有作業(yè)完成分配，轉(zhuǎn)步驟8；否則按照工位接受準(zhǔn)則判斷是否接受該工位，如果是，則接受當(dāng)前工位的所有分配，Ns=Ns+1，Nw=Nw+L，更新相應(yīng)的參數(shù)；否則L=L?1，清空Ns工位分配的作業(yè).轉(zhuǎn)步驟2.

步驟8分配完成，計算函數(shù)值輸出.

工位的接受準(zhǔn)則定義為只需滿足以下（a 或b）一個條件即接受當(dāng)前工位的分配：

a）當(dāng)前工位的工人數(shù)量L=1 ；

b）滿足

式中：R為（0，1）之間符合均勻分布的隨機(jī)數(shù)，Tc為當(dāng)前溫度；δ=Midle?UB，Midle為平均的工人空閑時間，如式（18），Al為分配給當(dāng)前工位的工人l 的所有作業(yè)，UB為提前給定的一個能接受的空閑時間的上界，如式（19）.

2.3 目標(biāo)函數(shù)設(shè)計

設(shè)計的模型除了考慮如式（1）所示的函數(shù)目標(biāo)f1之外，額外添加了輔助目標(biāo)即最小化平滑指標(biāo)SI（如式（20）所示）.若兩個可行解對應(yīng)的f1相同時，則比較其SI，較小者更優(yōu).

式中：qm為模型m在所有模型中占的比例；lw,k為對應(yīng)第k個工人的負(fù)荷，即分配給該工人作業(yè)時間的總和；lw,max為所有工人負(fù)荷的最大值.

2.4 算法流程

ICSO 算法的步驟可以描述如下：

步驟1初始化雞群算法的參數(shù)，包括N、NR、NH、NC、NM；定義參數(shù)FL；最大迭代時間tmax；更新參數(shù)G.

步驟2隨機(jī)生成N個初始解，并評價其目標(biāo)函數(shù)，按從小到大排序，迭代次數(shù)g=0.

步驟3函數(shù)值排名前NR個個體確定為公雞群，后NC個個體確定小雞群；其他的個體為母雞群，此外，每個小雞隨機(jī)從母雞群中選擇一個作為母親；記錄時間t；

步驟4若t≤tmax，則轉(zhuǎn)步驟5，否則轉(zhuǎn)步驟7.

步驟5若（g%G==0），則轉(zhuǎn)步驟3；否則轉(zhuǎn)步驟6.

步驟6更新群體中每一個個體，公雞按式（13）更新；母雞按式（15）更新；小雞按式（16）更新；并計算更新后的函數(shù)值g=g+1；如果更新后的函數(shù)值不大于更新前的，則新的解取代之前的解，此外更新最優(yōu)解并轉(zhuǎn)步驟4.

步驟7輸出當(dāng)前最優(yōu)解.

3 實驗結(jié)果

本文的實驗結(jié)果分為兩部分，首先是針對小規(guī)模算例的求解，MMALBP-I 原模型和本文提出模型的實驗結(jié)果進(jìn)行比較；其次是針對大規(guī)模算例的求解，原算法模擬退火算法和本文提出的ICSO 算法的實驗結(jié)果進(jìn)行對比.本文的測試算例來自測試裝配線平衡問題的標(biāo)準(zhǔn)算例集（https://assembly-linebalancing.de/salbp/benchmark-data-sets-1993/）.其 中包括In1～ In12 問題，其優(yōu)先關(guān)系圖保持不變.由于文獻(xiàn)[13]的作者未提供其用于測試的數(shù)據(jù)集對應(yīng)的作業(yè)時間且與其聯(lián)系未果，所以本文隨機(jī)生成不同問題的作業(yè)時間.數(shù)據(jù)集的特征如表2 所示.其中Tmax和Tmin分別為最大的作業(yè)時間和最小的作業(yè)時間.此外，所有的程序在Inter? Core? i3,3.4 GHz處理器和 4.0 GB 內(nèi)存的計算機(jī)上運行.

表2 測試數(shù)據(jù)集特征Tab.2 The feature of test data sets

文獻(xiàn)[13]的模型和本文的模型均用OPL 語言編碼，在IBM ILOG CPLEX 12.6.3 軟件上運行.結(jié)果如表3 所示，其中～表示運行時間已經(jīng)達(dá)到預(yù)定的最大時間限制（1 h），模型未找到對應(yīng)算例的可行解或者最優(yōu)解；模型1 和模型2 分別表示文獻(xiàn)[13]的數(shù)學(xué)模型和本文提出解決數(shù)學(xué)模型；G% 是模型求解上下界的差值百分?jǐn)?shù)，當(dāng)G%=0 時，表示尋找到最優(yōu)解.

由表3 可知：模型1 和模型2 在求解In1、In2和In3，3 個n<9的算例時均找到最優(yōu)解，且求解時間均在1 s 之內(nèi)；在求解In4 和In5 兩個n=11 的算例時也找到最優(yōu)解，但模型1 的運行時間比模型2長；在求解In6 和In7 兩類n>20的共11 個算例中，在最大時間限制內(nèi)，模型1 僅求出其中2 個算例的最優(yōu)解，而模型2 求出其中10 個；模型2 求解的速度明顯快于模型1，因此證明模型2 比模型1 更優(yōu).

表3 模型對比結(jié)果Tab.3 Model comparison results

基于In7～I(xiàn)n12 共37 個算例，用文獻(xiàn)[13]提出的模擬退火（SA）算法和本文提出的ICSO 算法來進(jìn)行比較驗證.其中SA 算法的所有參數(shù)和步驟均與文獻(xiàn)[13]一致.而ICSO 共有6 個參數(shù)，其中N、NR、NH、NC、NM、G分別設(shè)定為100、15、70、15、50、10.此外FL設(shè)定如式（21）所示，迭代終止的條件為達(dá)到tmax，該時間設(shè)定為1 h.SA 算法和ICSO 算法均用MATLAB 語言編碼，并在軟件MATLAB R2016a 上運行，每個算例運行10 次，n≥70的算例包括In10、In11 和In12，計算結(jié)果如表4，其中：LE為效率指標(biāo)，如式（22）；LB為該問題的一個工人數(shù)量的下界，如式（23），LB,m為對應(yīng)模型m時處理該問題的工人數(shù)量的一個下界，如式（24）.

由表4 可知：針對較大規(guī)模算例，ICSO 算法優(yōu)于SA 算法.其中，加粗的部分為ICSO 算法找到的Ns(Nw)的最佳值優(yōu)于SA 算法的解.

表4 算法對比結(jié)果Tab.4 Comparison results of algorithms

此外，兩個算法針對In7～I(xiàn)n12 的所有算例的對比結(jié)果如表5 所示.其中：g1%為算法找到的工人數(shù)量與其對應(yīng)下界的差值百分比（式（25））；g2%為算法找到的工位數(shù)量與其對應(yīng)下界的差值百分比（式（26）），LB,s為處理該問題的工位數(shù)量的下界（式（27））；Db為指標(biāo)平均值和最佳值的差值；Dc為對應(yīng)指標(biāo)10 次運行結(jié)果的方差.

由表5 可知：

表5 對比結(jié)果匯總Tab.5 The summary of comparison results

1）ICSO 算法g1%的最佳值和平均值比SA 算法分別低6.62%和10.74%，說明ICSO 算法在測試的算例中找到了更多更接近工人數(shù)量下界的解；

2）ICSO 算法g2%的最佳值和平均值比SA 算法分別低7.04%和15.05%，說明ICSO 算法在測試算例中同樣找到了更多更接近工位數(shù)量下界的解；

3）在指標(biāo)SI的平均值上，ICSO算法同樣比SA算法找到更多更小的平滑指標(biāo)值；

4）g1%和g2%對應(yīng)的Db和Dc，ICSO算法均比SA算法低，說明ICSO相較于SA算法更穩(wěn)定，收斂性更強；

5）就時間的平均值而言，ICSO 算法比SA 算法高6 s，其中，求解算例In11 中，ICSO 算法的平均收斂時間是低于SA 算法，而求解算例In12 時，ICSO算法的平均收斂時間略高于SA 算法.

6）ICSO 算法在求解性能上優(yōu)于SA 算法.

4 結(jié) 論

為求解第一類混流多人共站裝配線平衡問題，本文提出一個改進(jìn)的數(shù)學(xué)模型，該模型比原模型復(fù)雜度更低，且求解性能更優(yōu).此外，針對大規(guī)模算例，提出一個改進(jìn)的雞群算法，實驗結(jié)果表明ICSO 算法優(yōu)于SA 算法.但本文只針對第一類問題進(jìn)行研究，下一步可以考慮第二類問題.

此外，本文僅考慮單一目標(biāo)，下一步可考慮多目標(biāo)優(yōu)化問題.最后，可以將ICSO 算法應(yīng)用到求解其他離散組合優(yōu)化問題.