方 佳， 陸志強(qiáng)

(同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院， 上海 201804)

飛機(jī)移動(dòng)裝配線因其較高的裝配效率和相對(duì)穩(wěn)定的裝配過程被越來越多的飛機(jī)制造企業(yè)所采納.飛機(jī)裝配是飛機(jī)制造過程中的重要環(huán)節(jié)，對(duì)飛機(jī)裝配過程中的作業(yè)實(shí)現(xiàn)科學(xué)的調(diào)度有助于提高飛機(jī)制造行業(yè)的生產(chǎn)效率并降低生產(chǎn)成本.

飛機(jī)移動(dòng)裝配生產(chǎn)線的調(diào)度問題可以抽象為資源受限項(xiàng)目的調(diào)度問題.對(duì)確定性環(huán)境下的資源受限項(xiàng)目調(diào)度問題的研究已經(jīng)比較充分，算法主要分為精確算法、啟發(fā)式算法和元啟發(fā)式算法[1-2].但確定性環(huán)境中的調(diào)度問題研究對(duì)作業(yè)工期、物料供應(yīng)情況、機(jī)器設(shè)備狀態(tài)等的假設(shè)都較為理想化，不符合項(xiàng)目執(zhí)行過程中干擾及不確定因素較多的實(shí)際情況.因此，近幾年的研究主要圍繞不確定環(huán)境下的調(diào)度問題展開[3].

為了解決不確定因素影響下的調(diào)度問題，現(xiàn)有文獻(xiàn)提出的方法主要有兩種，即反應(yīng)式調(diào)度方法和前攝型調(diào)度方法.反應(yīng)式調(diào)度方法的相關(guān)研究中，Elloumi等[4]在多模式資源受限項(xiàng)目調(diào)度問題的基礎(chǔ)上，考慮模式切換受干擾的場(chǎng)景，以項(xiàng)目執(zhí)行總工期和穩(wěn)定性評(píng)價(jià)指標(biāo)為目標(biāo)，建立了多目標(biāo)模型并提出新的啟發(fā)式進(jìn)化算法修復(fù)調(diào)度計(jì)劃.Paprocka等[5]建立了流水車間多目標(biāo)模型，設(shè)計(jì)了一種混合多目標(biāo)免疫反應(yīng)調(diào)度算法以應(yīng)對(duì)操作出現(xiàn)中斷的情況，為流水車間的動(dòng)態(tài)調(diào)度研究提供了新的思路.

上述反應(yīng)型調(diào)度方法通常都是在模板調(diào)度計(jì)劃已經(jīng)給定的情況下，在擾動(dòng)事件發(fā)生時(shí)才通過一系列的策略對(duì)未執(zhí)行的作業(yè)進(jìn)行調(diào)度，以減小此擾動(dòng)對(duì)模板計(jì)劃造成的影響.這種方法適用于復(fù)雜的大型隨機(jī)制造系統(tǒng)，在不確定因素對(duì)系統(tǒng)產(chǎn)生的影響難以預(yù)測(cè)的情況下才比較高效.而前攝型調(diào)度方法在擾動(dòng)事件未發(fā)生時(shí)，就對(duì)其可能產(chǎn)生的影響進(jìn)行了預(yù)期，通過生成具有魯棒性的模板調(diào)度計(jì)劃應(yīng)對(duì)隨機(jī)干擾事件.Van de Vonder等[6-7]指出相比于純反應(yīng)調(diào)度方法，前攝型調(diào)度方法通常更高效.現(xiàn)有文獻(xiàn)中對(duì)不確定調(diào)度問題的研究通常將前攝型調(diào)度方法與魯棒調(diào)度以及魯棒優(yōu)化理論相結(jié)合進(jìn)行研究，目的是提供可應(yīng)對(duì)不確定事件的魯棒性較好的前攝型調(diào)度計(jì)劃[8].而前攝型調(diào)度方案的魯棒性評(píng)價(jià)指標(biāo)通常分為兩類，分別是解魯棒性和質(zhì)量魯棒性，前者用于評(píng)價(jià)不確定事件發(fā)生后實(shí)際調(diào)度計(jì)劃與初始調(diào)度計(jì)劃的接近程度，現(xiàn)有文獻(xiàn)中常根據(jù)實(shí)際需求設(shè)置最小化作業(yè)的開始時(shí)間偏差加權(quán)和或最小化偏差成本等優(yōu)化指標(biāo)；后者評(píng)價(jià)不確定事件發(fā)生時(shí)實(shí)際調(diào)度計(jì)劃的目標(biāo)值與最優(yōu)初始調(diào)度計(jì)劃目標(biāo)值的接近程度，現(xiàn)有文獻(xiàn)中常見的優(yōu)化目標(biāo)有最小化最大完工時(shí)間或拖期等.這兩種指標(biāo)雖然有所差異，但都說明了如果實(shí)際調(diào)度計(jì)劃與初始調(diào)度計(jì)劃的接近程度越高，則表明初始調(diào)度計(jì)劃的魯棒性越好[9].

