基于混合優化算法的多目標裝配線平衡問題求解模型

李俊成 王 巍

（東北林業大學機電工程學院，黑龍江 哈爾濱 150040）

裝配線問題（Assembly Line Balancing Problem，ALBP）[1]在現代制造領域中具有重要地位，自福特汽車公司建立生產線以來，相關人員一直在探索和研究該問題，并在此期間進行了多次嘗試。

裝配線平衡問題的不同的目標函數主要分為3 類：在已知生產節拍的情況下，使工作站數最小化（即ALBP-Ⅰ）；在已知工作站數的情況下，使生產節拍最小化（即ALBP-Ⅱ）；在已知工作站數和生產節拍的情況下，使裝配線負荷更均勻，即平滑指數最小化（即ALBP-Ⅲ）。已知裝配線問題屬于NPhard 問題[2]，通常使用精確算法或元啟發式算法對裝配線平衡問題進行求解，例如原丕業等[3]提出的改進的自適應遺傳算法求解模型能夠更好地解決混流裝配線平衡問題。

本文根據裝配線平衡問題的特征，以最小化工作站數量、綜合考慮裝配線平衡率和平滑指數為優化目標建立裝配線平衡模型，并結合遺傳算法與蟻群算法，提出了一種混合優化算法模型（GA-ACO），以解決裝配線平衡問題。

1 裝配線平衡模型構建

本文研究的裝配線平衡問題是在生產節拍已知的情況下，在裝配過程中，各工序在緊前作業順序的約束下將全部工序安排到工作站中進行裝配作業，保證每個工作站的裝配時間不超過生產節拍，并盡量使安排的工作站數最少且每個工作站的裝配作業時間和裝配作業負荷盡量均衡。本文將裝配線平衡率和平滑指數作為評價指標，其中的裝配線平衡率表示裝配線的平衡狀況，平衡率越大，說明裝配線平衡效果越好。平滑指標表示裝配線的負荷狀況，平滑指數越小，說明裝配線負荷越均勻。本文將裝配線平衡率與平滑指數相結合，并作為目標函數。

1.1 假設

本文所提問題的基本假設如下。1）只對某一類產品進行裝配作業。2）每道工序作業時間是已知且確定的。3）所有作業工序必須滿足優先順序。4）每道工序只能分配到一個工作站中。5）每個工作站的裝配工作時間不能超過生產節拍。

1.2 數學模型

本文所提多目標裝配線平衡問題的數學描述如下。

裝配線平衡率P越大，表示裝配線平衡狀況越好，即裝配線空余時間最少；平滑指數SI越小，表示裝配線負荷越均勻。二者分別如公式（1）、公式（2）所示。

式中：P為裝配線平衡率；SI為平滑指數；m為工位的數量；sti為第i個工作站的工作時間；CT為生產節拍。

裝配線平衡優化目標函數H1、H2分別如公式（3）、公式（4）所示。

約束條件如公式（5）～公式（8）所示。任意2 個工作站不能出現重復的工序如公式（5）所示。任意1 個工作站的裝配時間都≦生產節拍如公式（6）所示。任意1 個裝配工序都應被分配到工作站中如公式（7）所示。每個工序的緊前作業關系如公式（8）所示。

式中：H1、H2表示目標函數；Mk1、Mk2分別為第k1個和第k2個工作站所分配工序的集合；Tk表示第k個工作站的所有工序裝配時間；M 表示所有工作站中工序的集合；Mk表示第k個工作站上所分配工序的集合；Pij=1 表示工序i是工序j的緊前作業順序；i∈Ma、j∈Mb表示工序i和工序j分別在第a個和第b個工作站完成。

2 混合優化算法求解

2.1 混合算法設計

本文將遺傳算法與蟻群算法相結合，提出了一種混合優化算法模型來求解裝配線平衡問題。首先，對遺傳算法參數進行初始化設置，用隨機拓撲法[4]按照工序順序圖生成初始序列，產生初始種群，然后計算初始種群的適應度值。其次，通過選擇、交叉和變異等方法生成新的種群，再計算新種群的適應度值。進行迭代調整后，得出最優結果。再次，將蟻群算法中所有參數進行初始化設置，將遺傳算法得到的最終解作為蟻群算法最初的信息素分布，隨機生成螞蟻的初始節點，根據概率選擇公式選擇下一可行節點，更新信息素，并計算每條路徑的信息素濃度。經過迭代調整后，生成裝配線平衡問題的最優解。混合優化算法模型求解裝配線平衡問題流程如圖1所示。

圖1 混合優化算法模型流程圖

2.2 遺傳算法設計

2.2.1 生成初始種群

本文要求初始群體中的所有作業序列均為可行作業序列，采用基于作業順序的染色體編碼規則。根據作業順序圖，用隨機拓撲排序法生成初始序列，以確保初始種群的多樣性。隨機拓撲排序的一般步驟如下。1）從序列圖中隨機選擇一個輸入度為0 的頂點并輸出。2）從序列圖中刪除該頂點和所有以該頂點為起點的有向線段。3）重復步驟1 和2，直到序列圖為空或者不存在輸入度為0 的頂點為止。4）輸出當前序列并生成初始種群

