基于裝配關系復雜性測度的多目標混流裝配線平衡優化

張志穎，劉 鑫，聶迎春

（河北工業大學 經濟管理學院，天津 300401）

0 引言

裝配線平衡問題(Assembly Line Balancing Problem，ALBP)是運用優化方法，在工序優先關系和節拍等約束條件下將工序合理分配到工作站，使線上運營和生產系統流暢合理[1]。當前，市場需求正向著個性化和多元化的方向發展，產品的多樣化和規模化對制造企業的產能提出了新的要求。為提高企業產能，裝配線的平衡問題受到了國內外學者的廣泛關注與研究。隨著制造系統逐漸趨向于智能化和柔性化，裝配線系統也變得更加復雜。國內外學者對裝配線平衡的研究也從單品種到混流[2～4]，從簡單的設備、工藝、工人三方面演變成要額外考慮物料供應[5]、產品需求[6]、能源消耗等[7]不確定性因素的復雜系統。復雜的裝配線系統不僅包含更多的工序，其工序間的裝配關系也蘊含著更大的信息量[8]。這說明在裝配線平衡研究過程中，僅考慮線上工人操作等因素對生產效率和成本的影響只能保證裝配線局部最優。因此，需要探究裝配關系的復雜性對裝配線的影響，量化系統的不確定性，以提供更具實踐意義的解決方案。

制造系統復雜性指制造系統難以被理解、描述、預測和控制的狀態，可分為結構復雜性、過程復雜性和控制復雜性[9]。相關研究多集中于運用信息熵進行復雜性測度和從宏觀上構建制造系統中各類復雜性的理論框架。如Fujimoto[10]針對裝配多個階段設置相應的復雜性，運用信息熵對其進行度量；Sivadasan等[11]基于供應商-客戶系統操作操作復雜性，提出一種測量供應商-客戶系統信息需求的方法，并從信息論角度對該系統操作復雜性建立數學模型求解。何非等[12]將制造系統復雜性中結構復雜性進一步劃分成裝配關系復雜性、裝配工藝復雜性和系統配置復雜性，并以最小裝配關系復雜性差異度為優化目標建模求解。Efthymiou等[13]則對制造系統復雜性的建模方法進行了綜述，分析制造系統復雜性對生產過程產生的影響。

直到近幾年，關于制造系統運行優化的研究逐漸增加，更多學者開始深入研究實際生產過程中復雜性對裝配系統的影響。趙小松等[14]將工作站裝配復雜性作為人員疲勞等因素的誘因，以最小化裝配系統復雜性為優化目標建立模型并求解，提升工作站可靠性。劉亮等[15]發現并行裝配過程在實現產品多樣化的同時，制造復雜性則隨之提高，為解決該矛盾，提出考慮制造復雜性優化和顧客選擇的并行裝配系統設計方法。劉雪梅等[16]指出裝配過程中的不確定性會導致操作時間波動，于是基于信息熵提出工位復雜度度量方法，建立操作時間不確定的數學模型，減少不確定性因素干擾的同時平衡工位復雜度。李愛平等[8]提出了新的裝配關系復雜性度量方法，基于此建立多目標裝配線平衡優化模型，運用模糊聚類算法改進求解的遺傳算法交叉環節，從裝配關系復雜性角度提高裝配線效率。

可見，上述研究將復雜性引入裝配線平衡優化問題中，探究多種因素對裝配線系統的影響并建模求解，提升裝配線的可靠性。但針對混流裝配線平衡問題，考慮結構復雜性中裝配關系復雜性對生產效率影響的研究較少，而且缺乏對裝配關系復雜性度量方法的研究。

因此，本文考慮裝配關系復雜性對混流裝配線平衡的影響，基于信息熵提出混流裝配線裝配關系復雜性的度量方法，然后以生產節拍、裝配線平滑指數、裝配關系復雜性平滑指數建立一個多目標混流裝配線平衡優化模型，并運用第二代非支配排序遺傳算法（Nondominated Sorting Genetic Algorithm 2，NSGA 2）求解。最后，結合某公司泵體混流裝配線實例分析驗證優化方法，為該問題在企業實際工程中應用提供參考。

1 問題描述

Becker等[17]認為裝配線平衡問題主要分為四類，生產節拍一定，最小化工作站的數量；工作站數量一定，最小化生產節拍；生產節拍和工作站數量一定，求裝配線可行解；生產節拍與工作站數量待定，求裝配線可行解。本文研究屬于第二類裝配線平衡問題，工作站數量不變，最小化生產節拍。

裝配關系復雜性描述裝配產品所需要開展的各項任務及其任務之間關系復雜性的程度，其大小取決于產品裝配任務的數量及其各任務間的先后順序關系[12]。可見，裝配線上各個工作站作業之間的排序和數量均會影響該工作站裝配關系復雜度。若某工作站中裝配關系復雜度越高，則產品的裝配過程越繁瑣，一定程度上提高了工人的勞動強度，且當裝配過程出現錯誤時，將耗費更多的時間和精力檢查問題工序的來源。因此需要量化裝配關系復雜性，使各工作站負荷均衡，減少裝配錯誤。