本研究的主要問題是基于前攝型調(diào)度并采用解魯棒性指標(biāo)評(píng)價(jià)調(diào)度方案的魯棒性表現(xiàn)，其基本思想是基于機(jī)器設(shè)備的歷史數(shù)據(jù)對(duì)設(shè)備故障導(dǎo)致的作業(yè)延時(shí)程度事先進(jìn)行推導(dǎo)預(yù)測(cè)，優(yōu)先增大最易受干擾作業(yè)的松弛時(shí)間，從而使生成的模板調(diào)度計(jì)劃對(duì)未來可能發(fā)生的設(shè)備故障與修復(fù)具有一定的吸收和應(yīng)對(duì)能力，使得在這些不確定事件干擾下的實(shí)際調(diào)度計(jì)劃相比于模板調(diào)度計(jì)劃而言的變動(dòng)性更小.換言之，生成的模板調(diào)度計(jì)劃在應(yīng)對(duì)不確定事件干擾時(shí)有較強(qiáng)的魯棒性，將具有這一性質(zhì)的調(diào)度計(jì)劃稱為魯棒調(diào)度計(jì)劃.考慮設(shè)備隨機(jī)故障這一不確定因素的前攝型調(diào)度研究已經(jīng)取得了一些成果.Wang等[10]在單機(jī)系統(tǒng)背景下假設(shè)工件實(shí)際加工時(shí)間受機(jī)器退化程度和資源投入量的影響，考慮機(jī)器隨機(jī)故障中斷工件加工的場(chǎng)景，并設(shè)計(jì)了一種基于支持向量回歸代理指標(biāo)的多目標(biāo)進(jìn)化算法，以決策工件的加工順序和資源投入量.趙嬋媛等[11]研究帶有隨機(jī)故障的流水線車間調(diào)度問題,以質(zhì)量魯棒性和解魯棒性的綜合指標(biāo)為優(yōu)化目標(biāo)，設(shè)計(jì)了內(nèi)、外兩層嵌套式優(yōu)化算法分別進(jìn)行緩沖時(shí)間和工件加工順序的決策.陸志強(qiáng)等[12]以離散流水車間為背景，通過預(yù)防性維護(hù)提高設(shè)備可靠性并減小設(shè)備故障對(duì)工件加工的影響，建立不確定性環(huán)境下的設(shè)備預(yù)防性維護(hù)及生產(chǎn)調(diào)度的集成優(yōu)化模型，設(shè)計(jì)了基于工件優(yōu)先列表、有效代理指標(biāo)、鄰域搜索機(jī)制的3階段啟發(fā)式算法，對(duì)模型進(jìn)行求解.從現(xiàn)有文獻(xiàn)可以看出，考慮設(shè)備隨機(jī)故障的前攝型調(diào)度多以單機(jī)系統(tǒng)和流水車間為研究背景，單機(jī)系統(tǒng)下只需考慮一臺(tái)機(jī)器設(shè)備的故障對(duì)工件加工過程產(chǎn)生的影響且工件間不存在緊前緊后關(guān)系；流水車間雖是多機(jī)系統(tǒng)，但通常假設(shè)一條流水線上的機(jī)器為同種類型且服從相同的故障概率分布.然而對(duì)飛機(jī)移動(dòng)裝配線而言，由于飛機(jī)對(duì)裝配精度的要求較高，使得一項(xiàng)裝配作業(yè)可能需要多種類型的多臺(tái)設(shè)備同時(shí)工作以輔助實(shí)現(xiàn)定位、調(diào)整、檢測(cè)等功能.實(shí)際裝配現(xiàn)場(chǎng)中，不同類型的設(shè)備往往具有不同的故障率，任何一類設(shè)備發(fā)生故障都會(huì)導(dǎo)致作業(yè)的中斷，再加上作業(yè)之間存在時(shí)序約束和資源約束，被中斷的作業(yè)可能通過網(wǎng)絡(luò)結(jié)構(gòu)直接或間接影響其他作業(yè)的開始時(shí)間.通過比較可以發(fā)現(xiàn)，以飛機(jī)移動(dòng)裝配線為背景研究設(shè)備隨機(jī)故障與修復(fù)影響下的前攝型調(diào)度問題復(fù)雜度更大，也正因?yàn)檠b配作業(yè)之間存在復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)傳遞關(guān)系，制定具有魯棒性的模板裝配計(jì)劃才更具有實(shí)際意義，不僅能使飛機(jī)裝配過程更穩(wěn)定高效，還能減少過程不穩(wěn)定帶來的經(jīng)濟(jì)損失.

