基于預(yù)測機制的裝配作業(yè)重調(diào)度問題建模優(yōu)化

陸志強，方 佳

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

在實際飛機移動裝配線中，裝配作業(yè)在裝配調(diào)度計劃的指導(dǎo)下依次執(zhí)行。飛機移動裝配線調(diào)度問題可抽象成資源受限項目調(diào)度問題（resourceconstrained project scheduling problem），近幾年的相關(guān)研究大多圍繞不確定環(huán)境展開，Panda等［1］和Liu等［2］均以制造業(yè)為背景研究作業(yè)時長變動、物料送達不準(zhǔn)時等不確定因素影響下的調(diào)度問題。對于飛機移動裝配這種單件大型復(fù)雜產(chǎn)品的裝配項目而言，因裝配質(zhì)量不合規(guī)格增加的修復(fù)操作就是不可忽視的不確定因素之一，它既可能導(dǎo)致后續(xù)作業(yè)延遲開始也可能造成裝配人員安排、資源配送和使用計劃發(fā)生伴隨性變動，裝配計劃執(zhí)行過程不穩(wěn)定性增加的同時企業(yè)也將產(chǎn)生額外的計劃調(diào)整成本。本文從高效性和經(jīng)濟性出發(fā)，研究飛機移動裝配線中作業(yè)因為質(zhì)量原因被增加修復(fù)操作這一環(huán)境下的重調(diào)度問題。

隨著飛機移動裝配線越來越多地采用智能設(shè)備輔助裝配，設(shè)備性能衰退逐漸成為影響作業(yè)裝配質(zhì)量進而干擾裝配計劃的要因。Kang等［3］和Liu等［4］都研究制造系統(tǒng)中機器設(shè)備“硬故障”（設(shè)備徹底不可運行）中斷作業(yè)這一環(huán)境下的調(diào)度問題，相比設(shè)備“硬故障”，飛機移動裝配線中發(fā)生設(shè)備“軟故障”的頻繁更高。與Shahkarami等［5］分析的光纖網(wǎng)絡(luò)軟故障（soft-failure）類似，復(fù)雜裝配系統(tǒng)中機器設(shè)備發(fā)生“軟故障”時雖能運行，但卻會導(dǎo)致裝配質(zhì)量問題頻繁出現(xiàn)并演變?yōu)轭l繁的作業(yè)修復(fù)。本文將機器設(shè)備中工裝夾具、刀具、夾具與刀具構(gòu)成的部件定義為質(zhì)量相關(guān)部件，它們的磨損與退化是促使設(shè)備發(fā)生“軟故障”的主要因素。本文通過收集設(shè)備質(zhì)量相關(guān)部件的衰退以及作業(yè)質(zhì)量特性偏差歷史數(shù)據(jù)構(gòu)建前端的作業(yè)質(zhì)量預(yù)測模型。

現(xiàn)有解決不確定環(huán)境下調(diào)度問題的方法可以分為前攝調(diào)度法和反應(yīng)調(diào)度法。多數(shù)研究前攝調(diào)度方法的文獻通過數(shù)學(xué)公式推導(dǎo)出可插入調(diào)度計劃中的緩沖時間值或資源投入量來應(yīng)對干擾。前攝型調(diào)度研究成果中，Cui等［6］針對流水車間故障不確定環(huán)境下的生產(chǎn)調(diào)度與維護計劃聯(lián)合優(yōu)化問題，提出了雙層循環(huán)算法。Tan等［7］將緊急救援問題抽象成了資源受限項目調(diào)度問題并設(shè)計了一種混合型遺傳-禁忌算法。Bruni等［8］研究了作業(yè)執(zhí)行時間不確定的資源受限項目調(diào)度問題并提出了自適應(yīng)的魯棒優(yōu)化模型對資源分配作出決策。在反應(yīng)調(diào)度方法的研究中，Qiao等［9］針對半導(dǎo)體制造中的突發(fā)事件提出了包含一個規(guī)則和一個調(diào)度程序的局部快速修復(fù)型重調(diào)度算法。Creemers等［10］研究作業(yè)執(zhí)行時間隨機變動的反應(yīng)型調(diào)度問題并采用馬爾科夫鏈進行動態(tài)優(yōu)化決策。Rahmani等［11］針對動態(tài)柔性車間中未預(yù)期的新工件到達造成干擾的問題，設(shè)定雙優(yōu)化目標(biāo)并提出了一種變鄰域算法生成較穩(wěn)定的重調(diào)度方案。

如今智能制造正通過促進信息通信技術(shù)與制造過程的整合來重塑制造業(yè)，數(shù)據(jù)驅(qū)動式的決策方式對制造業(yè)的未來具有重要意義。本文基于這種思想提出了指導(dǎo)現(xiàn)場實際作業(yè)裝配的閉環(huán)框架，該框架的前端利用預(yù)測模型對作業(yè)質(zhì)量進行預(yù)測，后端基于預(yù)測結(jié)果構(gòu)建重調(diào)度模型并運用本文提出的改進型免疫算法調(diào)整作業(yè)裝配計劃。

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