單產品裝配線可根據工藝流程畫出作業優先關系圖，從而分析得到作業之間的裝配關系。混流裝配線則需要將線上所有產品的作業按優先關系綜合為一個聯合作業優先關系圖，繼而得到作業之間的裝配關系。混流裝配線上生產的多種產品工藝相似，但具體工序會有差異，需要將三個產品的作業優先關系圖綜合為一個聯合優先關系圖，如圖1和圖2所示。然后根據產品各自訂單數dj占總訂單數D的比例，求解出聯合優先關系圖中作業n的時間ti為：

圖1 三種產品優先關系圖

圖2 聯合優先關系圖

其中tij是每個產品各自作業的時間，i=1，2，3，…，n，j=1，2，3。若某產品工序不包含某個作業時，在計算該產品作業時記為零，這樣混流裝配線平衡問題便轉化為單一產品裝配線平衡問題。

2 模型構建

2.1 裝配關系復雜性度量

當前關于裝配關系復雜性度量方法的研究主要有兩類：一類在梳理各作業先后順序關系過程中，僅考慮直接前序、間接前序和并序對當前作業裝配關系復雜度的影響，忽略了后序與當前作業的裝配關系，并且該方法把每個作業自身裝配關系復雜度加入其后序作業裝配關系復雜度的計算，導致越靠后的作業復雜度越高，這與實際裝配線情況不相符[12]。另一類充分考慮前序、并序和后序對當前作業裝配關系復雜度的影響，但前序和后序作業中均存在直接和間接從屬兩種關系，需要加以區分[8]。因此，本文綜合考慮直接前序、間接前序、并序、直接后序、間接后序對當前作業影響，給出裝配關系復雜性的度量方法。

設裝配線產品任意作業為i，共有n個作業。構成所有作業之間裝配關系的集合為G={g1，g2，g3，g4，g5}，其中g1=當前作業直接前序，g2=當前作業間接前序，g3=當前作業的并行工序，g4=當前作業直接后序，g5=當前作業間接后序，該裝配關系集合可以表示作業在優先關系中的位置特征。

信息熵，作為研究制造系統復雜性度量最重要的手段之一，可用于對一個系統中所包含的信息量和不確定性進行度量。而復雜度是復雜性一個基本特征，一定程度上可用不確定性的測度來表示[18]。因此，本文用信息熵來描述各作業間裝配關系復雜程度。當前作業5種裝配關系各自的數量占總裝配關系數量的比例分別表示為{p1，p2，p3，…，ph}，即p1=g1/(g1+g2+g3+g4+g5)，p2=g2/(g1+g2+g3+g4+g5)，p3=g3/(g1+g2+g3+g4+g5)，p4=g4/(g1+g2+g3+g4+g5)，p4=g4/(g1+g2+g3+g4+g5)，則反映第i個作業裝配關系復雜性的信息量為：

其中概率元素ph≥0，，，對數一般取2為底，單位為比特，也可取其他對數底，使用相應的單位。本文對數計算取2為底。

2.2 平衡模型的建立

2.2.1 模型參數

模型的參數和決策變量符號如下：

C為節拍；

n為作業總個數；

N為工作站總數量；

ti為聯合作業圖中第i 個作業的標準作業時間，i=1，2，3，…，n；

Pre(i)表示作業優先關系集合，先于任務i完成得任務集合；

Hi為第i個作業裝配關系復雜度；

H(k)為第k個工作站裝配關系復雜度總和，k=1，2，3，…，N；

h為作業間裝配關系指數；

ph為作業間不同裝配關系占總裝配關系數量的概率；

m為混流裝配線產品種類；

D為混流裝配線產品總訂單數；

dj為產品j的訂單數量，j=1，2，3，…，m；

tij為j產品第i個作業的標準作業時間；

Gq為種群中第q個個體工作站數量；

P為種群規模；

2.2.2 目標及約束

依據參數和定義可知，第k工作站各作業裝配關系復雜度之和為：

本文考慮到各個工作站裝配關系復雜性的平衡會影響工人作業效率，降低負荷，提高產品的一次通過率。除最小化生產節拍外，額外加入最小化裝配線平滑指數和裝配關系復雜度平滑指數[8]為優化目標，可以使裝配關系復雜度均衡分配，得到三個優化目標如下。其中最小化生產節拍為：

最小化各個工作站負荷的裝配線平滑指數為：

最小化裝配關系復雜性平滑指數為：

混流裝配線平衡的約束如下：

其中約束(7)是工作站數目不變；約束(8)是每個工作站的總作業時間不能超過生產節拍；約束(9)是每個作業只能分配一次，不可再次分配；約束(10)是各個作業分配過程中必須滿足裝配的優先關系；約束(11)是作業在工作站分配情況的0/1型決策變量。

3 基于NSGA 2的模型求解過程

3.1 算法流程

本文采用NSGA 2[19]設計求解優化模型。在求解過程中，發現得出的優化方案類型較少，未能完全搜索裝配線作業任務的分配情況，為了更好的進行全局搜索，采用類PMX[20]（Partially Matched Exchange）的交叉方式，提高種群多樣性，避免過早產生局部最優解。算法具體流程圖如圖3所示。

