基于混合優化算法的船用柴油機脈動裝配線平衡優化技術研究＊

陶 帥 張勝文 陳銀娟 王 沾 章 振

（江蘇科技大學機械工程學院，江蘇 鎮江 212003）

裝配階段是產品全生命周期中最重要、耗費大量資源與時間的步驟之一，其中，復雜產品的裝配過程需要占用整個生產過程中約33%的人力資源、40%以上的生產費用以及40%～60%的總生產工時[1]。裝配線平衡是通過合理的任務分配，確保各工作站的工作負荷相對均衡，以此來提高效率和資源利用率、縮短裝配周期和降低生產成本。目前，針對裝配線平衡問題，許多研究人員已經進行了大量研究。U?ur ?等[2]考慮并行裝配線中工人分配和裝配線平衡問題聯合周期時間最小化的研究，建立二元線性數學規劃模型，并提出了一種基于人工蜂群的大中型問題求解方法，與經典粒子群優化算法相對比驗證所提算法的有效性。Lakhdar B 等[3]針對機器人裝配線中最小化能源消耗問題，提出了一種基于記憶的布谷鳥搜索算法（MBCSA），得出較好的裝配線方案。Marcel A[4]提出了一種基于整數規劃的優化方法來解決自動化裝配線的動態資源重構問題，實現可重構生產，降低自動化裝配線的生產成本，同時提高可持續性。Bao Z K 等[5]針對某型飛機總裝線的平衡問題，提出了一種基于構造和改進的兩階段啟發式方法，并建立了一個整數線性規劃模型，有效降低了平衡工作站周期時間并最小化總資源投資成本。Niroomand S 等[6]通過人工電場算法以及模擬退火算法結合完整的編碼方案，解決了直線型裝配線平衡問題。Li Z 等[7]針對以成本為導向的裝配線平衡問題，提出了一種多目標混合整數規劃模型，并與多目標候鳥優化算法相結合，旨在縮短機器人采購周期和降低采購成本。Zhang B 等[8]針對混合模型U 型機器人裝配線的平衡與排序問題，建立該雙目標問題的數學模型，并對基本蜻蜓算法進行改進，最后與HMODA 算法進行對比體現出所提算法的優越性。Zhong Y[9]提出了一種有效的離散人工魚群算法來解決以成本為導向的裝配線平衡問題，該算法的目標是使建造成本最小化，通過大量的計算實驗，驗證了所提出的人工魚群算法的有效性。鄭諧等[10]針對飛機脈動式裝配線平衡問題,建立飛機脈動式裝配線站位內平衡問題模型，并結合改進的遺傳算法，實現了脈動式裝配線站位內的裝配線平衡。

基于以上分析，裝配生產線平衡問題的解決方法在不斷發展和完善。不同的方法具有不同的特點，并且適用于不同的裝配生產線平衡目標。由此，在研究裝配生產線平衡問題時，需要綜合考慮企業的生產狀況、裝配流程特點，并利用智能優化算法解決問題。

船用柴油機是典型的復雜產品，在傳統固定式裝配轉型為脈動式裝配線的過程中，其結構復雜、零部件繁多、裝配工藝復雜等特點往往會導致裝配作業分配不均衡、裝配周期長、資源利用率較低等問題。基于以上分析，構建站位內裝配生產線平衡的數學模型，制定裝配作業分配規則，并通過混合優化算法對平衡方案進行求解。

1 脈動式裝配線站位內平衡問題數學模型構建

本文主要研究船用柴油機脈動式裝配線各站位內裝配作業平衡分配問題，主要表現為：在滿足工藝優先關系、站位內所有裝配作業的完成時間不超過裝配生產線節拍等約束條件下，將站位內的裝配作業均衡、有序地分配給各個班組，并綜合考慮了裝配生產線的平衡率和平滑系數，以及本研究的目標是將站位內的裝配作業分配實現均衡，并以最大化班組效率為優化目標。考慮船用柴油機脈動式裝配流程，構建目標函數和約束條件。

（1）平滑系數（SI）

本文采用站位內所有班組空閑時間的標準差表示平滑系數。

式中：CT為裝配生產線節拍；m為站位內班組數量；TTk（k=1,2,···,m）為班組內裝配作業總時間。

（2）平衡率η

平衡率反映了產品的裝配效率。本文采用裝配線節拍與完成站位內所有裝配作業的實際時間的比值表示平衡率。

式中：Tk為第k（k=1,2,···,m）個班組的實際裝配時間。

為了優化船用柴油機脈動式裝配生產線站位內的裝配作業分配，選取平滑系數和平衡率作為優化目標，構建目標函數 minF(m)為