1.1 問題描述

以飛機移動裝配線為背景提出的預(yù)測-重調(diào)度閉環(huán)框架的相關(guān)假設(shè)與說明如下，其中后端作業(yè)重調(diào)度模型的內(nèi)容在1.2節(jié)詳細(xì)描述。

（1）飛機移動裝配線當(dāng)前工位的裝配作業(yè)集合記作J={1，2，3，...，j，...，N}，其中1和N是虛擬作業(yè)；作業(yè)j∈J有確定的裝配時長tdj和對第k∈K種資源的需求量r jk，K為資源集合；任意作業(yè)j受到時序約束必須在其全部緊前作業(yè)完成后才能開始；此外，受有限資源量的約束，任意時刻任意種類的資源總需求量不能超過該類資源的供應(yīng)量R k。

（2）裝配作業(yè)所需機器設(shè)備中共包含ρ類質(zhì)量相關(guān)部件，類型集合記作Q={1，2，3，...ρ}。作業(yè)j所需第q∈Q類質(zhì)量相關(guān)部件的衰退情況用夾具長度衰退量l jq、夾具直徑衰退量c jq、夾具張緊力衰退量s jq和刀具磨損量g jq構(gòu)成的向量D jq=(l jq，c jq，s jq，g jq)T表示，D j是維度為4O j的單列向量，其中O j為作業(yè)j所需質(zhì)量相關(guān)部件類型總數(shù)。Wang等［12］針對衰退型生產(chǎn)系統(tǒng)研究生產(chǎn)與維護聯(lián)合優(yōu)化問題時采用gamma過程來描述生產(chǎn)系統(tǒng)退化；Lu等［13］研究串并行多階段制造系統(tǒng)機會維護問題時，考慮到設(shè)備中質(zhì)量相關(guān)部件（QRCs）衰退過程具有隨機獨立、非負(fù)增量的性質(zhì)故采用gamma過程對QRCs衰退進行建模，同理本文假設(shè)作業(yè)所需設(shè)備中質(zhì)量相關(guān)部件的衰退過程服從gamma過程。任意作業(yè)j的初始衰退向量記作Dojq=(lojq，cojq，sojq，gojq)T，Dojq中每個維度都服從正態(tài)分布。

（3）為保證飛機裝配的質(zhì)量，作業(yè)j完成后必須接受n個質(zhì)量特性偏差檢測，檢測時間忽略不計，結(jié)果 記 作X j=(b x1，b y1，b z1，b x2，b y2，b z2...b x n，b y n，b z n)T，b x i、b y i和b z i（i∈[1，n]）是作業(yè)j的第i個質(zhì)量特性偏差值在x、y和z3個方向上的分量。若X j各維度均落在標(biāo)準(zhǔn)規(guī)格范圍內(nèi)可繼續(xù)執(zhí)行后續(xù)作業(yè)；否則需對作業(yè)j添加屬性為tdjr=?tdj和r jrk=?r jk的修復(fù)作業(yè)jr，jr未完成時作業(yè)j所有緊后作業(yè)都無法執(zhí)行。

假設(shè)X j的各維度b i∈X j，i=[1，3n]都服從正態(tài)分布且裝配過程對各維度正態(tài)分布的影響可明顯體現(xiàn)在均值上，忽略各維度方差σji的細(xì)微波動，作業(yè)最多進行一次修復(fù)便可質(zhì)量達標(biāo)。裝配現(xiàn)場的數(shù)據(jù)采集系統(tǒng)每隔一定周期進行一次質(zhì)量相關(guān)部件衰退數(shù)據(jù)以及質(zhì)量特性偏差數(shù)據(jù)的更新與存儲。

（4）作業(yè)j的裝配質(zhì)量有3個主要影響因素：該作業(yè)所需設(shè)備中質(zhì)量相關(guān)部件衰退情況、關(guān)鍵緊前作業(yè)jb的質(zhì)量特性偏差和j裝配中的噪聲量。假設(shè)任意作業(yè)j有且僅有一個關(guān)鍵緊前作業(yè)jb對X j有關(guān)鍵影響。當(dāng)前工位內(nèi)的全部關(guān)鍵緊前作業(yè)構(gòu)成激發(fā)預(yù)測機制的作業(yè)列表Jb，時間驅(qū)動方式下只要有jb∈Jb完成且質(zhì)檢合格將直接觸發(fā)后續(xù)作業(yè)質(zhì)量特性偏差的預(yù)測機制，預(yù)測機制運行時間忽略不計；質(zhì)檢不通過則直接采用右移策略插入修復(fù)作業(yè)計劃形成新的調(diào)度計劃指導(dǎo)裝配，此部分不是本文重點故不再贅述。

（5）假設(shè)裝配現(xiàn)場已提供經(jīng)優(yōu)化的預(yù)防性維護閾值δ=50%，作業(yè)質(zhì)量合格概率預(yù)測值相比標(biāo)準(zhǔn)值下降超過δ時將根據(jù)更換零衰退部件的成本與質(zhì)量合格概率改善程度之比確定性價比最高的維護方式，維護時長為tm，維護結(jié)束后相應(yīng)作業(yè)才能開始裝配。

