基于混合優(yōu)化算法的飛機(jī)總裝脈動(dòng)生產(chǎn)線平衡問(wèn)題

潘志豪，郭 宇，查珊珊，章詩(shī)晨，王 彬

(1.南京航空航天大學(xué) 機(jī)電學(xué)院，江蘇 南京 210016;2.北京衛(wèi)星制造廠，北京 100190)

0 引言

隨著我國(guó)航空產(chǎn)業(yè)的加速發(fā)展，軍民各型飛機(jī)的生產(chǎn)訂單快速增長(zhǎng)，產(chǎn)品需求日趨多樣化。在這一背景下，為解決傳統(tǒng)的飛機(jī)總裝固定站位生產(chǎn)模式中存在的裝配效率低、生產(chǎn)現(xiàn)場(chǎng)混亂、質(zhì)量難保證[1]等不足，各生產(chǎn)廠商將裝配效率更高、產(chǎn)品質(zhì)量更穩(wěn)定的移動(dòng)生產(chǎn)模式應(yīng)用于飛機(jī)總裝生產(chǎn)線?，F(xiàn)有飛機(jī)總裝的移動(dòng)生產(chǎn)模式主要分為連續(xù)移動(dòng)式和脈動(dòng)式，其中脈動(dòng)生產(chǎn)模式相對(duì)于連續(xù)移動(dòng)生產(chǎn)模式具有生產(chǎn)柔性更高、產(chǎn)線運(yùn)行更平穩(wěn)、任務(wù)劃分更合理等優(yōu)勢(shì)，能夠更好地應(yīng)對(duì)多變的生產(chǎn)需求和復(fù)雜的飛機(jī)構(gòu)型。目前脈動(dòng)生產(chǎn)模式已經(jīng)在阿帕奇、F-35和波音787等飛機(jī)的總裝中成功應(yīng)用，極大地提高了飛機(jī)總裝的生產(chǎn)能力和經(jīng)濟(jì)效益[2]。脈動(dòng)生產(chǎn)模式在飛機(jī)總裝中的成功應(yīng)用離不開合理的生產(chǎn)線平衡方案，因此有必要結(jié)合飛機(jī)總裝以及脈動(dòng)生產(chǎn)模式的特點(diǎn)開展飛機(jī)總裝脈動(dòng)生產(chǎn)線平衡問(wèn)題(Aircraft Pulse Assembly Line Balancing Problem, APALBP)的研究工作。

由于移動(dòng)生產(chǎn)模式應(yīng)用于現(xiàn)代飛機(jī)總裝的時(shí)間較短，APALBP的相關(guān)研究文獻(xiàn)數(shù)量較少，亟需進(jìn)一步深入研究。其中Ríos等[3]以作業(yè)負(fù)載平滑為優(yōu)化目標(biāo)，通過(guò)仿真優(yōu)化獲取飛機(jī)總裝線平衡優(yōu)化結(jié)果；徐劍等[4]借助面向?qū)ο蠓謱淤x時(shí)Petri網(wǎng)建立飛機(jī)總裝生產(chǎn)線模型，并基于該模型運(yùn)用啟發(fā)式方法對(duì)第二類裝配線平衡問(wèn)題進(jìn)行優(yōu)化求解；張超等[5]通過(guò)粒子群算法對(duì)第二類飛機(jī)總裝移動(dòng)生產(chǎn)線平衡問(wèn)題進(jìn)行優(yōu)化求解，并借助仿真軟件進(jìn)行結(jié)果分析。相關(guān)研究主要基于簡(jiǎn)單裝配線平衡問(wèn)題(Simple Assembly Line Balancing Problem, SALBP)和一般裝配線平衡問(wèn)題(General Assembly Line Balancing Problem, GALBP)模型對(duì)飛機(jī)總裝線進(jìn)行平衡優(yōu)化，而未針對(duì)性地構(gòu)建APALBP模型，所得平衡優(yōu)化結(jié)果難以有效反映飛機(jī)總裝的實(shí)際生產(chǎn)情況。為提高研究的應(yīng)用價(jià)值，本文針對(duì)飛機(jī)總裝脈動(dòng)生產(chǎn)線多工種協(xié)同裝配以及多區(qū)域并行作業(yè)等特點(diǎn)建立多目標(biāo)多約束的APALBP數(shù)學(xué)模型，從而確?；谠撃Ｐ偷娘w機(jī)總裝脈動(dòng)生產(chǎn)線平衡優(yōu)化結(jié)果的有效性。