約束條件構建如下：

式中：Qk1和 Qk2分別為班組k1 和班組k2 的裝配作業集合，k=k1、k2，且k1≠k2；H為站位內可用人員數量；xik表示第i項裝配作業被分配到班組k中；Pij為第i項裝配作業和第j項裝配作業工藝優先關系，i,j=1,2,···,n，且i≠j。

上述公式描述了裝配生產線站位內的優化條件，式（4）代表著每個班組不會重復進行相同的操作；根據式（5），每個班組必須遵守裝配生產線規定的裝配過程時間，以確保其準確性；根據式（6），為了確保每個班組能夠順利完成裝配任務，所需的人員數量必須達到規定的標準，以支持并行裝配，并且人員數量不會少于班組數；根據式（7）和式（8），每一個裝配任務必須僅由一個班組完成并且保證所有裝配任務完全分配；根據式（9），裝配任務的安排應當遵循工藝優先原則。

2 構建基于遺傳算法和蟻群優化算法（GAACO）的混合優化模型

2.1 設計算法流程

本文采用GA-ACO 作為一種混合優化算法，用于解決船用柴油機脈動式裝配生產線的平衡問題。算法流程如圖1 所示。

圖1 混合優化算法流程

2.2 基于GA-ACO 的求解模型

為了解決脈動式裝配線站位內裝配作業平衡分配問題，將GA-ACO 與脈動式裝配線站位內平衡問題數學模型相結合，以快速生成裝配作業平衡分配方案，解決裝配線平衡問題。

（1）遺傳算法種群初始化

基于裝配作業編號進行染色體編碼，以避免運算量大的進制轉換問題，同時隨機生成初始種群用于GA 算法。此外，生成初始種群時需要考慮實際裝配作業的工藝優先關系。

裝配作業工藝優先關系有向圖，如圖2 所示。圈中和圈外的數字分別表示站位內裝配作業編號以及對應站位內裝配作業的工時（h）。

圖2 裝配作業工藝優先關系有向圖

由圖2 可知，根據設計的編碼方式，生成了染色體序列[3,1,5,2,4,8,6,7]。然而，該序列并不符合裝配作業的工藝優先關系。基于以上分析，根據裝配作業工藝優先關系矩陣進行解碼和調整，得到可行的染色體序列[1,3,2,5,4,6,7,8]，具體流程如圖3所示。

圖3 種群初始化流程

（2）制定裝配作業的分配規則

制定裝配作業分配規則，將可行染色體個體代表的裝配作業流程合理地分配到可選班組中，以解決裝配生產線平衡問題，規則如下。

規則一：根據站位內所有裝配作業累積工時與裝配生產線節拍的比值，設置初始班組數量。如果比值包含小數部分，將比值向上取整。

規則二：當前待分配作業應分配到累計作業時間最少的班組中。

規則三：所有作業分配完畢后，若存在班組實際完成時間超過了CT，則重新調整班組數量。

具體流程如圖4 所示。

圖4 站位內裝配作業均衡分配流程

（3）染色體交叉、變異操作

設定交叉率PC，使用雙點交叉方式生成新的染色體個體，以更大程度地改變其結構。通過在染色體個體上交換基因位置，以設定的變異率PM 來生成新的個體。

（4）計算蟻群轉移概率以及構造路徑

通過使用GA 和ACO 算法，創建一個高效的信息素初始分布矩陣，從而幫助螞蟻找到最優的行進路線。為了更好地實現這一目標，將采用以下步驟。

步驟一：使用遺傳算法（GA）得到的優秀解，基于信息素增強因子Q，更新蟻群算法（ACO）的初始信息素矩陣Tau（n階矩陣）。在信息素矩陣Tau中，需要更新的位置被標記為Tau(bestChrom(i),bestChrom(i+1))，則：

式中：bestChrom(i)、bestChrom(i+1)表示遺傳算法求得的較優裝配作業排序中的相鄰項，其中前者表示第i項作業編號，后者表示第i+1 項作業編號。

步驟二：從裝配作業數范圍內隨機選擇螞蟻的初始節點，以初始化距離信息矩陣dimat。

步驟三：使用信息素矩陣Tau和啟發值矩陣Eta，并基于信息素因子Alpha以及啟發值因子Beta，構建了螞蟻轉移概率模型p，則有：

式中：currentNode表示當前選中的節點；temporarynextNode表示下一個待選節點；TAU（currentNode,temporarynextNode）表示需要更新信息素矩陣Tau的位置；ETA（currentNode,temporarynextNode）表示需要更新啟發值矩陣Eta的位置。