（6）離散化時間集合記為T={0，1，2，3...T}，裝配項目啟動前由遺傳算法優(yōu)化得到初始調(diào)度計劃Fo，基于Fo經(jīng)調(diào)整形成的新調(diào)度計劃Fn又可視作下一次計劃調(diào)整的初始調(diào)度計劃。

1.2 后端作業(yè)重調(diào)度符號與數(shù)學(xué)模型

（1）時間相關(guān)符號。T：離散化時刻集合；tm：預(yù)防性維護持續(xù)時長；tp：預(yù)測機制觸發(fā)時刻即重調(diào)度時刻，tp∈T。

（2）資源相關(guān)符合。K：有限資源集合；R k：第k類資源的供應(yīng)量。

（3）作業(yè)相關(guān)符號。J：工位內(nèi)裝配作業(yè)集合；j：J中的任意作業(yè)；jr：j對應(yīng)的修復(fù)作業(yè)；tdj：作業(yè)j的執(zhí)行時長；r jk：作業(yè)j對第k類資源的需求量；w j：作業(yè)j實際開始時間偏離初始計劃開始時間每單位時間所付成本即作業(yè)的權(quán)重；W j：作業(yè)j所有緊后作業(yè)單位時間偏差成本累積和。

（4）調(diào)度計劃相關(guān)符號。Fo（Fn）：初始（新）調(diào)度計劃方案；tosj（tnsj）：作業(yè)j在初始（新）調(diào)度計劃中的開始時刻。

（5）重調(diào)度相關(guān)符號。Jstp：tp時刻已開始作業(yè)列表；Jntp：tp時刻未開始作業(yè)列表；Jmtp：tp時刻接受質(zhì)量相關(guān)部件維護的作業(yè)列表；Jptp：tp時刻確定要進行預(yù)調(diào)度的修復(fù)作業(yè)列表；Jftp：tp時刻Jntp中未進行修復(fù)預(yù)調(diào)度的作業(yè)列表；J tp：tp時刻確定的重調(diào)度作業(yè)列表；JAj（JBj）：預(yù)調(diào)度作業(yè)確定后，作業(yè)j更新后的全部緊后（緊前）作業(yè)集合。

（6）決策變量符號。x jt：0-1變量，作業(yè)j在t時刻開始取1，否則取0。

（7）數(shù)學(xué)模型為

式（1）是優(yōu)化目標(biāo)。式（5）tcj是重調(diào)度列表中未進行修復(fù)預(yù)調(diào)度的作業(yè)在新調(diào)度計劃中的松弛時間，tcj等于作業(yè)j結(jié)束時刻到最早緊后開始時刻這段時區(qū)中滿足資源約束的最大連續(xù)時段數(shù)，貢獻時段tfj取tcj和tdj間的較小值，其含義是一旦j產(chǎn)生了預(yù)期外的修復(fù)需求且裝配現(xiàn)場實施右移策略時作業(yè)j所有緊后作業(yè)都能少推遲的時間值；式（4）W j是作業(yè)j所有緊后作業(yè)單位偏差時間需付成本之和；基于式（4）、（5）的式（2）衡量新調(diào)度計劃中未進行修復(fù)預(yù)調(diào)度的作業(yè)應(yīng)對質(zhì)量修復(fù)干擾時能節(jié)約的成本可視為作出的貢獻，而式（3）衡量新調(diào)度計劃相比初始調(diào)度計劃因作業(yè)延遲開始給企業(yè)造成的成本支出，因此由式（2）與式（3）的差值構(gòu)成的優(yōu)化目標(biāo)函數(shù)（1）的含義是最大化新調(diào)度計劃對企業(yè)的總貢獻值。

式（6）-（11）給出了新調(diào)度計劃（Fn）與初始調(diào)度計劃（Fo）間的映射與約束關(guān)系：Fn是在Fo基礎(chǔ)上運用預(yù)測和算法得到，但Fn與Fo的對應(yīng)關(guān)系不存在顯性表達故直接記作式（6）的β；式（7）-（9）給出了Fn中作業(yè)開始時間與決策變量的關(guān)系式，同時約束了任意作業(yè)只能有一個開始時刻；式（10），（11）則進一步約束了重調(diào)度時刻已開始作業(yè)的開始時間應(yīng)與Fo保持一致，重調(diào)度作業(yè)在Fn中的開始時間不得早于Fo。

最后，式（12）-（15）從時序及資源方面給出了約束：式（12）-（14）從裝配工藝時序、裝配與修復(fù)時序及維護與裝配時序角度約束了作業(yè)的開始時間；式（15）表示任意時刻作業(yè)的資源需求總量不能超過資源的總供應(yīng)量。

2 整體框架與算法設(shè)計