本文考慮裝配現(xiàn)場(chǎng)自動(dòng)化機(jī)器設(shè)備的隨機(jī)故障以及修復(fù)對(duì)裝配作業(yè)計(jì)劃開始時(shí)間的影響，提出一種群體智能算法——依賴感知器的果蠅優(yōu)化算法，為生成魯棒模板調(diào)度計(jì)劃提供了一定的思路.

1 問題描述及數(shù)學(xué)模型

1.1 問題描述

考慮機(jī)器設(shè)備故障與修復(fù)的飛機(jī)移動(dòng)裝配線調(diào)度問題的假設(shè)與說明如下.

圖1 飛機(jī)移動(dòng)裝配線布局示意圖

(2) 將時(shí)間進(jìn)行離散化，記時(shí)間集合為D={t0,t1,…tT},tT為較大的正整數(shù)值.飛機(jī)移動(dòng)裝配線的生產(chǎn)模式是一種面向市場(chǎng)的拉動(dòng)式生產(chǎn)方式，每個(gè)工位都設(shè)有一個(gè)節(jié)拍時(shí)間ttac，ttac通常是項(xiàng)目經(jīng)理根據(jù)市場(chǎng)情況以及企業(yè)實(shí)際生產(chǎn)能力等綜合信息制定的，工位q中全部裝配作業(yè)的完工時(shí)間受到ttac的約束.

(3) 裝配線旁的物料存儲(chǔ)區(qū)保證了飛機(jī)移動(dòng)裝配現(xiàn)場(chǎng)的整齊有序，裝配作業(yè)所需的物料會(huì)根據(jù)作業(yè)計(jì)劃開始時(shí)間和配送提前期從中心倉(cāng)庫(kù)運(yùn)往線邊物料存儲(chǔ)區(qū)，以確保作業(yè)能夠準(zhǔn)時(shí)開始.當(dāng)裝配現(xiàn)場(chǎng)機(jī)器設(shè)備發(fā)生故障導(dǎo)致作業(yè)執(zhí)行中斷時(shí)，中斷作業(yè)必須在設(shè)備修復(fù)完成后重新執(zhí)行，則此中斷作業(yè)所需物料的占用線邊存儲(chǔ)空間的時(shí)間也會(huì)相應(yīng)延長(zhǎng).由于作業(yè)間存在時(shí)序約束，被中斷作業(yè)開始時(shí)間的延遲可能導(dǎo)致其他作業(yè)開始時(shí)間的推后，這些間接受到干擾的作業(yè)不管其物料是已經(jīng)運(yùn)送至現(xiàn)場(chǎng)還是存放在中心倉(cāng)庫(kù)，物料存儲(chǔ)時(shí)間的增加都將導(dǎo)致物料存儲(chǔ)成本的增加.假設(shè)任意作業(yè)j的單位時(shí)間線邊物料存儲(chǔ)成本和單位時(shí)間中心倉(cāng)庫(kù)物料存儲(chǔ)成本相同，記為αj，不同的作業(yè)根據(jù)其物料占用空間的大小有不同的αj.當(dāng)作業(yè)j實(shí)際的開始時(shí)間相比計(jì)劃開始時(shí)間每延遲一個(gè)單位，作業(yè)j的物料存儲(chǔ)成本將增加αj.因此，αj也可看作是作業(yè)j實(shí)際開始時(shí)間偏離計(jì)劃開始時(shí)間的單位懲罰值.特殊的，給虛擬作業(yè)n設(shè)置較大的懲罰權(quán)重αn作為完成工位q中所有裝配作業(yè)總時(shí)間超出節(jié)拍時(shí)間ttac時(shí)的單位懲罰值.

