張志穎，劉 鑫，聶迎春

（河北工業(yè)大學(xué) 經(jīng)濟(jì)管理學(xué)院，天津 300401）

0 引言

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

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

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

可見，上述研究將復(fù)雜性引入裝配線平衡優(yōu)化問(wèn)題中，探究多種因素對(duì)裝配線系統(tǒng)的影響并建模求解，提升裝配線的可靠性。但針對(duì)混流裝配線平衡問(wèn)題，考慮結(jié)構(gòu)復(fù)雜性中裝配關(guān)系復(fù)雜性對(duì)生產(chǎn)效率影響的研究較少，而且缺乏對(duì)裝配關(guān)系復(fù)雜性度量方法的研究。

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

1 問(wèn)題描述

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

裝配關(guān)系復(fù)雜性描述裝配產(chǎn)品所需要開展的各項(xiàng)任務(wù)及其任務(wù)之間關(guān)系復(fù)雜性的程度，其大小取決于產(chǎn)品裝配任務(wù)的數(shù)量及其各任務(wù)間的先后順序關(guān)系[12]。可見，裝配線上各個(gè)工作站作業(yè)之間的排序和數(shù)量均會(huì)影響該工作站裝配關(guān)系復(fù)雜度。若某工作站中裝配關(guān)系復(fù)雜度越高，則產(chǎn)品的裝配過(guò)程越繁瑣，一定程度上提高了工人的勞動(dòng)強(qiáng)度，且當(dāng)裝配過(guò)程出現(xiàn)錯(cuò)誤時(shí)，將耗費(fèi)更多的時(shí)間和精力檢查問(wèn)題工序的來(lái)源。因此需要量化裝配關(guān)系復(fù)雜性，使各工作站負(fù)荷均衡，減少裝配錯(cuò)誤。

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

圖1 三種產(chǎn)品優(yōu)先關(guān)系圖

圖2 聯(lián)合優(yōu)先關(guān)系圖

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

2 模型構(gòu)建

2.1 裝配關(guān)系復(fù)雜性度量

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

設(shè)裝配線產(chǎn)品任意作業(yè)為i，共有n個(gè)作業(yè)。構(gòu)成所有作業(yè)之間裝配關(guān)系的集合為G={g1，g2，g3，g4，g5}，其中g(shù)1=當(dāng)前作業(yè)直接前序，g2=當(dāng)前作業(yè)間接前序，g3=當(dāng)前作業(yè)的并行工序，g4=當(dāng)前作業(yè)直接后序，g5=當(dāng)前作業(yè)間接后序，該裝配關(guān)系集合可以表示作業(yè)在優(yōu)先關(guān)系中的位置特征。

