多人共站第一類混流裝配線平衡問題的優化

楊武成，程文明

（西南交通大學機械工程學院，四川 成都 610031）

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

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

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

基于此，本文在文獻[13]的基礎上提出一個改進的數學模型，以工人/工位數量為首要目標，平滑指標為次要目標設計了一個改進的雞群算法（improved chicken swarm optimization，ICSO）求解MMALBP-I.

1 問題描述和數學模型

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

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

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

本文提出的數學模型表示如下：

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

2 算法設計

2.1 算法原理

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

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

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

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

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

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

式中：r3為小雞p對應的母雞編號；FL為在(0,2)區間內的一個參數.

以上提及的CSO 算法是為求解連續優化問題設計的一種啟發式算法，而本文求解的MMALBI 問題為離散組合優化問題，因此需要對CSO 算法重新設計.

2.2 編碼解碼

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

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

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

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

步驟2確定可分配作業集合（集合內每一個作業應滿足無前序作業或者前序作業已經被分配）.

步驟3若可分配作業集合不為空，轉步驟4，否則轉步驟7.

步驟4根據優先權值序列，選擇一個作業i.

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

步驟6將作業i分配給當前工位選中的工人l，更新相關的參數，轉步驟2.

步驟7如果所有作業完成分配，轉步驟8；否則按照工位接受準則判斷是否接受該工位，如果是，則接受當前工位的所有分配，Ns=Ns+1，Nw=Nw+L，更新相應的參數；否則L=L?1，清空Ns工位分配的作業.轉步驟2.

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

工位的接受準則定義為只需滿足以下（a 或b）一個條件即接受當前工位的分配：

a）當前工位的工人數量L=1 ；

b）滿足

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

2.3 目標函數設計

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

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

2.4 算法流程

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

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

步驟2隨機生成N個初始解，并評價其目標函數，按從小到大排序，迭代次數g=0.

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

步驟4若t≤tmax，則轉步驟5，否則轉步驟7.

步驟5若（g%G==0），則轉步驟3；否則轉步驟6.

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

步驟7輸出當前最優解.

3 實驗結果

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

表2 測試數據集特征Tab.2 The feature of test data sets

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

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

表3 模型對比結果Tab.3 Model comparison results

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

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

表4 算法對比結果Tab.4 Comparison results of algorithms

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

由表5 可知：

表5 對比結果匯總Tab.5 The summary of comparison results

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

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

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

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

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

6）ICSO 算法在求解性能上優于SA 算法.

4 結 論

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

此外，本文僅考慮單一目標，下一步可考慮多目標優化問題.最后，可以將ICSO 算法應用到求解其他離散組合優化問題.