1.2 數(shù)學(xué)模型

構(gòu)建考慮機(jī)器設(shè)備故障與修復(fù)的飛機(jī)移動(dòng)裝配線調(diào)度問題的數(shù)學(xué)模型，此模型中的決策變量為0-1變量，即xji={0,1}, ?j∈J, ?ti∈D.如果作業(yè)j在時(shí)刻ti開始，則xji=1，否則xji=0.以最小化所有作業(yè)的懲罰值之和Z為目標(biāo)函數(shù)，建立的數(shù)學(xué)模型如下.

(1)

(2)

(3)

(4)

(5)

(6)

(7)

Xi～exp(ai) ?ki∈K

(8)

Yi～exp(bi) ?ki∈K

(9)

xji={0,1} ?j∈J, ?ti∈D

(10)

2 算法設(shè)計(jì)

Pan[13]于2011年提出果蠅優(yōu)化算法，并在優(yōu)化一般回歸神經(jīng)網(wǎng)絡(luò)時(shí)取得了比較好的收斂性能.相比起遺傳算法以及禁忌搜索算法等一些經(jīng)典算法，果蠅優(yōu)化算法更加新穎、簡(jiǎn)便和高效，但僅適用于值連續(xù)型的尋優(yōu)問題，而不太適合直接用于解決調(diào)度問題，因此在借鑒其優(yōu)化思想的基礎(chǔ)上重新設(shè)計(jì)了 “依賴感知器的果蠅優(yōu)化算法(PDFOA)”，用于解決所提問題.

自然界中果蠅覓食是一個(gè)依賴視覺、嗅覺、觸覺等感知器的過程，憑借群體協(xié)作從一個(gè)較為狹小的空間飛往更寬闊的空間尋找食物.所提的依賴感知器的果蠅優(yōu)化算法設(shè)計(jì)了窄域感知器搜索與寬域感知器搜索兩大重要模塊，前一模塊實(shí)則對(duì)應(yīng)了方案的局部搜索過程，通過嗅覺與視覺搜索操作的配合對(duì)鄰域解進(jìn)行高效評(píng)價(jià)和篩選；后一模塊借助“果蠅知識(shí)記憶庫(kù)”提高算法的全局搜索能力.

2.1 代理指標(biāo)的設(shè)計(jì)

目標(biāo)函數(shù)Z是基于Nsce個(gè)場(chǎng)景來評(píng)價(jià)調(diào)度計(jì)劃的優(yōu)劣的，基于場(chǎng)景的評(píng)價(jià)方式具有動(dòng)態(tài)性，因此需要借助抽樣仿真，但直接將抽樣仿真嵌入算法來評(píng)價(jià)每個(gè)解的好壞會(huì)大大增加該算法的迭代尋優(yōu)消耗時(shí)長(zhǎng).相比較而言，設(shè)計(jì)一個(gè)靜態(tài)的代理指標(biāo)評(píng)價(jià)中間方案的優(yōu)劣更加簡(jiǎn)便而且快速.因此，只有在對(duì)比實(shí)驗(yàn)部分才涉及抽樣仿真，算法主體部分不采用抽樣仿真的方式.基于Lambrechts等[14]設(shè)計(jì)的代理指標(biāo)，設(shè)計(jì)與本文算法配套的代理指標(biāo)如下式所示：