為獲取生產(chǎn)能力和經(jīng)濟(jì)效益綜合提升的平衡優(yōu)化結(jié)果，將裝配線平滑指數(shù)最小和人員總數(shù)最少作為飛機(jī)總裝脈動(dòng)生產(chǎn)線平衡優(yōu)化的目標(biāo)，同時(shí)根據(jù)生產(chǎn)線升級(jí)改造的實(shí)際需求和四類裝配線平衡問(wèn)題的特點(diǎn)[6]，選擇E類飛機(jī)總裝脈動(dòng)生產(chǎn)線平衡問(wèn)題(APALBP-E)為具體研究對(duì)象。其中因?yàn)檠b配線平衡問(wèn)題屬于NP-hard問(wèn)題，同時(shí)E類裝配線平衡問(wèn)題(Assembly Line Balancing Problem Type E, ALBP- E)中裝配節(jié)拍和站位數(shù)量均不確定，使得目標(biāo)函數(shù)具有多極值特點(diǎn)，進(jìn)一步提高了優(yōu)化求解的難度，所以傳統(tǒng)的精確求解算法難以在有限時(shí)間內(nèi)獲取高質(zhì)量的優(yōu)化結(jié)果，需采用近似求解算法進(jìn)行優(yōu)化求解。近年針對(duì)ALBP-E優(yōu)化方法的研究有：Masitah等[7]通過(guò)離散粒子群算法優(yōu)化求解多目標(biāo)E類單邊裝配線平衡問(wèn)題；Wei等[8]改進(jìn)了E類單邊裝配線平衡問(wèn)題數(shù)學(xué)模型，并通過(guò)啟發(fā)式算法優(yōu)化獲取優(yōu)化結(jié)果;Zacharia等[9]運(yùn)用改進(jìn)遺傳算法優(yōu)化求解模糊作業(yè)時(shí)間E類單邊裝配線平衡問(wèn)題。上述優(yōu)化求解方法主要是將ALBP-E分解為多個(gè)第二類裝配線平衡問(wèn)題并依次進(jìn)行求解，導(dǎo)致算法的求解的效率低下且效果不佳。為提高ALBP-E求解效率和結(jié)果質(zhì)量，本文設(shè)計(jì)一種混合優(yōu)化算法對(duì)APALBP-E進(jìn)行優(yōu)化求解，在求解過(guò)程中主要通過(guò)動(dòng)態(tài)搜索算法提高算法的求解效率和結(jié)果質(zhì)量，并通過(guò)改進(jìn)種群個(gè)體距離和萊維飛行距離計(jì)算方法來(lái)提高第二類非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithm-Ⅱ, NSGA-Ⅱ)和布谷鳥搜索(Cuckoo Search, CS)算法的尋優(yōu)能力。

本文對(duì)飛機(jī)總裝脈動(dòng)生產(chǎn)線的特點(diǎn)和平衡優(yōu)化需求進(jìn)行分析，并根據(jù)分析結(jié)果建立多目標(biāo)多約束的APALBP-E模型，同時(shí)針對(duì)模型特點(diǎn)設(shè)計(jì)一種混合優(yōu)化算法進(jìn)行優(yōu)化求解。最后通過(guò)標(biāo)準(zhǔn)案例測(cè)試以及應(yīng)用案例分析，證明本文算法性能優(yōu)異且能夠有效求解APALBP。

1 飛機(jī)總裝脈動(dòng)生產(chǎn)線平衡問(wèn)題描述