圖3 NSGA2算法流程圖

3.2 編碼、初始化種群和交叉變異

本文涉及的混流裝配線平衡問題屬于JSP問題，需要對作業進行排序，因此編碼采用排列編碼法更為簡單可靠。每個作業對應一個基因位，按照優先關系將n個作業排成一排，N-1個分割點按升序排列到作業之后，組成長度為n+N-1的染色體。其中后面N-1個基因是工作站之間的分割點，可表示當前分配作業的數量。解碼則將染色體按照節拍約束和作業排列順序分配到各個工作站。

初始化種群過程則產生作業隨機序列，根據聯合優先關系圖，對作業進行選擇和優先關系檢查，將符合優先關系的作業加入集合I中。若選擇的作業已經在集合I中，則重新選擇作業。

為了提高種群多樣性，交叉過程采用類PMX的交叉方式。與傳統PMX方法中直接交換染色體交叉部分不同，類PMX則是將A、B兩個染色體各自的交叉部分分別放到對方染色體之前，并將A染色體剩余部分和B染色體交叉部分、B染色體剩余部分和A染色體交叉部分進行比對，若有和交叉部分相同的則刪除，過程如圖4所示。

圖4 類PMX交叉過程

變異過程采用倒位變異方式，即在一個染色體上隨機選擇兩個變異點，變異點之間的區域為變異區域，將變異區域倒序排列得到新的變異個體。如在染色體（1 3 |5 8 9 2 6| 7 4）上隨機兩個變異點為5和6，則將包括5和6之間的區域倒序，變異后染色體為（1 3 |6 2 9 8 5| 7 4）。

4 實例分析

4.1 案例數據

以某液壓泵混流裝配線為例進行裝配線平衡優化，驗證本文優化方法的有效性。該混流裝配線具有完備的工裝和電子設備，但部分工序操作復雜，工作站時間差異較大，且時常出現裝配錯誤導致產品重裝或報廢的問題，需要優化線效率和產品質量。整個裝配線共包含3種產品，65個作業任務，分配到11個工作站。本文選取一個訂單周期，根據訂單需求計算標準作業時間，并繪制聯合優先關系圖如圖5所示。由于整條產線作業任務數量較多，工藝順序較復雜，人工得出優化方案較為困難，有必要結合模型優化得到分配方案。

圖5 聯合優先關系

根據聯合優先關系圖和式(2)可得各作業任務裝配關系復雜度，如表1所示。三種產品訂單需求比例為3∶1∶1，結合產品各自作業時間，用式(1)可求得各個作業任務的作業時間如表2所示。

表1 作業任務裝配關系復雜度

（續）

表2 作業任務時間

通過式(4)～式(6)計算可得當前混流裝配線的生產節拍為596.2s，裝配線平滑指數SI≈58.0，裝配關系復雜性平滑指數為HSI≈26.5。

4.2 優化結果分析

通過以上數據收集，建立多目標數學模型，用MATLAB2019編程求解。其中NSGA 2算法的參數初始值設定如下：由于作業任務數量很多，設置種群規模P=200，迭代次數M=800，交叉概率Pc=0.7，變異概率Pm=0.3。初始節拍設置為C=680，給予適當的優化空間。經過計算得到優化后的Pareto前沿如圖6所示。圖上每一個點代表一個Pareto解集，對應三個目標函數值，每個解都至少在一個目標上優于現有方案。目標函數值隨迭代次數優化的過程分別如圖7～圖9所示。從圖中可看出，隨著遺傳代數的增加，三個目標的函數值都明顯降低，之后趨于平穩。

圖6 Pareto最優前沿解集

圖7 生產節拍進化過程

圖8 裝配線平衡指數進化過程

圖9 裝配關系復雜性進化過程

通過計算得到數個Pareto解集后，需要簡單的人工選擇最優解。在所有的優化方案中，綜合考慮生產時間，各個工作站之間的負荷差異度，選擇C=499.6s，SI≈29.2，HSI≈12.0為最優分配方案，其作業任務分布圖如圖10所示。與現有方案C=596.2s，SI≈58.0，HSI≈26.5相比，三個方面均有所改進。

圖10 最優方案作業任務分布

5 結語

本文為了進一步平衡工作站負荷、提高混流裝配線的作業效率，選取裝配制造系統中裝配關系復雜性的特征，基于信息熵給出裝配關系復雜性的度量方法，將復雜性這一抽象的概念定量化，以生產節拍、裝配線平滑指數和裝配關系復雜性平滑指數為優化目標，建立多目標混流裝配線平衡優化模型，并運用NSGA2進行設計求解。通過實例分析可知本文提出的基于裝配關系復雜性的多目標混流裝配線平衡優化方法可以有效降低生產節拍，減少各工作站之間作業時間和工作負荷的差異，使各工作站裝配關系復雜性均衡，實現混流裝配線的平衡。后續可進一步考慮裝配工位復雜度對裝配系統生產效率和產品質量的影響。