(11)

(12)

2.2 果蠅種群初始化

圖2 編碼以及解碼示意圖

2.3 窄域感知器搜索模塊

(13)

(14)

(15)

圖3 嗅覺搜索操作優(yōu)化機(jī)制

對(duì)果蠅進(jìn)行窄域嗅覺搜索操作的完整步驟如下：

步驟1初始化感知器開關(guān)參數(shù)θ1=1,θ2=0，窄域嗅覺搜索的次數(shù)count=0.

圖4 窄域視覺搜索流程圖

圖4虛線框中的具體步驟如下：

2.4 寬域感知器搜索模塊

3 數(shù)值實(shí)驗(yàn)

3.1 實(shí)例參數(shù)和實(shí)驗(yàn)平臺(tái)

圖5 仿真實(shí)驗(yàn)調(diào)度結(jié)果圖

在進(jìn)行對(duì)比實(shí)驗(yàn)之前，先通過預(yù)實(shí)驗(yàn)收集了 1 200 個(gè)(Z,ZA)樣本對(duì)，每30對(duì)計(jì)算一個(gè)Pearson相關(guān)系數(shù)ξ，Pearson相關(guān)系數(shù)箱型圖如圖6所示.

圖6 皮爾遜相關(guān)系數(shù)箱型圖

由圖6可知，40個(gè)Pearson相關(guān)系數(shù)的均值為-0.61，且其中75%的值分布在區(qū)間[-0.79,-0.55]中，進(jìn)一步說明了ZA與Z之間有較強(qiáng)的負(fù)相關(guān)性，驗(yàn)證了代理指標(biāo)設(shè)置的合理性.

3.2 不同作業(yè)規(guī)模仿真結(jié)果與禁忌搜索算法結(jié)果的對(duì)比

將PDFOA與文獻(xiàn)[14]中的禁忌搜索(TS)算法進(jìn)行對(duì)比，對(duì)每個(gè)算例獲得的模板計(jì)劃取Nsce=100組完整的執(zhí)行場(chǎng)景，并計(jì)算此算例的目標(biāo)函數(shù)值Z.同一作業(yè)規(guī)模的算例進(jìn)行5次實(shí)驗(yàn)，每次實(shí)驗(yàn)計(jì)算這一規(guī)模下10個(gè)算例所獲得的Z平均值，并統(tǒng)計(jì)算法所用的平均時(shí)間進(jìn)行對(duì)比.

3.2.1小規(guī)模作業(yè)結(jié)果對(duì)比 小規(guī)模作業(yè)下的實(shí)驗(yàn)結(jié)果如表1所示，其中：tal為各組實(shí)驗(yàn)中對(duì)應(yīng)算法的運(yùn)行時(shí)間; Ave為均值；R為4個(gè)作業(yè)規(guī)模下(30、60、90、120)，5組實(shí)驗(yàn)中由PDFOA獲得的優(yōu)勝比例值，該值由每組實(shí)驗(yàn)中PDFOA所得Z值更小的算例數(shù)除以本組實(shí)驗(yàn)總算例數(shù)獲得；GAP為由PDFOA與TS算法計(jì)算所得目標(biāo)值的差值百分比，GAP值為正表示PDFOA所得結(jié)果更優(yōu)，且值越大表示由PDFOA所得的結(jié)果越好.由表1可知，小規(guī)模作業(yè)下PDFOA的優(yōu)勢(shì)并不明顯，5組實(shí)驗(yàn)中有2組實(shí)驗(yàn)的GAP值為負(fù)數(shù)，平均GAP只有1.67%.

表1 小規(guī)模作業(yè)實(shí)驗(yàn)結(jié)果對(duì)比