飛機(jī)總裝脈動(dòng)生產(chǎn)線的特點(diǎn)有：①在整線裝配中產(chǎn)品按節(jié)拍脈動(dòng)式向前移動(dòng)，在作業(yè)站位中產(chǎn)品采取類似固定站位裝配的作業(yè)方式，如圖1所示；②飛機(jī)由多系統(tǒng)組成且體型較大，各作業(yè)任務(wù)在站位中特定區(qū)域進(jìn)行，根據(jù)本文的應(yīng)用案例作業(yè)區(qū)域劃分為10個(gè)區(qū)域，如圖1站位5所示；③飛機(jī)裝配自動(dòng)化程度較低，并涉及多個(gè)技術(shù)領(lǐng)域，各作業(yè)任務(wù)需由相應(yīng)工種人員進(jìn)行。

根據(jù)以上特點(diǎn)對(duì)APALBP提出以下假設(shè)：①作業(yè)任務(wù)裝配時(shí)間確定；②所有任務(wù)都必須被分配到作業(yè)站位中；③人員被劃分為多個(gè)工種，各工種僅能參與相應(yīng)的作業(yè)任務(wù)；④同工種的人員裝配作業(yè)熟練度一致；⑤各作業(yè)站位間不進(jìn)行人員流動(dòng)；⑥在作業(yè)站位內(nèi)將裝配空間劃分為多個(gè)作業(yè)區(qū)域；⑦在作業(yè)站位中滿足裝配先后順序約束和作業(yè)區(qū)域互不干涉的約束條件下，允許不同工種參與的裝配任務(wù)并行作業(yè)，以5作業(yè)任務(wù)2工種的某作業(yè)站位為例，其中一個(gè)可行裝配序列根據(jù)SALBP的假設(shè)獲得的裝配甘特圖，如圖2a所示，而根據(jù)APALBP的假設(shè)將作業(yè)站位的裝配空間劃分為兩個(gè)作業(yè)區(qū)域，其中作業(yè)任務(wù)1，4的作業(yè)區(qū)域?yàn)?區(qū)域，作業(yè)任務(wù)2，3，5的作業(yè)區(qū)域?yàn)?區(qū)域，按照假設(shè)⑦可以得到作業(yè)站位的裝配甘特圖，如圖2b所示，作業(yè)任務(wù)1和3、2和4并行裝配。

2 飛機(jī)總裝脈動(dòng)生產(chǎn)線平衡問(wèn)題模型構(gòu)建

為進(jìn)一步挖掘飛機(jī)總裝脈動(dòng)生產(chǎn)線的生產(chǎn)能力，提高生產(chǎn)線的裝配效率和人員利用率，建立APALBP模型，并考慮人員工種約束和作業(yè)區(qū)域約束。

2.1 變量定義

n為裝配作業(yè)任務(wù)數(shù)量；

m為裝配線站位數(shù)量；

mmin為允許站位數(shù)量的下限；

mmax為允許站位數(shù)量的上限；

o為裝配線工種數(shù)量；

a為裝配作業(yè)區(qū)域數(shù)量；

i為裝配作業(yè)任務(wù)序號(hào)，i=1,2,3,…,n；

j為裝配線站位序號(hào)，j=1,2,3,…,m；

k為裝配線工種序號(hào)，k=1,2,3,…,o；

l為裝配作業(yè)區(qū)域序號(hào)，l=1,2,3,…,a；

si為作業(yè)任務(wù)的開始時(shí)間；

ci為作業(yè)任務(wù)的完成時(shí)間；

ti為作業(yè)任務(wù)i的裝配時(shí)間；

pi為作業(yè)任務(wù)i的參與人員數(shù)量；

CT為裝配線裝配節(jié)拍；

PK(i)為作業(yè)任務(wù)i同工種的前一作業(yè)任務(wù)；

PL(i)為作業(yè)任務(wù)i同作業(yè)區(qū)域的前一作業(yè)任務(wù)；

G為裝配作業(yè)任務(wù)優(yōu)先關(guān)系集合；

2.2 目標(biāo)函數(shù)

本文模型為最小規(guī)劃模型，為獲取裝配效率和人員利用率最優(yōu)的裝配線方案，選取平滑指數(shù)和作業(yè)人員總數(shù)作為APALBP的目標(biāo)函數(shù)。

(1)平滑指數(shù)