圖1是本文構(gòu)建的實際應(yīng)用閉環(huán)框架。前端離線訓(xùn)練部分主要完成數(shù)據(jù)的提取、處理和作業(yè)質(zhì)量特性偏差預(yù)測模型的訓(xùn)練；后端在線預(yù)測部分則主要根據(jù)裝配線實際數(shù)據(jù)進行預(yù)測并基于預(yù)測結(jié)果實現(xiàn)裝配計劃重調(diào)度。2.1節(jié)、2.3節(jié)和2.2節(jié)分別對前端模型訓(xùn)練、后端重調(diào)度算法以及兩者的過渡部分進行了闡述，研究重點仍集中在后端重調(diào)度算法的有效性和整體框架的可行性分析上。

圖1 實際應(yīng)用前后端整體框架Fig.1 Front-end overall framework of actual application

2.1 前端支持向量回歸（SVR）模型訓(xùn)練

2.1.1 生成訓(xùn)練樣本

采用文獻［14］基于質(zhì)量偏差流理論的狀態(tài)空間模型即公式（16）模擬各作業(yè)質(zhì)量特性偏差的歷史數(shù)據(jù)：

其中，Μjjb是j的關(guān)鍵緊前作業(yè)jb與作業(yè)j間的質(zhì)量特性偏差傳遞矩陣，H j是質(zhì)量相關(guān)部件衰退對作業(yè)j質(zhì)量特性偏差影響的傳遞矩陣，Y j是噪聲矩陣。M jjb、H j和Y j采用文獻［14］中的數(shù)據(jù)?？紤]到實際裝配現(xiàn)場質(zhì)量相關(guān)部件衰退及作業(yè)質(zhì)量特性偏差在短時間內(nèi)變化較小故構(gòu)建訓(xùn)練樣本時以數(shù)據(jù)采集系統(tǒng)數(shù)據(jù)更新周期為取樣周期，作業(yè)j的訓(xùn)練樣本如（17）矩陣S j所示，S j∈Rs1×s2，其中s2是樣本總數(shù)。

S j中每個樣本的輸入矢量I j∈R(3n+4O j)×1由各取樣周期內(nèi)jb的質(zhì)量特性偏差均值Xmjb以及作業(yè)j所需設(shè)備的質(zhì)量相關(guān)部件衰退均值Dmj構(gòu)成，輸出矢量E j∈R3n×1等于作業(yè)j在周期內(nèi)的質(zhì)量特性偏差均值Xmj。

2.1.2 訓(xùn)練支持向量回歸模型

對作業(yè)質(zhì)量特性偏差的每一維都建立支持向量回歸（SVR）模型，SVR可通過映射函數(shù)將非線性問題成功轉(zhuǎn)換為式（18）中高維特征空間的線性回歸模型，利用結(jié)構(gòu)風(fēng)險最小化原則和對偶問題最終可將預(yù)測值優(yōu)化問題表示為（19）［15］：

2.2 作業(yè)質(zhì)量預(yù)測機制的激發(fā)與結(jié)果輸出

基于2.1節(jié)訓(xùn)練的質(zhì)量特性偏差預(yù)測模型，時間驅(qū)動下質(zhì)量預(yù)測機制的激發(fā)與結(jié)果輸出流程如下：

步驟1:作業(yè)jb∈Jb按計劃在tp時刻裝配完成并接受質(zhì)檢得到質(zhì)量特性偏差X jb，考慮到一個數(shù)據(jù)采集周期內(nèi)數(shù)據(jù)都十分接近，故可近似將該值視為當(dāng)前數(shù)據(jù)采集周期內(nèi)的均值Xmjb。

步驟2:確定jb的關(guān)鍵緊后作業(yè)列表Jh。遍歷Jh，檢測jh∈Jh所需設(shè)備中質(zhì)量相關(guān)部件的衰退量并基于歷史衰退過程預(yù)估jh完成時的衰退均值Dmjh，將Xmjb和Dmjh構(gòu)成矢量Ιjh輸入作業(yè)jh的預(yù)測模型并最終輸出jh的質(zhì)量特性偏差均值預(yù)測值Xmjh。由Xmjh以及質(zhì)量特性偏差的上下規(guī)格矢量Xujh和Xdjh通過式（20）可算出jh的合格概率預(yù)測值PEjh，若達到預(yù)防性維護閾值則將jh納入Jmtp。

步驟3:tp時刻未開始作業(yè)列表Jntp中未被預(yù)測的作業(yè)質(zhì)量合格概率默認(rèn)為歷史概率，被預(yù)測的作業(yè)質(zhì)量合格概率若是Jntp中的瓶頸，其修復(fù)作業(yè)將被納入預(yù)調(diào)度列表Jptp，Jptp中作業(yè)不可多于Nu。

步驟4:重調(diào)度作業(yè)列表J tp由Jntp和Jptp構(gòu)成，進一步調(diào)用2.3節(jié)算法生成裝配作業(yè)重調(diào)度計劃。

2.3 改進型免疫算法

免疫算法是一種模仿生物體免疫學(xué)機理的較為成熟的啟發(fā)式算法，本文所提改進型免疫算法（I-IA）重點在種群初始化、交叉變異和種群更新方面進行了改進。

2.3.1 初始種群的生成