3.2.2大規(guī)模作業(yè)實(shí)驗(yàn)結(jié)果對(duì)比 在作業(yè)規(guī)模為60,90和120的情況下，PDFOA相比TS算法在時(shí)間和結(jié)果上的優(yōu)勢(shì)都較為明顯，實(shí)驗(yàn)結(jié)果如表2所示.由表2可知，各作業(yè)規(guī)模下的5組實(shí)驗(yàn)中均沒有出現(xiàn)GAP為負(fù)數(shù)的情況.隨著作業(yè)規(guī)模的增大，GAP值也有變大的趨勢(shì)，進(jìn)一步體現(xiàn)出在大規(guī)模作業(yè)下PDFOA能夠在較短的時(shí)間內(nèi)獲得魯棒性較高的模板計(jì)劃.

表2 大規(guī)模任務(wù)實(shí)驗(yàn)結(jié)果對(duì)比

大規(guī)模作業(yè)算例下，PDFOA較有優(yōu)勢(shì)的原因可能有以下兩點(diǎn)：① PDFOA在一定程度上彌補(bǔ)了文獻(xiàn)[14]中代理指標(biāo)的不足，文獻(xiàn)[14]中的代理指標(biāo)使得網(wǎng)絡(luò)結(jié)構(gòu)圖中越靠前的作業(yè)獲得緩沖時(shí)間的可能性越大，在作業(yè)數(shù)目較大時(shí)其合理性有所欠缺.PDFOA將緩沖時(shí)間優(yōu)先分配給松弛時(shí)間最小且最可能受其他作業(yè)干擾的作業(yè)，目的是減小這些作業(yè)干擾其他作業(yè)的可能性. ② TS算法通過交換任意兩個(gè)滿足時(shí)序關(guān)系的作業(yè)位置以及改變緩沖時(shí)間列表中作業(yè)的緩沖時(shí)間值進(jìn)行鄰域搜索，禁忌搜索列表的設(shè)置在一定程度上避免了重復(fù)搜索，但是隨著作業(yè)規(guī)模的增大、可交換位置的作業(yè)對(duì)變多，禁忌列表起到的作用變小并且搜索方向也更難控制，因此很難在較短的時(shí)間內(nèi)保證解的質(zhì)量.

以上實(shí)驗(yàn)通過比較GAP均值的方法驗(yàn)證所提算法的有效性，但弊端在于個(gè)別表現(xiàn)特別優(yōu)異的算例或?qū)嶒?yàn)組會(huì)對(duì)整體均值產(chǎn)生影響進(jìn)而干擾判斷.而表1和表2中，不同作業(yè)規(guī)模下的優(yōu)勝比例基本都大于0.6，進(jìn)一步說明了PDFOA的有效性.

3.2.3PDFOA與TS算法的敏感度分析 實(shí)際飛機(jī)制造企業(yè)的生產(chǎn)節(jié)拍由生產(chǎn)計(jì)劃部門根據(jù)市場(chǎng)信息制定，市場(chǎng)信息的變動(dòng)使得工位的節(jié)拍發(fā)生改變.考慮到這種實(shí)際情況，取出一個(gè)作業(yè)規(guī)模為30且tcpm=38的算例，通過改變比例值γ給此算例設(shè)置不同的ttac.實(shí)驗(yàn)設(shè)置為γ∈[1.2,2],每隔步長(zhǎng)0.1取一個(gè)新的γ，則ttac的取值可通過計(jì)算γtcpm并四舍五入取整獲得，在僅改變ttac不改變此算例其他信息的條件下進(jìn)行對(duì)比實(shí)驗(yàn).

每個(gè)γ下對(duì)此算例分別采用PDFOA和TS算法進(jìn)行3次實(shí)驗(yàn)，如圖7所示.其中：EX1、EX2、EX3分別代表實(shí)驗(yàn)1、2、3.由圖7可以看出，當(dāng)γ≤1.5時(shí)，3組實(shí)驗(yàn)中GAP為負(fù)數(shù)的情況較多，這說明了TS算法更有利于解決問題；當(dāng)γ>1.5時(shí)，GAP基本都為正數(shù)，說明PDFOA優(yōu)勢(shì)更明顯.因此，解決實(shí)際問題時(shí)可根據(jù)實(shí)際情況選擇適用的算法.

