陸志強(qiáng)，方 佳

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

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

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

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

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

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

1.1 問(wèn)題描述

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

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

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

（3）為保證飛機(jī)裝配的質(zhì)量，作業(yè)j完成后必須接受n個(gè)質(zhì)量特性偏差檢測(cè)，檢測(cè)時(shí)間忽略不計(jì)，結(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個(gè)質(zhì)量特性偏差值在x、y和z3個(gè)方向上的分量。若X j各維度均落在標(biāo)準(zhǔn)規(guī)格范圍內(nèi)可繼續(xù)執(zhí)行后續(xù)作業(yè)；否則需對(duì)作業(yè)j添加屬性為tdjr=?tdj和r jrk=?r jk的修復(fù)作業(yè)jr，jr未完成時(shí)作業(yè)j所有緊后作業(yè)都無(wú)法執(zhí)行。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

S j中每個(gè)樣本的輸入矢量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)練支持向量回歸模型

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

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

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

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

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

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

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

2.3 改進(jìn)型免疫算法

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

2.3.1 初始種群的生成

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

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

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

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

2.3.2 交叉與變異操作

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

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

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

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

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

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

2.3.3 種群更新與末尾淘汰機(jī)制

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

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

3.1 實(shí)驗(yàn)平臺(tái)與實(shí)例參數(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次取平均。每個(gè)作業(yè)僅有2類(lèi)質(zhì)量相關(guān)部件，初始衰退量lojq、cojq、sojq和gojq分別服從區(qū)間［0，1］、［0，1］、［0，3］和［0，10］內(nèi)的均勻分布。質(zhì)量相關(guān)部件的衰退服從gamma過(guò)程，其中形狀參數(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。本文實(shí)驗(yàn)利用差值百分比G來(lái)衡量I-I-A相對(duì)其他B算法所得目標(biāo)函數(shù)的改善程度。本文優(yōu)化目標(biāo)可能出現(xiàn)負(fù)數(shù)，按式（25）計(jì)算G，可直接通過(guò)G值分析出I-I-A相對(duì)不同算法的改善程度大小。G值為正數(shù)時(shí)表示I-I-A所得結(jié)果更優(yōu)，G值越大表示I-I-A優(yōu)化程度越明顯。

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

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

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

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

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

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

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

3.2.2 多次預(yù)測(cè)下調(diào)度計(jì)劃后驗(yàn)對(duì)比實(shí)驗(yàn)

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

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

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

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