平滑指數(shù)(SI)反映各作業(yè)站位空閑時(shí)間的離散程度，用以評(píng)價(jià)生產(chǎn)線的裝配效率，

(1)

式中Tj為作業(yè)站位j的總裝配時(shí)間。

(2)作業(yè)人員總數(shù)

作業(yè)人員總數(shù)(SN)反映裝配線的人員配置情況，用以評(píng)價(jià)生產(chǎn)線的人員利用率，

(2)

式中Pjk為作業(yè)站位j中工種為k類的作業(yè)人員總數(shù)。

2.3 約束條件

根據(jù)飛機(jī)總裝脈動(dòng)生產(chǎn)線的特點(diǎn)以及平衡問(wèn)題的假設(shè)建立相應(yīng)的約束條件，約束條件的數(shù)學(xué)表達(dá)如下：

cPK(i)≤si,i=2,3,…,n;

(3)

cPL(i)≤si,i=2,3,…,n;

(4)

ci=max(cPL(i),cPK(i))+ti;

(5)

Tj=max(ci·xij),i=1,2,…,n;

(6)

Tj≤CT,j=1,2,…,m;

(7)

(8)

(9)

(10)

Pjk=max(pi·xij·yik),i=1,2,…,n。

(11)

其中：式(3)表示作業(yè)任務(wù)必須在同工種的前一任務(wù)完成以后才能開始裝配；式(4)表示作業(yè)任務(wù)必須在同作業(yè)區(qū)域前一任務(wù)完成以后才能開始裝配；式(5)表示作業(yè)任務(wù)裝配完成時(shí)間為最早開始時(shí)間加裝配時(shí)間；式(6)表示作業(yè)站位的所有作業(yè)任務(wù)完成時(shí)間為作業(yè)任務(wù)完成時(shí)間的最大值；式(7)表示作業(yè)站位的所有作業(yè)任務(wù)完成時(shí)間不能大于裝配節(jié)拍；式(8)表示每個(gè)作業(yè)任務(wù)只能被安排在一個(gè)作業(yè)站位；式(9)表示各作業(yè)任務(wù)互相之間的裝配先后順序關(guān)系；式(10)表示在裝配線中各作業(yè)區(qū)域一定會(huì)有作業(yè)任務(wù)進(jìn)行裝配；式(11)表示同站位中各工種的人數(shù)取該工種在該站位中單作業(yè)任務(wù)參與人數(shù)的最大值。

3 多目標(biāo)多約束優(yōu)化模型的求解算法及其性能測(cè)試

3.1 多目標(biāo)多約束優(yōu)化模型的求解算法設(shè)計(jì)

針對(duì)所建APALBP-E模型，設(shè)計(jì)一種混合優(yōu)化算法進(jìn)行求解。該算法混合改進(jìn)的NSGA、NS算法以及動(dòng)態(tài)搜索算法，其中改進(jìn)的NSGA優(yōu)化生產(chǎn)線裝配序列，NS算法尋找裝配線的最優(yōu)站位數(shù)量，動(dòng)態(tài)搜索算法則在多重解碼過(guò)程中尋找各裝配序列對(duì)應(yīng)的最優(yōu)站位數(shù)量和裝配節(jié)拍，圖3所示為混合優(yōu)化算法的運(yùn)行流程圖。

3.1.1 編碼和解碼

在個(gè)體的編碼上采用面向裝配序列的編碼方式[10]，該編碼方式保證優(yōu)化算法能夠完全搜索APALBP的裝配序列空間，但種群中會(huì)出現(xiàn)不滿足約束條件的個(gè)體編碼。以標(biāo)準(zhǔn)測(cè)試案例Mertens為示例，按照面向裝配序列的編碼方式可以得到示例編碼{1,3,2,4,6,7,5}，但由圖4左圖中的案例裝配先后關(guān)系有向圖可知，當(dāng)前編碼不滿足裝配先后順序約束，需根據(jù)圖4右圖中的裝配先后關(guān)系矩陣對(duì)編碼從左向右依次進(jìn)行約束檢查和次序調(diào)整，示例編碼經(jīng)調(diào)整后得到編碼{1,2,3,4,7,5,6}，滿足裝配先后順序約束。