步驟四：在獲取節點之后，為其分配轉移概率，并計算節點的累積轉移概率。

步驟五：將隨機數[0,1]與累積概率進行比較，選擇下一個節點，更新螞蟻的搜索路徑。

步驟六：隨著不斷地迭代更新，若節點全部選取完畢，則執行步驟七，否則繼續執行步驟五。

步驟七：鑒于螞蟻路徑與裝配工藝的優先級不一致，為了使它們達到預期的效果，必須對它們進行解碼處理，以此來滿足裝配工藝的優先關系需求。

步驟八：根據裝配生產線的節拍CT約束，將已規劃的路徑中的裝配作業均衡地分配到各班組中。

（5）全局信息素更新

螞蟻每周遍歷所有的裝配作業號，生成裝配作業序列，并更新最優解的信息素，吸引后者跟隨。本文旨在提高算法搜索效率，采用全局信息素更新策略，選擇最優螞蟻對其進行全局信息素更新，并且只將信息素添加到當前的全局最優解中。更新公式：

式中：cost(u) 表示第u個螞蟻的價值評價函數值；kv表示價值區間的下限；l表示價值區間范圍大小；value(u) 表示第u個螞蟻適應能力值；mincost表 示種群適應度下限；maxcost表示種群適應度上限；route(r) 表示第u個螞蟻路徑中第r個節點；Tau(route(r),route(r+1))代表信息素矩陣Tau中需要更新的位置；rho為信息素揮發系數，取值范圍為[0,1]。具體步驟如下。

步驟一：記錄 maxcost和 mincost。

步驟二：使用適應度上限 maxcost和適應度下限mincost對價值區間進行歸一化，并創建螞蟻個體的價值評估函數cost(u)。

步驟三：利用增強因子Q、揮發系數rho和價值評價函數cost(u)，更新信息素矩陣Tau。

3 實例驗證

基于上述數學模型和約束條件，使用GA-ACO混合優化算法進行船用柴油機脈動式裝配生產線預裝站位內所有裝配作業的均衡分配的驗證。

表1 詳細列出了預裝站位內的裝配作業，而圖5展示了這些裝配作業之間的工藝優先關系。根據表1 和圖5，將預裝站位內的裝配作業轉化為工藝優先關系矩陣圖，如圖2 所示。

表1 預裝配站位內的裝配任務

圖5 預裝站位內裝配作業工藝優先關系有向圖

假設在給定條件下（預裝站位的工期為12 天，每日工時為10 h，可用工人數量為6 人），進行優化方案的計算。這些方案旨在實現裝配作業的均衡分配。盡管這些方案可能會在裝配作業的順序安排上存在差異，特別是在非關鍵路徑上的裝配作業的分配方式可能有多種選擇，但它們都滿足了相同的目標和約束條件。圖6 所示為一種較優的裝配作業均衡分配方案的甘特圖，班組分配結果見表2。將算法分配結果與現場人工分配結果進行比較，比較結果見表3。現場人工分配根據裝配作業的工藝優先關系和人工經驗，確保預裝站位內的裝配作業完成時間不超過生產節拍（圖7）。

表2 預裝站位內班組分配結果

表3 預裝站位內裝配作業分配方案對比

圖6 預裝站位內裝配作業工藝優先關系矩陣圖

圖7 預裝站位內裝配作業均衡分配甘特圖

由圖8 可知，本文所提的 GA-ACO 混合優化算法在處理裝配作業繁多的裝配線平衡問題上，相比單一的 GA 能夠更有效且較快地求解出裝配線平衡問題的最優解。

圖8 GA、GA-ACO 混合優化算法迭代優化對比圖

由表3 數據可見，采用算法分配方式可以節約班組數量2 個，縮短工期4 h，降低了1.14 的平滑系數，提高了3%的平衡率。

基于以上分析可知，通過算法分配方案，可以實現班組數量減少、工期縮短和裝配作業更均衡地分配的優勢。

4 結語

本文聚焦于解決船用柴油機脈動式裝配生產線平衡問題，提出一種基于混合優化算法的脈動生產線站位內裝配作業平衡分配方法。

（1）本文致力于解決裝配生產線的平衡問題，通過考慮節拍、班組數量和裝配作業間的工藝優先關系等約束條件，建立了一個數學模型，并提出了一套裝配作業分配規則，以提高班組效率和實現裝配作業的均衡分配。

（2）結合數學模型及裝配作業分配規則構建了GA-ACO 混合優化算法模型，并以某船用柴油機預裝站位內所有裝配作業為驗證對象，證明了該方法的有效性。