圖7 單個(gè)算例在不同γ下的表現(xiàn)

3.3 不同作業(yè)規(guī)模仿真結(jié)果與其他智能算法結(jié)果的對(duì)比

3.3.1對(duì)比算法參數(shù)說明及不同評(píng)價(jià)指標(biāo)計(jì)算方式下的算法對(duì)比 考慮到PDFOA借鑒了自然生物的覓食規(guī)則，與啟發(fā)式算法中借鑒生物進(jìn)化規(guī)則的遺傳算法以及鳥類飛行規(guī)則的粒子群算法具有較高的相似性，為了進(jìn)一步說明PDFOA的有效性，將 PDFOA 與基本遺傳算法(GA)以及文獻(xiàn)[17]提出的免疫粒子群優(yōu)化(IPSO)算法進(jìn)行對(duì)比.在用于對(duì)比的GA算法中加入了精英保留策略，交叉操作以0.7的交叉概率從表現(xiàn)優(yōu)良的染色體群體中選取染色體進(jìn)行交叉，變異操作以0.6的變異概率對(duì)不存在任何緊前緊后約束關(guān)系的作業(yè)基因位進(jìn)行交換.文獻(xiàn)[17]以裝配作業(yè)車間為研究背景進(jìn)行調(diào)度問題研究，所提出的IPSO算法是免疫算法與粒子群算法的結(jié)合.

考慮到該篇文獻(xiàn)與本文的研究背景和領(lǐng)域較為相似，因此本部分實(shí)驗(yàn)中選取文獻(xiàn)[17]中的IPSO算法模型及其相關(guān)參數(shù)進(jìn)行對(duì)比.此外，兩個(gè)對(duì)比算法中的群體數(shù)目、迭代數(shù)目等參數(shù)均與PDFOA保持一致.還需說明的是，在迭代過程中直接采用抽樣仿真的方式計(jì)算評(píng)價(jià)指標(biāo)對(duì)時(shí)間的消耗非常大且實(shí)用性欠佳，因此只從4種作業(yè)規(guī)模的算例中各抽取了1個(gè)算例進(jìn)行對(duì)比，所獲得的對(duì)比結(jié)果如表3所示.其中：IPSO和GA算法在迭代過程中的評(píng)價(jià)指標(biāo)是取抽樣場(chǎng)景數(shù)為5的情況下仿真所得的結(jié)果；PDOFA在迭代過程中的評(píng)價(jià)指標(biāo)采用的是代理指標(biāo).由表3可知，IPSO和GA算法中耗時(shí)最少的算例分別消耗了 16 723.95 s (4.645 h)、17 010.34 s(4.725 h)，而采用代理指標(biāo)的PDFOA 僅用21.483 s.由此可見， GA和IPSO算法在消耗較多運(yùn)算時(shí)間的情況下結(jié)果卻不如PDFOA好.從理論上而言，迭代過程中采用抽樣仿真的形式評(píng)價(jià)解的優(yōu)劣時(shí)，抽取的場(chǎng)景數(shù)目越多對(duì)解的評(píng)價(jià)越準(zhǔn)確，最終經(jīng)過Nsce=100次模擬仿真后獲得的目標(biāo)函數(shù)Z也會(huì)越好.但是，從表3不難看出，該方法下GA和 IPSO 算法的運(yùn)算時(shí)間已經(jīng)較長(zhǎng)，進(jìn)一步增加迭代過程中的抽樣場(chǎng)景數(shù)目將使運(yùn)算時(shí)間更長(zhǎng)，從而進(jìn)一步削弱算法的使用價(jià)值.相比較而言，設(shè)置代理指標(biāo)大大節(jié)約了運(yùn)算時(shí)間，在為裝配現(xiàn)場(chǎng)快速提供模板調(diào)度計(jì)劃方面具有優(yōu)勢(shì).