為在增加抗體多樣性的同時降低轉(zhuǎn)變?yōu)橥耆S機搜索的風(fēng)險，初始種群L中P條抗體由2種不同的生成方式ξ1(?)和ξ2(?)按照比例a1和a2構(gòu)成，記作式（21）：

圖2給出了局部作業(yè)網(wǎng)絡(luò)結(jié)構(gòu)和運用2種方式生成的抗體編碼示例。第1行示意第1種方式，在不違背緊前緊后關(guān)系約束的前提下隨機生成可行調(diào)度編碼即抗體；第2行示意第2種方式，編碼在不違背作業(yè)時序約束的同時被劃分為具有一定性質(zhì)的不同模塊，示例被劃分的［1］、［3 4］、［8 2 5 7］和［9］這4個模塊相互之間位置不可換，但任意一個模塊內(nèi)部的作業(yè)相互之間不存在緊前緊后關(guān)系，因此可隨機交換位置。

圖2 抗體生成方式示例Fig.2 Example of antibody generation methods

當(dāng)有修復(fù)作業(yè)被預(yù)調(diào)度時只需增加修復(fù)作業(yè)與原作業(yè)間的約束關(guān)系并更新整體作業(yè)網(wǎng)絡(luò)結(jié)構(gòu)的時序約束關(guān)系就可按上述方式生成初始種群。

2.3.2 交叉與變異操作

免疫算法中交叉和變異操作對算法整體性能至關(guān)重要。交叉和變異概率越大則抗體被更新的機會越多，這有助于提高種群的多樣性但太大的交叉和變異概率也可能使優(yōu)良基因丟失［16］。在參考文獻［17］中交叉變異算子的基礎(chǔ)上設(shè)計了如下自適應(yīng)交叉（pc）和變異（pm）算子：

式（22）是方案貢獻值也是抗體親和度評價指標(biāo)，式（23）、（24）中Ag和As對應(yīng)2條交叉抗體中較大和較小的親和度值，Am和Av分別是當(dāng)前群體的最大與平均親和度值，Ac是當(dāng)前抗體的親和度值?？贵w可根據(jù)自身親和度在群體中的表現(xiàn)動態(tài)調(diào)節(jié)交叉或變異概率：親和度高于群體平均水平的抗體，親和度越高pm越小，親和度低于群體平均水平的抗體，親和度越低pc越大。這種方式可保留較優(yōu)抗體并有針對性地促使較差抗體進行鄰域搜索。此外，本文針對第2種方式生成的抗體設(shè)置了簡單快速的變異規(guī)則：①w j越大的作業(yè)調(diào)度優(yōu)先級越高。②W j越大的作業(yè)調(diào)度優(yōu)先級越高。③全部緊后作業(yè)總數(shù)越大的作業(yè)調(diào)度優(yōu)先級越高。④隨機交換模塊中的作業(yè)順序。①-④可針對編碼的一個或多個模塊實施從而靈活控制變異程度。抗體交叉變異流程如下：

步驟1：按抗體生成方式不同，劃分原抗體群為群1和群2，交叉抗體d1、d2需同時源于群1或群2。

步驟2：計算pc并生成隨機數(shù)r1，若r1≤pc則轉(zhuǎn)步驟3進行交叉，否則不交叉。

步驟3：若d1、d2都來自群2則隨機選擇2個相鄰模塊，重新生成2個模塊的作業(yè)順序后分別得到子抗體d1s和d2s；若d1、d2都來自群1則隨機產(chǎn)生滿足h2＞h1的2個位置h1和h2，d1中位置介于h1與h2間的作業(yè)按照d2中這些作業(yè)的對應(yīng)順序排列，其他作業(yè)位置不變得到子抗體d1s，同理形成d2s并最終根據(jù)親和度大小更新d1、d2。

步驟4：對交叉后的抗體群實現(xiàn)自適應(yīng)變異，群1抗體進行單點挪位變異，群2抗體則按前文所給變異規(guī)則進行模塊內(nèi)的變異。

2.3.3 種群更新與末尾淘汰機制

本文設(shè)置的知識記憶庫中最佳親和度值若連續(xù)U代未變將按照種群初始化方式重構(gòu)下一代種群，否則先按親和度降序排列交叉變異后的群體，再對末尾抗體實施克隆、變異，選出親和度最大的抗體淘汰當(dāng)前末尾抗體，親和度相同則根據(jù)抗體編碼和解碼后作業(yè)的松弛時間選擇相似度小的。

3 數(shù)值實驗及分析

3.1 實驗平臺與實例參數(shù)