因?yàn)樗Ｐ蜑锳PALBP-E模型，在ALBP-E中裝配節(jié)拍和站位數(shù)量均未知且二者相互影響，需要同時(shí)搜索二者的求解空間，其中站位數(shù)量的求解空間明顯小于裝配節(jié)拍的求解空間，所以圖3中的裝配序列解碼采用確定站位數(shù)量的第二類SALBP(SALBP-Ⅱ)解碼方法，其流程如下：

步驟1獲取站位數(shù)量種群中與當(dāng)前裝配序列個(gè)體對(duì)應(yīng)的站位數(shù)量m。

步驟3從左向右將個(gè)體編碼中未被分配的前s個(gè)作業(yè)任務(wù)分配到工作站位中，并以第s作業(yè)任務(wù)為工作站位中的最后一個(gè)作業(yè)任務(wù)，使第s個(gè)作業(yè)任務(wù)滿足cs≤CT

步驟4如果作業(yè)任務(wù)還有未分配的，且未分配到最后作業(yè)站位，則轉(zhuǎn)步驟3，否則進(jìn)行下一步操作。

步驟5當(dāng)作業(yè)任務(wù)分配到最后作業(yè)站位時(shí)，將個(gè)體編碼中所有未被分配的作業(yè)任務(wù)都分配到最后作業(yè)站位。

步驟6計(jì)算各作業(yè)站位的裝配時(shí)間和目標(biāo)函數(shù)，取當(dāng)前站位裝配時(shí)間的最大值作為裝配節(jié)拍CT。

3.1.2 動(dòng)態(tài)搜索算法

為提高解碼質(zhì)量和混合算法的求解效率，設(shè)計(jì)并運(yùn)用動(dòng)態(tài)搜索算法在多重解碼過(guò)程中搜索各裝配序列相應(yīng)的最優(yōu)站位數(shù)量和裝配節(jié)拍，如圖3所示。該算法根據(jù)前一次解碼結(jié)果動(dòng)態(tài)調(diào)整站位數(shù)量，減少對(duì)應(yīng)低質(zhì)量解的站位數(shù)量的解碼次數(shù)，提高解碼質(zhì)量和求解效率，算法具體步驟如下：

步驟1對(duì)個(gè)體解碼所得到的各站位裝配時(shí)間和裝配節(jié)拍CT進(jìn)行分析，以5站位的裝配線為例，可獲得以下3種情況：①最后一個(gè)作業(yè)站位的裝配時(shí)間遠(yuǎn)大于其余站位的裝配時(shí)間平均值，如圖5a所示，對(duì)二者的比值取整，其值大于1，轉(zhuǎn)步驟2；②最后一個(gè)作業(yè)站位的裝配時(shí)間遠(yuǎn)小于其余站位的裝配時(shí)間平均值，如圖6a所示，對(duì)二者的比值取整，其值小于1，轉(zhuǎn)步驟3；③最后一個(gè)作業(yè)站位的裝配時(shí)間接近其余站位的裝配時(shí)間平均值，如圖7a所示，對(duì)二者的比值取整，其值等于1，轉(zhuǎn)步驟4。

步驟4如果mmin≤m≤mmax，則CT=CT+r3·tmin，其中r3為(-1,1)范圍內(nèi)的隨機(jī)數(shù)，tmin為各作業(yè)任務(wù)裝配時(shí)間最小值，對(duì)CT取整后得到的裝配情況，如果結(jié)果如圖7b所示，轉(zhuǎn)步驟6，否則轉(zhuǎn)步驟5。

步驟6根據(jù)CT和m進(jìn)行解碼，獲取新的解并與之前解碼結(jié)果進(jìn)行支配關(guān)系比較，若新解支配當(dāng)前的最優(yōu)解或達(dá)到終止步長(zhǎng)，則跳出結(jié)束輸出本次搜索所得的非支配解及對(duì)應(yīng)的CT和m，否則轉(zhuǎn)步驟1。

3.1.3 布谷鳥搜索算法