2.2.2 選擇

本文采用輪盤賭法進行選擇操作。個體的適應度值越高時，則個體被選中的概率越大，如公式（9）所示。

式中：Pxi表示個體被選中的概率；fxi表示被選中個體的適應度值；fxj表示不同個體的適應度值。

2.2.3 交叉

交叉是指從種群中根據概率隨機選擇2 個個體，并將2 個個體間的染色體進行交換。本文選擇的交叉方式是兩點交叉，即從染色體中隨機選擇2 個交叉點，將這2 個交叉點間的染色體進行交換，形成新的基因序列，如圖2所示。

圖2 交叉操作示意圖

2.2.4 變異

變異是指用其他等位基因替換個體染色體的基因座的基因值，從而形成一個新的個體，如圖3所示。

圖3 變異操作示意圖

2.3 蟻群算法設計

2.3.1 評價解的質量的目標函數

本文求解的是ALBP-Ⅰ問題，即明確生產節拍，使工作站數最少。在求解過程中，如果以目標函數H1為目標函數，會出現大量重復解，不易區分。因此，選用目標函數H2來評價解的質量。

2.3.2 信息素更新

本文的信息素更新策略為全局信息素更新。當螞蟻周游全部裝配工序并構建全局最優解后，才會添加信息素，從而使其他螞蟻跟隨，提高了搜索的目的性。當前迭代中，全局最優螞蟻會根據公式（10）、公式（11）更新全局信息素。

式中：τij為信息素強度；τij（t）為t時刻信息素強度；τij（t+1）為（t+1）時刻的信息素強度；ρ為信息素揮發系數；H2為當前最優分配方案的目標函數。

3 案例分析

基于上述算法的思路和流程，為了驗證其有效性，用MATLAB R2021b 實現上述算法，采用網址“https：//assemblyline-balancing.de/”中的標準算例進行測試和比較。分別用傳統遺傳算法模型與混合優化算法模型對裝配線平衡問題進行求解，并比較其平衡優化效果。

3.1 參數設置

本文采用經典問題Buxey 問題對模型進行驗證，并與實例庫中的其他案例[5-8]進行比較。Buxey 問題的作業優先順序如圖4所示。

圖4 Buxey 問題的作業優先順序圖

基于混合算法求解裝配線平衡問題，具體參數見表1。

表1 混合優化算法模型參數

3.2 實例結果分析

Buxey 問題由29 個裝配工序組成，當生產節拍CT=36s 時，混合算法模型所得裝配線平衡結果如圖5所示。

圖5 裝配線平衡圖

本文將混合算法模型與傳統遺傳算法模型所得結果進行比較，見表2 和表3。根據表2、表3 可知，當混合算法模型和遺傳算法模型在CT=36s 時，對于Buxey 問題，2 種算法模型都可以得出最小工作站數m=10 的結果，均為最優工作站數。但混合算法模型所得裝配線平衡率和平滑指數分別為0.952941%和2.04939，而遺傳算法模型所得裝配線平衡率和平滑指數分別為0.925714%和4.09878。顯而易見，混合算法模型所得裝配線平衡率更高且平滑指數更小，證明在裝配線平衡問題的求解方面，本文所提混合算法模型比遺傳算法模型更好。

表2 混合算法模型求解結果

表3 遺傳算法模型求解結果

為了更好地驗證本文混合算法模型的有效性，需要與文獻[5-8]中相同的經典案例進行比較，驗證結果見表4。根據表4 可知，混合優化算法模型求解裝配線平衡算例與遺傳算法模型有較明顯的差距。混合優化算法模型在每個算例的驗證中都得到了最優工作站數，而遺傳算法模型則在多種算例中多次出現未達到最優工作站數的情況。并且在2 種算法模型均達到最優工作站數的情況下，混合優化算法模型的目標函數值H2均不小于遺傳算法模型的目標函數值H2。因此在裝配線問題的求解中，本文提出的混合優化算法模型比遺傳算法模型更具有效性。

表4 經典算例驗證結果

4 結論

本文針對第一類裝配線平衡問題，并結合第三類裝配線問題提出了一種混合算法模型，在已知生產節拍的情況下，求解出最小工作站數、最大裝配線平衡率和最小平滑指數。該算法模型將遺傳算法與蟻群算法相結合，并以將遺傳算法最終解作為蟻群算法最初信息素分布的方式將2 種算法結合起來，從而有效改進前期收斂速度不足的問題。在目標函數上，增加了裝配線平衡率與平滑指數相結合的目標函數，能夠在2 種算法同時獲得最小工作站數的情況下更好地評價算法的優劣，進而選擇效果更好的算法。與經典算例進行比較后可知，在求解裝配線平衡問題方面，本文所提混合優化算法模型能夠獲得更多的最優解和最小的平滑指數。由此可以證明，本文所提GA-ACO 混合優化算法模型對裝配線平衡問題具有更好的求解能力。