Lambrechts等［18］提取服從三角分布的離散數(shù)據(jù)為作業(yè)設(shè)定不穩(wěn)定性成本權(quán)重，本文以相同方式使非虛擬作業(yè)權(quán)重服從參數(shù)為（0.01，0.06，0.10）的三角分布，結(jié)尾虛作業(yè)的權(quán)重從參數(shù)為（0.10，0.15，0.18）的三角分布中抽樣1 000次取平均。每個作業(yè)僅有2類質(zhì)量相關(guān)部件，初始衰退量lojq、cojq、sojq和gojq分別服從區(qū)間［0，1］、［0，1］、［0，3］和［0，10］內(nèi)的均勻分布。質(zhì)量相關(guān)部件的衰退服從gamma過程，其中形狀參數(shù)和尺寸參數(shù)分別服從區(qū)間［0.001 35，0.001 56］和［0.018 70，0.033 60］內(nèi)的均勻分布。調(diào)度算法中抗體規(guī)模為50，迭代20次，pc與pm算子中λ1=0.8，λ2=0.4，λ3=0.6，λ4=0.8。本文實驗利用差值百分比G來衡量I-I-A相對其他B算法所得目標(biāo)函數(shù)的改善程度。本文優(yōu)化目標(biāo)可能出現(xiàn)負(fù)數(shù)，按式（25）計算G，可直接通過G值分析出I-I-A相對不同算法的改善程度大小。G值為正數(shù)時表示I-I-A所得結(jié)果更優(yōu)，G值越大表示I-I-A優(yōu)化程度越明顯。

3.2 重調(diào)度算法性能對比

3.2.1 節(jié)選擇了工程實踐中常用的基于作業(yè)優(yōu)先順序的規(guī)則［19］AWA1和右移策略（RS）2種對比算法：①AWA1將作業(yè)按照在Fo中開始時間的先后順序排列，所有修復(fù)作業(yè)安排至正常作業(yè)的后一位形成AWA1編碼。②RS將修復(fù)作業(yè)安排在對應(yīng)正常作業(yè)結(jié)束時刻開始執(zhí)行，其他作業(yè)順延到各自的緊前作業(yè)全部完成后開始執(zhí)行［20］?？紤]到I-I-A是啟發(fā)式算法而AWA1與RS并非啟發(fā)式算法，因此3.2.1進一步選取同樣是啟發(fā)式算法的遺傳算法與I-I-A進行對比，驗證I-I-A的有效性。需說明的是，3.2.1節(jié)單次預(yù)測下的每組對比實驗僅對比單次預(yù)測-重調(diào)度后的裝配計劃的貢獻值；而3.2.2節(jié)則模擬了裝配現(xiàn)場時間驅(qū)動下按順序進行的多次預(yù)測-重調(diào)度過程并對最終形成的總裝配計劃的貢獻值進行后驗對比。

3.2.1 單次預(yù)測下算法性能對比

實驗在5種作業(yè)規(guī)模下進行，各規(guī)模下均取5個算例共進行5組實驗，這5個算例分別有且僅有1個關(guān)鍵作業(yè)。每個算例下的一組實驗需對關(guān)鍵作業(yè)激發(fā)預(yù)測機制并實現(xiàn)重調(diào)度的過程進行20次模擬，在保持預(yù)測部分一致的情況下對比運用I-I-A、AWA1和RS這3種重調(diào)度算法得到的調(diào)度計劃在目標(biāo)函數(shù)值上的表現(xiàn)。表1每組數(shù)據(jù)是該組20次模擬所得結(jié)果里與目標(biāo)函數(shù)中位值所在次對應(yīng)的數(shù)據(jù)信息。用G1和G2分別表示I-I-A與AWA1、RS的目標(biāo)函數(shù)優(yōu)化結(jié)果之間的差值百分比。表1中G1和G2列大部分為正數(shù)說明I-I-A結(jié)果基本都優(yōu)于AWA1和RS，多數(shù)G2均值比G1均值大10%左右反映出I-I-A優(yōu)于RS的程度大于AWA1。僅從目標(biāo)函數(shù)優(yōu)化結(jié)果可見I-I-A相比AWA1和RS有顯著的改善效果，但I-IA的運算時間遠(yuǎn)遠(yuǎn)大于AWA1和RS，主要因為本文的I-I-A需迭代尋優(yōu)而AWA1和RS并不存在迭代搜索過程。

考慮到本文I-I-A屬于啟發(fā)式算法，遺傳算法（GA）作為經(jīng)典啟發(fā)式算法其解決調(diào)度問題的適用性和有效性已被大量文獻研究驗證，為進一步驗證I-I-A的算法性能，將其與GA進行對比。GA在種群規(guī)模和迭代總數(shù)上與I-I-A保持一致，但交叉和變異采用固定概率0.8和0.7，初始種群僅采用一種隨機生成方式。該對比實驗中各算例都確定了10個激發(fā)預(yù)測機制的關(guān)鍵作業(yè)，每個算例進行3次實驗，每次實驗這10個關(guān)鍵作業(yè)在保持前端一致而后端分別采用I-I-A和GA可得到10個調(diào)度結(jié)果和對應(yīng)的目標(biāo)函數(shù)值，I-I-A優(yōu)化得到的目標(biāo)函數(shù)值與GA優(yōu)化得到的目標(biāo)函數(shù)值之間的差值百分比用G表示，表2匯總了每次實驗10個實驗結(jié)果的最大、最小、平均G和2種算法的運行時間。