CS算法由Yang等[11]于2009年提出，與其他群智能優(yōu)化算法相比具有收斂速度快、算法精度高、尋優(yōu)效果好等特點(diǎn)，本文根據(jù)站位數(shù)量尋優(yōu)的特點(diǎn)對(duì)CS算法進(jìn)行改進(jìn)，在萊維飛行的隨機(jī)步長(zhǎng)計(jì)算中增加當(dāng)前最優(yōu)站位數(shù)量的影響因式，從而提高CS算法搜索最優(yōu)站位數(shù)量的效率和質(zhì)量。

(12)

(13)

(14)

式中：β是一個(gè)[1,2]之間的參數(shù)，此處取β=1.5;u和v服從正態(tài)分布,即

(15)

(16)

在局部搜索的過(guò)程中，采用隨機(jī)步長(zhǎng)數(shù)組S更新布谷鳥蛋被發(fā)現(xiàn)的鳥巢，其表達(dá)為

(17)

式中r6為(0,1)的隨機(jī)數(shù)。此外Pa表示布谷鳥蛋被發(fā)現(xiàn)的概率，這里Pa=0.25，每個(gè)鳥巢是否被發(fā)現(xiàn)采用數(shù)組K表示,

(18)

其中隨機(jī)數(shù)Ra∈[0,1]。若Ra>Pa，則鳥巢主人發(fā)現(xiàn)布谷鳥蛋，Ki置一;否則鳥巢主人未發(fā)現(xiàn)布谷鳥蛋，Ki置零，第t+1代站位數(shù)量位置

(19)

3.1.4 第二類非支配排序遺傳算法

NSGA-Ⅱ由Deb[14]等于2002年對(duì)NSGA進(jìn)行改進(jìn)所得，其最大的改進(jìn)就是采用對(duì)結(jié)果進(jìn)行相似度計(jì)算遴選個(gè)體參與后續(xù)操作，從而避免種群早熟。而APALBP問(wèn)題的各代結(jié)果集中度高，因此改由相同解集合中隨機(jī)選取來(lái)進(jìn)行個(gè)體篩選。改進(jìn)后的NSGA-Ⅱ如圖3所示對(duì)裝配序列進(jìn)行優(yōu)化，具體過(guò)程如下：

步驟1由于個(gè)體的解相似度高且有大量個(gè)體對(duì)應(yīng)結(jié)果相同，采取從相同結(jié)果的個(gè)體中隨機(jī)選出代表個(gè)體，而不是如傳統(tǒng)NSGA-Ⅱ采用個(gè)體之間距離衡量相似度來(lái)進(jìn)行個(gè)體遴選。

步驟2對(duì)遴選后的種群進(jìn)行錦標(biāo)賽選擇操作，個(gè)體的優(yōu)劣評(píng)價(jià)采取Pareto排序，選擇每次隨機(jī)規(guī)模中的非支配解，組成隨后參與遺傳操作的新種群。

步驟3交叉操作，采用優(yōu)先交叉操作(Prece dence Operation Crossover, POX)[15]，交叉父代染色體中作業(yè)任務(wù)的裝配順序。操作過(guò)程如圖8所示，以案例Mertens的兩個(gè)裝配序列染色體P1和P2的POX交叉為例，將所有作業(yè)任務(wù)隨機(jī)劃分為作業(yè)任務(wù)集合J1和J2，將P1中集合J1和P2中集合J2的作業(yè)任務(wù)分別復(fù)制到子代C1和C2，再將集合J1和J2的作業(yè)任務(wù)分別按P2和P1的裝配順序補(bǔ)充到子代C2和C1中，完成POX交叉操作。

步驟4變異操作，采用多點(diǎn)鄰域變異。在染色體中隨機(jī)選取個(gè)別作業(yè)任務(wù)，并從該作業(yè)任務(wù)集合的排序鄰域中隨機(jī)選取一個(gè)替代當(dāng)前排序，如圖9所示，從染色體P1中隨機(jī)選取3個(gè)作業(yè)任務(wù)，其排序?yàn)閧4,5,3}，從該排序鄰域中隨機(jī)獲取新的排序{5,3,4}，并按照新的排序更新染色體獲取子代C1，完成多點(diǎn)鄰域變異操作。

