基于混合優(yōu)化算法的船用柴油機脈動裝配線平衡優(yōu)化技術(shù)研究＊

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

（江蘇科技大學機械工程學院，江蘇 鎮(zhèn)江 212003）

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

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

船用柴油機是典型的復雜產(chǎn)品，在傳統(tǒng)固定式裝配轉(zhuǎn)型為脈動式裝配線的過程中，其結(jié)構(gòu)復雜、零部件繁多、裝配工藝復雜等特點往往會導致裝配作業(yè)分配不均衡、裝配周期長、資源利用率較低等問題?；谝陨戏治?，構(gòu)建站位內(nèi)裝配生產(chǎn)線平衡的數(shù)學模型，制定裝配作業(yè)分配規(guī)則，并通過混合優(yōu)化算法對平衡方案進行求解。

1 脈動式裝配線站位內(nèi)平衡問題數(shù)學模型構(gòu)建

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

（1）平滑系數(shù)（SI）

本文采用站位內(nèi)所有班組空閑時間的標準差表示平滑系數(shù)。

式中：CT為裝配生產(chǎn)線節(jié)拍；m為站位內(nèi)班組數(shù)量；TTk（k=1,2,···,m）為班組內(nèi)裝配作業(yè)總時間。

（2）平衡率η

平衡率反映了產(chǎn)品的裝配效率。本文采用裝配線節(jié)拍與完成站位內(nèi)所有裝配作業(yè)的實際時間的比值表示平衡率。

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

為了優(yōu)化船用柴油機脈動式裝配生產(chǎn)線站位內(nèi)的裝配作業(yè)分配，選取平滑系數(shù)和平衡率作為優(yōu)化目標，構(gòu)建目標函數(shù) minF(m)為

約束條件構(gòu)建如下：

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

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

2 構(gòu)建基于遺傳算法和蟻群優(yōu)化算法（GAACO）的混合優(yōu)化模型

2.1 設計算法流程

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

圖1 混合優(yōu)化算法流程

2.2 基于GA-ACO 的求解模型

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

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

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

裝配作業(yè)工藝優(yōu)先關(guān)系有向圖，如圖2 所示。圈中和圈外的數(shù)字分別表示站位內(nèi)裝配作業(yè)編號以及對應站位內(nèi)裝配作業(yè)的工時（h）。

圖2 裝配作業(yè)工藝優(yōu)先關(guān)系有向圖

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

圖3 種群初始化流程

（2）制定裝配作業(yè)的分配規(guī)則

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

規(guī)則一：根據(jù)站位內(nèi)所有裝配作業(yè)累積工時與裝配生產(chǎn)線節(jié)拍的比值，設置初始班組數(shù)量。如果比值包含小數(shù)部分，將比值向上取整。

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

規(guī)則三：所有作業(yè)分配完畢后，若存在班組實際完成時間超過了CT，則重新調(diào)整班組數(shù)量。

具體流程如圖4 所示。

圖4 站位內(nèi)裝配作業(yè)均衡分配流程

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

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

（4）計算蟻群轉(zhuǎn)移概率以及構(gòu)造路徑

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

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

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

步驟二：從裝配作業(yè)數(shù)范圍內(nèi)隨機選擇螞蟻的初始節(jié)點，以初始化距離信息矩陣dimat。

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

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

步驟四：在獲取節(jié)點之后，為其分配轉(zhuǎn)移概率，并計算節(jié)點的累積轉(zhuǎn)移概率。

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

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

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

步驟八：根據(jù)裝配生產(chǎn)線的節(jié)拍CT約束，將已規(guī)劃的路徑中的裝配作業(yè)均衡地分配到各班組中。

（5）全局信息素更新

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

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

步驟一：記錄 maxcost和 mincost。

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

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

3 實例驗證

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

表1 詳細列出了預裝站位內(nèi)的裝配作業(yè)，而圖5展示了這些裝配作業(yè)之間的工藝優(yōu)先關(guān)系。根據(jù)表1 和圖5，將預裝站位內(nèi)的裝配作業(yè)轉(zhuǎn)化為工藝優(yōu)先關(guān)系矩陣圖，如圖2 所示。

表1 預裝配站位內(nèi)的裝配任務

圖5 預裝站位內(nèi)裝配作業(yè)工藝優(yōu)先關(guān)系有向圖

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

表2 預裝站位內(nèi)班組分配結(jié)果

表3 預裝站位內(nèi)裝配作業(yè)分配方案對比

圖6 預裝站位內(nèi)裝配作業(yè)工藝優(yōu)先關(guān)系矩陣圖

圖7 預裝站位內(nèi)裝配作業(yè)均衡分配甘特圖

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

圖8 GA、GA-ACO 混合優(yōu)化算法迭代優(yōu)化對比圖

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

基于以上分析可知，通過算法分配方案，可以實現(xiàn)班組數(shù)量減少、工期縮短和裝配作業(yè)更均衡地分配的優(yōu)勢。

4 結(jié)語

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

（1）本文致力于解決裝配生產(chǎn)線的平衡問題，通過考慮節(jié)拍、班組數(shù)量和裝配作業(yè)間的工藝優(yōu)先關(guān)系等約束條件，建立了一個數(shù)學模型，并提出了一套裝配作業(yè)分配規(guī)則，以提高班組效率和實現(xiàn)裝配作業(yè)的均衡分配。

（2）結(jié)合數(shù)學模型及裝配作業(yè)分配規(guī)則構(gòu)建了GA-ACO 混合優(yōu)化算法模型，并以某船用柴油機預裝站位內(nèi)所有裝配作業(yè)為驗證對象，證明了該方法的有效性。