信息熵，作為研究制造系統(tǒng)復(fù)雜性度量最重要的手段之一，可用于對(duì)一個(gè)系統(tǒng)中所包含的信息量和不確定性進(jìn)行度量。而復(fù)雜度是復(fù)雜性一個(gè)基本特征，一定程度上可用不確定性的測(cè)度來(lái)表示[18]。因此，本文用信息熵來(lái)描述各作業(yè)間裝配關(guān)系復(fù)雜程度。當(dāng)前作業(yè)5種裝配關(guān)系各自的數(shù)量占總裝配關(guān)系數(shù)量的比例分別表示為{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個(gè)作業(yè)裝配關(guān)系復(fù)雜性的信息量為：

其中概率元素ph≥0，，，對(duì)數(shù)一般取2為底，單位為比特，也可取其他對(duì)數(shù)底，使用相應(yīng)的單位。本文對(duì)數(shù)計(jì)算取2為底。

2.2 平衡模型的建立

2.2.1 模型參數(shù)

模型的參數(shù)和決策變量符號(hào)如下：

C為節(jié)拍；

n為作業(yè)總個(gè)數(shù)；

N為工作站總數(shù)量；

ti為聯(lián)合作業(yè)圖中第i 個(gè)作業(yè)的標(biāo)準(zhǔn)作業(yè)時(shí)間，i=1，2，3，…，n；

Pre(i)表示作業(yè)優(yōu)先關(guān)系集合，先于任務(wù)i完成得任務(wù)集合；

Hi為第i個(gè)作業(yè)裝配關(guān)系復(fù)雜度；

H(k)為第k個(gè)工作站裝配關(guān)系復(fù)雜度總和，k=1，2，3，…，N；

h為作業(yè)間裝配關(guān)系指數(shù)；

ph為作業(yè)間不同裝配關(guān)系占總裝配關(guān)系數(shù)量的概率；

m為混流裝配線產(chǎn)品種類；

D為混流裝配線產(chǎn)品總訂單數(shù)；

dj為產(chǎn)品j的訂單數(shù)量，j=1，2，3，…，m；

tij為j產(chǎn)品第i個(gè)作業(yè)的標(biāo)準(zhǔn)作業(yè)時(shí)間；

Gq為種群中第q個(gè)個(gè)體工作站數(shù)量；

P為種群規(guī)模；

2.2.2 目標(biāo)及約束

依據(jù)參數(shù)和定義可知，第k工作站各作業(yè)裝配關(guān)系復(fù)雜度之和為：

本文考慮到各個(gè)工作站裝配關(guān)系復(fù)雜性的平衡會(huì)影響工人作業(yè)效率，降低負(fù)荷，提高產(chǎn)品的一次通過(guò)率。除最小化生產(chǎn)節(jié)拍外，額外加入最小化裝配線平滑指數(shù)和裝配關(guān)系復(fù)雜度平滑指數(shù)[8]為優(yōu)化目標(biāo)，可以使裝配關(guān)系復(fù)雜度均衡分配，得到三個(gè)優(yōu)化目標(biāo)如下。其中最小化生產(chǎn)節(jié)拍為：

最小化各個(gè)工作站負(fù)荷的裝配線平滑指數(shù)為：

最小化裝配關(guān)系復(fù)雜性平滑指數(shù)為：

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

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

3 基于NSGA 2的模型求解過(guò)程

3.1 算法流程

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

圖3 NSGA2算法流程圖

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

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

初始化種群過(guò)程則產(chǎn)生作業(yè)隨機(jī)序列，根據(jù)聯(lián)合優(yōu)先關(guān)系圖，對(duì)作業(yè)進(jìn)行選擇和優(yōu)先關(guān)系檢查，將符合優(yōu)先關(guān)系的作業(yè)加入集合I中。若選擇的作業(yè)已經(jīng)在集合I中，則重新選擇作業(yè)。

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

圖4 類PMX交叉過(guò)程

變異過(guò)程采用倒位變異方式，即在一個(gè)染色體上隨機(jī)選擇兩個(gè)變異點(diǎn)，變異點(diǎn)之間的區(qū)域?yàn)樽儺悈^(qū)域，將變異區(qū)域倒序排列得到新的變異個(gè)體。如在染色體（1 3 |5 8 9 2 6| 7 4）上隨機(jī)兩個(gè)變異點(diǎn)為5和6，則將包括5和6之間的區(qū)域倒序，變異后染色體為（1 3 |6 2 9 8 5| 7 4）。

4 實(shí)例分析

4.1 案例數(shù)據(jù)