表1 單次預(yù)測下I-I-A與AWA1以及RS對比結(jié)果Tab.1 Comparison of results of I-I-A,AWA1,and RS in single prediction

表2各算例實驗組下的平均G基本都在12%以上，60job時G的均值達到了29.61%，可見I-I-A的優(yōu)化結(jié)果明顯好于GA，并且I-I-A在運算時間上仍略優(yōu)于GA特別是在作業(yè)規(guī)模較大的算例中平均節(jié)約時間在6s左右。I-I-A在設(shè)置了知識記憶庫和末尾淘汰機制的情況下運算效率仍高于GA，側(cè)面反映出I-I-A中已改進部分的高效性。

3.2.2 多次預(yù)測下調(diào)度計劃后驗對比實驗

飛機裝配項目中裝配作業(yè)多且裝配時間長，通常存在多個關(guān)鍵作業(yè)也需進行多次預(yù)測和裝配計劃調(diào)整的情況。圖3給出了3次執(zhí)行預(yù)測-重調(diào)度（采用AWA1規(guī)則）后所有作業(yè)實際的總調(diào)度計劃。圖中第3次預(yù)測-重調(diào)度后形成的總調(diào)度計劃是第1、2、3次預(yù)測-重調(diào)度過程累積而成的總調(diào)度計劃，若當(dāng)前工位進入一個完全相同的新項目，該總調(diào)度計劃對制定新項目的裝配計劃具有重要參考價值。本部分實驗?zāi)M多次預(yù)測-重調(diào)度過程并對比不同重調(diào)度算法形成的實際總調(diào)度計劃在目標(biāo)函數(shù)上的表現(xiàn)。該實驗將工程中常用的AWA1規(guī)則改進成AWA2（即作業(yè)按Fo中開始時間的順序排列），若同時開始則w j+W j越大調(diào)度優(yōu)先級越高，所有修復(fù)作業(yè)插入至對應(yīng)正常作業(yè)的后一位形成AWA2重調(diào)度編碼。

圖3 多次預(yù)測后實際調(diào)度計劃示意Fig.3 Actual scheduling plan after multiple predic?tions

AWA1、AWA2與I-I-A的對比實驗在20job的算例下進行，列表［1，3，12，2，4，5，7，9，8，16，15，10，11］用于挑選激發(fā)預(yù)測機制的作業(yè)，激發(fā)作業(yè)規(guī)模介于區(qū)間［2，10］內(nèi)，各規(guī)模下從列表中隨機選擇30組不重復(fù)的作業(yè)并進行30組預(yù)測-重調(diào)度仿真模擬。該實驗采用G3和G4分別表示I-I-A與AWA1、AWA2得到的總調(diào)度計劃在目標(biāo)函數(shù)結(jié)果上的差值百分比。

不同激發(fā)作業(yè)規(guī)模下30組對比實驗的G3和G4分布分別如圖4深色與淺色箱形圖所示，圖中十字形點是30組數(shù)據(jù)里太大或者太小的數(shù)據(jù)視為異常值的點。與圖4相關(guān)的數(shù)據(jù)見表3。圖4不同規(guī)模下G3和G4的分布多為正數(shù)且形狀相似，這說明I-I-A的優(yōu)化能力強于AWA1和AWA2并且I-I-A優(yōu)于AWA1和AWA2的程度基本相同。

表2 單次預(yù)測下I-I-A與GA對比結(jié)果Tab.2 Comparison of results of I-I-A and GA in single prediction

圖4 不同激發(fā)作業(yè)規(guī)模下的G值分布箱形圖Fig.4 Box-plot of G distributions in different scales of trigger jobs

表3中較小四分位值、中位值和較大四分位值是將各激發(fā)規(guī)模下的30組G3（G4）升序排列后第25%，第50%和第75%個位置的G3（G4）值，分別對應(yīng)圖4矩形盒下、中、上3條線所示G值。表3較小四分位值對應(yīng)列的G值大部分都是正數(shù)說明多數(shù)規(guī)模下的30組實驗結(jié)果中I-I-A至少有75%的結(jié)果優(yōu)于AWA1或AWA2且30組G值中有75%的數(shù)據(jù)大于表中所給值，但激發(fā)作業(yè)規(guī)模為3和5的數(shù)據(jù)中也分別出現(xiàn)G4的較小四分位值是-2.54%和-0.254%的情況，說明這2種規(guī)模下的30組實驗中至少有25%的組數(shù)I-I-A的結(jié)果不如AWA2好，一定程度上反映出經(jīng)改進的AWA2規(guī)則在某些情況下性能優(yōu)于I-I-A。進一步分析表3，從G中位值以及較大四分位值來看G3和G4均未再出現(xiàn)負(fù)數(shù)并且G3和G4均值基本都大于40%，說明I-I-A不僅能在單次預(yù)測-重調(diào)度下生成貢獻值較大的重調(diào)度計劃，多次預(yù)測-重調(diào)度后形成的總調(diào)度計劃相比AWA1和AWA2而言依然具有更高的貢獻值，可為新進入當(dāng)前工位的裝配項目提供更合理的裝配計劃模板。