3.3.2不同作業(yè)規(guī)模下的仿真實(shí)驗(yàn) 為了更貼近實(shí)際需求并能更公平地對(duì)比各算法的性能，以下對(duì)比實(shí)驗(yàn)中的GA和IPSO算法在迭代過程中均采用本文設(shè)計(jì)的代理指標(biāo)ZA對(duì)迭代群體中解的優(yōu)劣程度進(jìn)行評(píng)價(jià)，種群規(guī)模以及迭代數(shù)目均與PDFOA保持一致.選取作業(yè)規(guī)模為120的一個(gè)算例進(jìn)行預(yù)實(shí)驗(yàn)后，3種算法在50次迭代中的最佳代理指標(biāo)值的變化及收斂過程如圖8所示.其中:Inum為迭代數(shù)序列；ZA為代理指標(biāo)值.由圖8可知，IPSO算法收斂得較快，而PDFOA收斂得相對(duì)較慢，從代理指標(biāo)最優(yōu)解來看，PDFOA最終的收斂值優(yōu)于GA以及 IPSO 算法.正式實(shí)驗(yàn)中，每個(gè)算例通過算法求解獲得的調(diào)度計(jì)劃在Nsce=100組完整的仿真場(chǎng)景中進(jìn)行仿真，并最終求出此算例的目標(biāo)函數(shù)值Z.在30、60、90和120這4種作業(yè)規(guī)模下分別進(jìn)行5組實(shí)驗(yàn)，每組實(shí)驗(yàn)取10個(gè)算例以獲得目標(biāo)函數(shù)Z的均值，計(jì)算結(jié)果如表4所示.其中，GAP1和GAP2分別為PDFOA與GA算法以及PDFOA與IPSO算法所得結(jié)果的GAP值，當(dāng)GAP1或GAP2為正數(shù)時(shí)，其GAP值越大表示PDFOA相比GA或IPSO算法所得的結(jié)果越優(yōu)；優(yōu)勝比例R1和R2為各規(guī)模作業(yè)下，每組實(shí)驗(yàn)中PDFOA所得的仿真結(jié)果比GA或IPSO算法結(jié)果更優(yōu)的算例數(shù)占該組實(shí)驗(yàn)總算例數(shù)的比例.

表4 PDFOA與GA、IPSO算法在不同作業(yè)規(guī)模算例下的對(duì)比結(jié)果

圖8 3種算法下代理指標(biāo)的收斂過程

與3.2節(jié)中的實(shí)驗(yàn)結(jié)果綜合來看，依賴感知器的PDFOA在性能總體上優(yōu)于TS算法、GA算法和IPOS算法的，TS算法在解決本文問題時(shí)比GA和IPSO算法更優(yōu)一些，但TS算法消耗的時(shí)間遠(yuǎn)遠(yuǎn)大于GA和IPSO算法，PDFOA在運(yùn)算時(shí)間上雖然也多于GA和IPSO算法，但相比于TS算法的運(yùn)行時(shí)間已經(jīng)有大幅下降且PDFOA在最終的仿真結(jié)果上表現(xiàn)比較優(yōu)異.

4 結(jié)論

(1) 以飛機(jī)移動(dòng)裝配線為實(shí)際應(yīng)用背景，考慮設(shè)備的故障與修復(fù)對(duì)飛機(jī)裝配作業(yè)計(jì)劃穩(wěn)定性可能產(chǎn)生的影響，為生成具有魯棒性的模板調(diào)度計(jì)劃提供了思路和方法.

(2) 借鑒了果蠅優(yōu)化算法簡(jiǎn)便高效的思想，將其靈活運(yùn)用至調(diào)度類問題，設(shè)計(jì)了更易理解和操作的鄰域搜索機(jī)制.將設(shè)計(jì)的依賴感知器的果蠅優(yōu)化算法與禁忌搜索算法、遺傳算法和免疫粒子群算法在不同作業(yè)規(guī)模的算例下進(jìn)行了仿真對(duì)比，驗(yàn)證了所提算法的有效性.

(3) 后續(xù)將基于自動(dòng)化設(shè)備的狀態(tài)進(jìn)行調(diào)度，前端與機(jī)器學(xué)習(xí)結(jié)合實(shí)現(xiàn)數(shù)據(jù)驅(qū)動(dòng).