以某液壓泵混流裝配線為例進(jìn)行裝配線平衡優(yōu)化，驗(yàn)證本文優(yōu)化方法的有效性。該混流裝配線具有完備的工裝和電子設(shè)備，但部分工序操作復(fù)雜，工作站時(shí)間差異較大，且時(shí)常出現(xiàn)裝配錯(cuò)誤導(dǎo)致產(chǎn)品重裝或報(bào)廢的問(wèn)題，需要優(yōu)化線效率和產(chǎn)品質(zhì)量。整個(gè)裝配線共包含3種產(chǎn)品，65個(gè)作業(yè)任務(wù)，分配到11個(gè)工作站。本文選取一個(gè)訂單周期，根據(jù)訂單需求計(jì)算標(biāo)準(zhǔn)作業(yè)時(shí)間，并繪制聯(lián)合優(yōu)先關(guān)系圖如圖5所示。由于整條產(chǎn)線作業(yè)任務(wù)數(shù)量較多，工藝順序較復(fù)雜，人工得出優(yōu)化方案較為困難，有必要結(jié)合模型優(yōu)化得到分配方案。

圖5 聯(lián)合優(yōu)先關(guān)系

根據(jù)聯(lián)合優(yōu)先關(guān)系圖和式(2)可得各作業(yè)任務(wù)裝配關(guān)系復(fù)雜度，如表1所示。三種產(chǎn)品訂單需求比例為3∶1∶1，結(jié)合產(chǎn)品各自作業(yè)時(shí)間，用式(1)可求得各個(gè)作業(yè)任務(wù)的作業(yè)時(shí)間如表2所示。

表1 作業(yè)任務(wù)裝配關(guān)系復(fù)雜度

（續(xù)）

表2 作業(yè)任務(wù)時(shí)間

通過(guò)式(4)～式(6)計(jì)算可得當(dāng)前混流裝配線的生產(chǎn)節(jié)拍為596.2s，裝配線平滑指數(shù)SI≈58.0，裝配關(guān)系復(fù)雜性平滑指數(shù)為HSI≈26.5。

4.2 優(yōu)化結(jié)果分析

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

圖6 Pareto最優(yōu)前沿解集

圖7 生產(chǎn)節(jié)拍進(jìn)化過(guò)程

圖8 裝配線平衡指數(shù)進(jìn)化過(guò)程

圖9 裝配關(guān)系復(fù)雜性進(jìn)化過(guò)程

通過(guò)計(jì)算得到數(shù)個(gè)Pareto解集后，需要簡(jiǎn)單的人工選擇最優(yōu)解。在所有的優(yōu)化方案中，綜合考慮生產(chǎn)時(shí)間，各個(gè)工作站之間的負(fù)荷差異度，選擇C=499.6s，SI≈29.2，HSI≈12.0為最優(yōu)分配方案，其作業(yè)任務(wù)分布圖如圖10所示。與現(xiàn)有方案C=596.2s，SI≈58.0，HSI≈26.5相比，三個(gè)方面均有所改進(jìn)。

圖10 最優(yōu)方案作業(yè)任務(wù)分布

5 結(jié)語(yǔ)

本文為了進(jìn)一步平衡工作站負(fù)荷、提高混流裝配線的作業(yè)效率，選取裝配制造系統(tǒng)中裝配關(guān)系復(fù)雜性的特征，基于信息熵給出裝配關(guān)系復(fù)雜性的度量方法，將復(fù)雜性這一抽象的概念定量化，以生產(chǎn)節(jié)拍、裝配線平滑指數(shù)和裝配關(guān)系復(fù)雜性平滑指數(shù)為優(yōu)化目標(biāo)，建立多目標(biāo)混流裝配線平衡優(yōu)化模型，并運(yùn)用NSGA2進(jìn)行設(shè)計(jì)求解。通過(guò)實(shí)例分析可知本文提出的基于裝配關(guān)系復(fù)雜性的多目標(biāo)混流裝配線平衡優(yōu)化方法可以有效降低生產(chǎn)節(jié)拍，減少各工作站之間作業(yè)時(shí)間和工作負(fù)荷的差異，使各工作站裝配關(guān)系復(fù)雜性均衡，實(shí)現(xiàn)混流裝配線的平衡。后續(xù)可進(jìn)一步考慮裝配工位復(fù)雜度對(duì)裝配系統(tǒng)生產(chǎn)效率和產(chǎn)品質(zhì)量的影響。