表3 不同激發(fā)作業(yè)規(guī)模下目標(biāo)函數(shù)值和G值表現(xiàn)情況Tab.3 Performance of objective and G values in different scales of trigger jobs

3.3 整體框架性能分析

3.2 節(jié)僅對比后端重調(diào)度算法并驗證了I-I-A的效果和效率，不能體現(xiàn)本文所提預(yù)測-重調(diào)度框架的優(yōu)勢，本節(jié)將該框架與文獻中經(jīng)典的前攝調(diào)度框架以及純反應(yīng)型重調(diào)度框架進行對比，對比實驗中采用了前攝-右移框架和反應(yīng)-右移框架。前攝-右移框架在初始調(diào)度計劃中事先插入部分緩沖時間用以應(yīng)對可能的修復(fù)干擾，當(dāng)有修復(fù)作業(yè)插入時采用右移策略更新調(diào)度計劃；反應(yīng)-右移框架不插入緩沖時間，僅在有修復(fù)作業(yè)加入時才采用右移策略更新調(diào)度計劃；本文框架在計劃執(zhí)行過程中主動預(yù)測并基于預(yù)測結(jié)果預(yù)調(diào)度一部分修復(fù)作業(yè)從而減少未來可能的修復(fù)干擾。本文框架前端SVR預(yù)測模型的平均準(zhǔn)確率接近81%，各算例實驗通過抽樣仿真模擬不同框架下計劃執(zhí)行的完整過程，修復(fù)場景根據(jù)作業(yè)的合格概率隨機抽樣得到，各算例下的5組實驗抽樣場景數(shù)均為50。需說明的是前攝-右移框架和反應(yīng)-右移框架除初始計劃不同，其他無區(qū)別，使用相同的抽樣場景。本文框架、前攝-右移框架、反應(yīng)-右移框架在50個仿真場景下得到的調(diào)度計劃平均周期時間見表4中的周期1、周期2和周期3，仿真中實際右移次數(shù)的平均值見最后3列數(shù)據(jù)。

表4部分算例本文框架相比前攝-右移框架在調(diào)度計劃平均周期上縮短了10個單位左右，主要原因是本文框架不在初始計劃內(nèi)插入緩沖而僅基于預(yù)測結(jié)果預(yù)調(diào)度部分修復(fù)作業(yè)因此降低了緩沖時間的冗余程度，實驗結(jié)果也反映出前攝-右移框架事先插入的緩沖時間針對性弱預(yù)防作用較??；本文框架與反應(yīng)-右移框架在調(diào)度計劃平均周期上非常接近但也有近4個單位時間的減少并且平均右移數(shù)目也少了近4次，這意味著本文框架減少了預(yù)期外質(zhì)量修復(fù)作業(yè)加入導(dǎo)致的事后型計劃調(diào)整次數(shù)，進一步體現(xiàn)出本文框架通過事前預(yù)測能準(zhǔn)確預(yù)調(diào)度出一部分修復(fù)作業(yè)便于在修復(fù)需求產(chǎn)生時直接按預(yù)調(diào)度計劃執(zhí)行。但是，本文框架也需付出預(yù)測-重調(diào)度的運算時間代價，由于算例中調(diào)度作業(yè)的時間單位未明確給出，因此無法與算法時間單位（s）統(tǒng)一，更難將包括預(yù)測部分在內(nèi)的整體算法運行時間一同納入調(diào)度仿真中以給出包含運算時間的最接近應(yīng)用實際的調(diào)度計劃周期，但是實際工程中可根據(jù)事前預(yù)測-重調(diào)度與事后重調(diào)度消耗時間和成本的具體情況選擇最合適的框架。

表4 各算例下不同框架仿真結(jié)果Tab.4 Simulation results of different frameworks in each case

4 結(jié)語

（1）以飛機移動裝配線為背景，針對質(zhì)量修復(fù)作業(yè)的加入干擾調(diào)度計劃的問題提出了基于預(yù)測機制的裝配作業(yè)重調(diào)度框架，框架前端訓(xùn)練了質(zhì)量預(yù)測模型，后端建立了作業(yè)重調(diào)度模型。

（2）提出了重調(diào)度算法I-I-A并通過不同的對比實驗驗證有效性。總體看，I-I-A在優(yōu)化效果和效率上均好于GA；相比AWA1和RS，I-I-A雖能得到更佳的優(yōu)化結(jié)果但在簡便程度和算法運行時間上的劣勢也較明顯。

（3）相比現(xiàn)有文獻中利用公式推導(dǎo)實現(xiàn)前攝調(diào)度，該框架可掌握更準(zhǔn)確的實際裝配信息進而得到更準(zhǔn)確的預(yù)測結(jié)果，有利于降低計劃中所插緩沖時間或資源的冗余度。此外，相比起反應(yīng)型調(diào)度方式，本文框架更利于保持項目執(zhí)行過程的穩(wěn)定性。

（4）后續(xù)進一步優(yōu)化前端預(yù)測模型并構(gòu)建前后端的集成優(yōu)化模型。