3.2 算法復(fù)雜度分析

O(2N)+O(N)+gen[O(m0l0N)+O(m0

(N+Ng)2)+O(m0N)+O(N)+O(PaN)+

=O(gen(m0(N+Ng)2+(m0l0+m0+

(20)

3.3 算法性能測(cè)試

本文優(yōu)化算法程序采用MATLAB 2012a編寫，在Windows7 64位操作系統(tǒng)環(huán)境下運(yùn)行，運(yùn)行計(jì)算機(jī)配置為內(nèi)存8 G、處理器Intel(R)Core(TM)i7-3770。優(yōu)化算法參數(shù)設(shè)置如下：裝配序列和站位數(shù)量種群個(gè)數(shù)Size=100，最大迭代次數(shù)gen=100，交叉概率Pc=0.8，變異概率Pm=0.8，動(dòng)態(tài)搜索算法的終止步長(zhǎng)L=mmax-mmin+1。

為測(cè)試本文算法性能，采用由文獻(xiàn)[16]提供的SALBP-E測(cè)試案例，測(cè)試案例數(shù)據(jù)可從http://alb.mansci.de/獲得，選取文獻(xiàn)[8-9]的優(yōu)化結(jié)果進(jìn)行算法性能分析，對(duì)各測(cè)試案例連續(xù)運(yùn)行10次，從中選取最優(yōu)結(jié)果，為便于優(yōu)化結(jié)果進(jìn)行比較，采用相同的目標(biāo)函數(shù)

(21)

式中IT為裝配線空閑時(shí)間，運(yùn)行結(jié)果如表1所示，其中Scale為測(cè)試案例的裝配作業(yè)任務(wù)規(guī)模。各測(cè)試案例優(yōu)化求解的平均運(yùn)行時(shí)間均不超過(guò)20 s，由表1中優(yōu)化結(jié)果對(duì)比可知本文算法在多數(shù)測(cè)試案例上的表現(xiàn)優(yōu)于文獻(xiàn)[8-9]，且在個(gè)別案例中優(yōu)化結(jié)果較歷史結(jié)果減少近數(shù)倍。以測(cè)試案例Hahn為例，在站位數(shù)量范圍[3,8]的條件下，本文算法所得最優(yōu)解減小到僅有文獻(xiàn)[9]歷史最優(yōu)解的38%，裝配線空閑時(shí)間大幅減少，圖10所示為案例Hahn最優(yōu)解的甘特圖，同時(shí)本文算法求解個(gè)別案例可獲取多組優(yōu)化解，證明本文算法能夠有效克服目標(biāo)函數(shù)的多峰特性，較文獻(xiàn)[8-9]的算法有顯著提升。

表1 測(cè)試案例優(yōu)化求解結(jié)果

為檢驗(yàn)算法的收斂性能，選取表1中的4個(gè)測(cè)試案例在各自站位數(shù)量搜索范圍最大的條件下優(yōu)化求解連續(xù)運(yùn)行10次的所得解，對(duì)每代最優(yōu)解的目標(biāo)函數(shù)取平均值，獲得裝配空閑時(shí)間收斂曲線，如圖11所示，由圖可知本文算法能夠在給定的有限迭代次數(shù)中獲取最優(yōu)解，有效避免陷入局部最優(yōu)解。

4 應(yīng)用實(shí)例

為驗(yàn)證所建模型和求解算法的有效性，選取某飛機(jī)脈動(dòng)總裝生產(chǎn)線進(jìn)行應(yīng)用分析。該實(shí)例的裝配任務(wù)總共有76個(gè)，作業(yè)人員根據(jù)裝配工藝類別被劃分為7個(gè)工種，各站位根據(jù)裝配任務(wù)的作業(yè)區(qū)域被劃分為11個(gè)作業(yè)區(qū)域，如圖1中作業(yè)站位5所示，裝配任務(wù)的數(shù)據(jù)信息和先后次序關(guān)系如表2所示。

表2 某飛機(jī)脈動(dòng)總裝生產(chǎn)線裝配信息

任務(wù)序號(hào)裝配時(shí)間/h裝配人數(shù)人員工種裝配區(qū)域緊前任務(wù)13610—23810134112244171254363263223278633283217,8—98172310436141183535128172,3,96138414,5,7,87144417,88

續(xù)表2

續(xù)表2

續(xù)表2

在與算法性能測(cè)試相同的計(jì)算機(jī)環(huán)境下，運(yùn)用所提出的混合優(yōu)化算法分別對(duì)案例的SALBP-E和APALBP-E模型進(jìn)行平衡優(yōu)化，并根據(jù)不同的裝配線實(shí)施條件設(shè)置多組站位數(shù)量范圍，分別對(duì)不同的站位數(shù)量范圍連續(xù)運(yùn)行10次，平衡優(yōu)化所得結(jié)果如表3所示，其中averT為連續(xù)優(yōu)化求解10次的運(yùn)行時(shí)間平均值。

由表3可知，在不同的站位數(shù)量范圍條件下，APALBP-E模型平衡優(yōu)化所得的裝配線方案在裝配效率上均較SALBP-E模型平衡優(yōu)化所得方案有大幅提高，并且二者優(yōu)化解的人員規(guī)模相當(dāng)。以站位數(shù)量范圍[4,7]為例，APALBP-E模型平衡優(yōu)化所得方案在裝配節(jié)拍和平滑指數(shù)上均優(yōu)于SALBP-E模型，在作業(yè)人員數(shù)量也較SALBP-E模型有所減少，實(shí)現(xiàn)了在合理的人員配置條件下提高裝配效率的目標(biāo)。從各最優(yōu)裝配線方案中選取第一作業(yè)站位作為分析對(duì)象的裝配甘特圖如圖12和圖13所示，對(duì)比發(fā)現(xiàn)在APALBP-E模型中在滿足多約束的條件下，優(yōu)化結(jié)果充分體現(xiàn)了飛機(jī)總裝脈動(dòng)生產(chǎn)線多工種協(xié)同裝配、多區(qū)域并行作業(yè)的特點(diǎn)，整線裝配周期大幅減小，接近實(shí)際生產(chǎn)情況，證明基于該模型的平衡優(yōu)化結(jié)果能夠有效反映飛機(jī)總裝脈動(dòng)生產(chǎn)線的實(shí)際生產(chǎn)。

表3 案例平衡優(yōu)化的結(jié)果

5 結(jié)束語(yǔ)

本文針對(duì)飛機(jī)總裝脈動(dòng)生產(chǎn)線多工種協(xié)同裝配、多區(qū)域并行作業(yè)的特點(diǎn)，在對(duì)SALBP-E的假設(shè)條件和約束條件進(jìn)行補(bǔ)充細(xì)化的基礎(chǔ)上建立多目標(biāo)多約束的APALBP-E模型，并運(yùn)用一種混合優(yōu)化算法求解模型獲取最優(yōu)裝配線方案，經(jīng)算法性能測(cè)試和生產(chǎn)案例應(yīng)用分析得出以下結(jié)論：

(1)通過(guò)應(yīng)用案例分析證明，由APALBP-E模型平衡優(yōu)化所得的最優(yōu)裝配線方案較SALBP-E模型的優(yōu)化方案在人員規(guī)?；静蛔兦闆r下的裝配效率顯著提升，且有效反映飛機(jī)總裝脈動(dòng)生產(chǎn)線的實(shí)際生產(chǎn)情況。

(2)所提出的混合優(yōu)化算法在標(biāo)準(zhǔn)案例的測(cè)試中優(yōu)于近年文獻(xiàn)中的優(yōu)化算法，并在個(gè)別案例中提供多組優(yōu)化方案，證明該算法性能優(yōu)異并能夠有效解決APALBP-E的多極值問(wèn)題。

綜上所述，本文所建APALBP-E模型及混合優(yōu)化算法可以有效解決APALBP。在后續(xù)研究中，可考慮在該模型的基礎(chǔ)上進(jìn)一步完善APALBP模型，并改進(jìn)優(yōu)化算法提高APALBP的結(jié)果質(zhì)量和求解效率。