考慮質(zhì)量預(yù)測(cè)的前攝調(diào)度問(wèn)題模型與算法

陸志強(qiáng)， 朱宏偉， 廖怡娜

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

對(duì)于飛機(jī)、船舶等大型設(shè)備裝配制造企業(yè)而言，建立合理的調(diào)度計(jì)劃是實(shí)現(xiàn)管理者高效管理裝配過(guò)程的重要前提[1]. 目前，陸志強(qiáng)等[2]和朱宏偉等[3]將大型設(shè)備裝配過(guò)程的調(diào)度問(wèn)題抽象為資源受限項(xiàng)目調(diào)度問(wèn)題(resource constrained project scheduling problem, RCPSP)及其擴(kuò)展問(wèn)題. 其中，RCPSP問(wèn)題以滿足資源限制和作業(yè)優(yōu)先順序?yàn)榍疤?，通過(guò)合理安排裝配作業(yè)的開(kāi)始時(shí)間來(lái)達(dá)到優(yōu)化相關(guān)決策目標(biāo)(包括最小化裝配工期等)的目的.

盡管已有學(xué)者就靜態(tài)環(huán)境下RCPSP問(wèn)題做了許多研究[4-6]，但裝配環(huán)境中存在的不確定性使得實(shí)際裝配過(guò)程的調(diào)度計(jì)劃安排變得更加復(fù)雜. 不確定性環(huán)境下的RCPSP研究主要集中在決策方法和研究對(duì)象兩個(gè)方面. 在決策方法方面，目前解決不確定性RCPSP問(wèn)題的方法主要包括反應(yīng)式調(diào)度、隨機(jī)項(xiàng)目調(diào)度、模糊項(xiàng)目調(diào)度和前攝調(diào)度等. 其中，前攝調(diào)度通過(guò)生成模板調(diào)度計(jì)劃以盡可能防止項(xiàng)目執(zhí)行過(guò)程中由于不確定性因素導(dǎo)致的中斷[7]. 崔南方等[8]和徐小峰等[9]分別提出了集中緩沖、STC(starting time criticality)分散緩沖方法和關(guān)鍵鏈緩沖區(qū)設(shè)置方法. Chakrabortty等[10]以具有不同概率分布函數(shù)的隨機(jī)變量表示作業(yè)持續(xù)時(shí)間，并針對(duì)該問(wèn)題提出了一種魯棒優(yōu)化模型. 在研究對(duì)象方面，除物料到達(dá)不確定、作業(yè)工期不確定和資源空窗期等外，部分學(xué)者還對(duì)有關(guān)質(zhì)量缺陷問(wèn)題開(kāi)展了相關(guān)研究. 在單項(xiàng)目問(wèn)題中，Al-Fawzan等[11]考慮到作業(yè)的執(zhí)行時(shí)間會(huì)因?yàn)樽鳂I(yè)返工而增加. 為了有效求解這一問(wèn)題，Abbasi等[12]提出了一種模擬退火算法. 在多項(xiàng)目問(wèn)題中，Tiwari等[13]假設(shè)作業(yè)可以先按照一種不滿足質(zhì)量標(biāo)準(zhǔn)的模式執(zhí)行，后續(xù)通過(guò)作業(yè)返工的形式來(lái)完善該作業(yè). 此外，Maghsoudlou等[14]認(rèn)為作業(yè)產(chǎn)生返工的風(fēng)險(xiǎn)由人員的技能水平差異所決定，因此以項(xiàng)目的執(zhí)行成本和作業(yè)的返工風(fēng)險(xiǎn)作為目標(biāo)函數(shù). 然而，上述研究主要將目光集中在返工事件發(fā)生后被動(dòng)的應(yīng)對(duì)處理，缺少通過(guò)主動(dòng)改善影響裝配質(zhì)量的相關(guān)因素而減少質(zhì)量缺陷的深入研究.

事實(shí)上，在裝配或加工流程明確的前提下，作業(yè)質(zhì)量可以通過(guò)分析質(zhì)量偏差傳遞過(guò)程以及建立質(zhì)量預(yù)測(cè)模型來(lái)實(shí)現(xiàn). 劉偉東等[15]通過(guò)建立偏差源傳遞的基本偏差流模型說(shuō)明零件內(nèi)部和外部偏差傳遞和相互作用. 江平宇等[16]采用基于粒子群算法優(yōu)化的支持矢量回歸機(jī)方法實(shí)現(xiàn)各作業(yè)的加工質(zhì)量預(yù)測(cè). 這些研究雖對(duì)質(zhì)量偏差傳遞機(jī)理和質(zhì)量預(yù)測(cè)方法進(jìn)行了詳細(xì)的分析，但相關(guān)模型仍不能真實(shí)反映實(shí)際飛機(jī)裝配過(guò)程的作業(yè)裝配質(zhì)量. 由于飛機(jī)裝配本身工藝的復(fù)雜性，除了待裝配零件加工質(zhì)量等因素對(duì)作業(yè)的影響之外，作業(yè)完成質(zhì)量極大程度上依賴于裝配人員水平. 裝配人員的水平會(huì)影響整個(gè)裝配系統(tǒng)的可靠性與穩(wěn)定性，是產(chǎn)生質(zhì)量缺陷的重要原因之一[17].

綜上所述，本文以飛機(jī)裝配過(guò)程為研究對(duì)象，分析與飛機(jī)裝配質(zhì)量傳遞相關(guān)的環(huán)節(jié)與信息，并結(jié)合裝配人員水平對(duì)作業(yè)質(zhì)量的影響情況，建立考慮裝配人員水平的作業(yè)質(zhì)量預(yù)測(cè)模型. 由于飛機(jī)裝配中產(chǎn)生的質(zhì)量特征(尺寸、位置和形狀等)具有高度非線性[18]，結(jié)合支持向量回歸(support vector regression，SVR)在非線性預(yù)測(cè)領(lǐng)域的適用性[19]，本文選擇用高斯徑向基函數(shù)為核函數(shù)的SVR預(yù)測(cè)模型對(duì)作業(yè)質(zhì)量進(jìn)行預(yù)測(cè). 在此基礎(chǔ)上，考慮到裝配人員分配的合理性會(huì)通過(guò)作業(yè)質(zhì)量間接影響到飛機(jī)整體裝配進(jìn)度，本文進(jìn)一步提出了考慮作業(yè)質(zhì)量預(yù)測(cè)的前攝調(diào)度問(wèn)題，將裝配作業(yè)的時(shí)間和人員決策耦合在同一決策框架中，并構(gòu)建兩階段禁忌搜索算法進(jìn)行求解.

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

1.1 問(wèn)題描述

考慮質(zhì)量預(yù)測(cè)的前攝調(diào)度問(wèn)題，是通過(guò)分析各質(zhì)量相關(guān)因素對(duì)飛機(jī)裝配過(guò)程作業(yè)質(zhì)量的影響形式，并結(jié)合實(shí)際作業(yè)質(zhì)量的歷史數(shù)據(jù)建立作業(yè)質(zhì)量預(yù)測(cè)模型，以此為基礎(chǔ)實(shí)現(xiàn)模板調(diào)度計(jì)劃制定過(guò)程中裝配資源合理分配和裝配工期優(yōu)化的目的. 考慮質(zhì)量預(yù)測(cè)的前攝調(diào)度問(wèn)題的假設(shè)和說(shuō)明如下.

1)設(shè)有I個(gè)裝配作業(yè)I={1,2,...,n}，i∈I為作業(yè)編號(hào)；作業(yè)i的前道作業(yè)集合為Pi，作業(yè)j為作業(yè)i的第j項(xiàng)前道作業(yè)；作業(yè)一旦開(kāi)始便無(wú)法中斷.

2)所有作業(yè)需要由相關(guān)裝配人員等可更新的裝配資源配合完成，記裝配資源種類為K={1,2,...,e},k∈K為資源種類編號(hào). 其中，裝配人員存在異質(zhì)性，主要體現(xiàn)在裝配人員水平的差異. 記m∈M?K為裝配人員種類編號(hào)，則裝配人員m的水平可以表示為lm∈L. 不同裝配作業(yè)i對(duì)資源k需求量記為rik. 資源k的資源總量上限為Rk.

圖1 作業(yè)質(zhì)量傳遞過(guò)程Fig.1 Transfer process of job quality

5)將時(shí)間離散化，記時(shí)間集合T={1,2,...,z}，t∈T為離散時(shí)間節(jié)點(diǎn).

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

基于以上分析，建立問(wèn)題數(shù)學(xué)模型如下：

(1)

(2)

(3)

(4)

(5)

(6)

xit={0,1},i∈I, ?t∈T;

(7)

yim={0,1}, ?i∈I, ?m∈M.

(8)

式(1)表示生成前攝調(diào)度計(jì)劃的目標(biāo)函數(shù)為最小化項(xiàng)目工期；式(2)代表作業(yè)間的時(shí)序約束，即任一作業(yè)不得早于其前道作業(yè)結(jié)束之前開(kāi)始；式(3)代表資源約束，即任一時(shí)刻資源用量不得多于資源總供應(yīng)量；式(4)代表作業(yè)一旦開(kāi)始就不能中斷；式(5)代表任一裝配人員在同一時(shí)刻最多只能參與一個(gè)作業(yè)；式(6)為作業(yè)實(shí)際工期與人員水平、工件質(zhì)量及前道作業(yè)質(zhì)量間的映射關(guān)系，通過(guò)預(yù)測(cè)模型實(shí)現(xiàn)；式(7)和(8)分別代表了xit與yim的取值范圍.

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

針對(duì)質(zhì)量預(yù)測(cè)前攝調(diào)度問(wèn)題的特點(diǎn)，提出考慮人員水平的SVR預(yù)測(cè)模型和兩階段循環(huán)迭代搜索算法. 算法核心包括：結(jié)合裝配作業(yè)歷史質(zhì)量數(shù)據(jù)，以裝配人員水平、工件質(zhì)量和前道作業(yè)裝配質(zhì)量等數(shù)據(jù)為輸入，作業(yè)裝配質(zhì)量為輸出，構(gòu)建考慮人員水平的SVR預(yù)測(cè)模型. 在SVR預(yù)測(cè)模型基礎(chǔ)上構(gòu)建兩階段循環(huán)迭代搜索算法. 算法上層為基于作業(yè)編碼的禁忌搜索算法，優(yōu)化作業(yè)執(zhí)行順序；算法下層在SVR預(yù)測(cè)模型的基礎(chǔ)之上，設(shè)計(jì)基于人員分配編碼的禁忌搜索算法，通過(guò)優(yōu)化人員配置提升作業(yè)質(zhì)量，從而減少作業(yè)返工的發(fā)生，降低項(xiàng)目整體工期.

2.1 SVR預(yù)測(cè)模型

SVR的基本原理為將給定的訓(xùn)練數(shù)據(jù)集映射到高維特征空間，在高維特征空間中尋求一個(gè)最優(yōu)超平面f(x)使得樣本點(diǎn)Ym(此處Yim和Xim省略下標(biāo)i)離超平面的總方差不大于誤差ε則為回歸無(wú)損，即滿足|Ym-f(Xm)|≤ε,?m. SVR標(biāo)準(zhǔn)狀態(tài)形式為：

圖2 多輸出目標(biāo)SVR模型訓(xùn)練及預(yù)測(cè)過(guò)程Fig.2 Training and prediction processes of multi-output SVRmodel

綜上所述，多輸出SVR預(yù)測(cè)模型的訓(xùn)練主要包含如下步驟：

步驟1確定訓(xùn)練樣本集，向模型中輸入樣本集中的樣本(Xim,Yim).

步驟2利用MOR，針對(duì)Yim中的每個(gè)偏差值，將Xim映射到高維空間中，并通過(guò)求解對(duì)偶問(wèn)題，最終分別得到特征向量Xim對(duì)應(yīng)的Yim中各個(gè)目標(biāo)輸出值的超平面參數(shù).

步驟3通過(guò)步驟2得到的各個(gè)超平面的參數(shù)分別建立各目標(biāo)輸出超平面模型.

2.2 兩階段循環(huán)迭代搜索算法

鑒于考慮質(zhì)量預(yù)測(cè)前攝調(diào)度問(wèn)題耦合了時(shí)間和資源兩類決策，本文采用兩階段循環(huán)迭代搜索算法構(gòu)建模板計(jì)劃. 其中，考慮到禁忌搜索算法在求解效率和搜索深度的優(yōu)勢(shì)，兩階段算法在上、下兩層中均采用禁忌搜索算法來(lái)實(shí)現(xiàn)時(shí)間和資源的決策. 算法上層借鑒陸志強(qiáng)等[2]求解靜態(tài)RCPSP問(wèn)題時(shí)采用的作業(yè)列表編碼方法設(shè)計(jì)禁忌搜索框架對(duì)作業(yè)執(zhí)行順序進(jìn)行深度搜索；鑒于傳統(tǒng)串行調(diào)度(serial schedule generation scheme, SSGS)在解碼時(shí)缺乏對(duì)人員合理安排的機(jī)制，下層在傳統(tǒng)串行調(diào)度基礎(chǔ)上內(nèi)嵌人員分配搜索模塊，通過(guò)對(duì)人員分配編碼進(jìn)行深度搜索來(lái)獲取較優(yōu)的人員配置情形. 算法整體流程圖如圖3所示.

圖3 兩階段循環(huán)迭代搜索算法流程Fig.3 Flow chart of two-level iterative search algorithm

2.2.1 基于作業(yè)列表禁忌搜索框架

基于作業(yè)列表禁忌搜索框架采用作業(yè)列表生成第一階段的作業(yè)執(zhí)行順序決策. 作業(yè)列表的編碼例子如圖4a所示，每一編碼位的數(shù)字代表作業(yè)編號(hào)，編碼過(guò)程要求：1)第一個(gè)編碼位和最后一個(gè)編碼位分別為虛擬初始作業(yè)和虛擬結(jié)束作業(yè)；2)后一編碼位中不得包含前一編碼位的直接或間接前道作業(yè). 只有前一編碼位的作業(yè)被執(zhí)行完成后，后一編碼位的作業(yè)才可以安排開(kāi)始.

圖4 鄰域生成方法示例Fig.4 Example of neighborhood generation method

初始作業(yè)列表通過(guò)隨機(jī)規(guī)則生成. 為搜索作業(yè)列表的鄰域，禁忌搜索框架采用兩作業(yè)隨機(jī)鄰域生成方法進(jìn)行單項(xiàng)互換操作，操作過(guò)程主要為：首先從當(dāng)前作業(yè)列表中隨機(jī)選取2個(gè)無(wú)直接或間接前道關(guān)系的作業(yè)，并互換兩作業(yè)在作業(yè)列表中的位置(如圖4b所示). 每一階段選取解碼后模板計(jì)劃工期最優(yōu)的作業(yè)列表所對(duì)應(yīng)的互換操作作為下一步移動(dòng)的禁忌對(duì)象，禁忌次數(shù)在[tabu1min,tabu1max]間隨機(jī)生成，設(shè)置禁忌搜索最大循環(huán)次數(shù)為iter1.

算法具體步驟如下：

步驟1令階段k=1，初始化作業(yè)列表Lk. 調(diào)用內(nèi)嵌人員分配搜索模塊的串行調(diào)度進(jìn)行解碼，獲得初始解SLk，令最優(yōu)解Sbest=SLk.

步驟2調(diào)用禁忌搜索框架搜索作業(yè)列表的鄰域N(Lk). 若列表L′∈N(Lk)未被禁忌，則調(diào)用內(nèi)嵌人員分配搜索模塊的串行調(diào)度求解；否則跳過(guò)該列表.

步驟3找出L*∈N(Lk)具有最小模板計(jì)劃工期. 若SL*

步驟4令k=k+1，構(gòu)建新鄰域N(Lk)=N(L*).

步驟5若達(dá)到終止條件，則輸出Sbest；否則，轉(zhuǎn)步驟2.

2.2.2 內(nèi)嵌人員分配搜索模塊串行調(diào)度

本文通過(guò)人員分配搜索模塊對(duì)可行的人員組合進(jìn)行搜索，以獲得較優(yōu)的人員分配方案，并在此基礎(chǔ)上通過(guò)的串行調(diào)度生成模板調(diào)度計(jì)劃. 內(nèi)嵌人員分配搜索模塊的初始人員分配方案通過(guò)最高質(zhì)量水平(highest quality level，HQL)規(guī)則生成. 采用HQL規(guī)則時(shí)，當(dāng)前作業(yè)會(huì)被分配當(dāng)前質(zhì)量水平最高的裝配人員.

為搜索當(dāng)前人員分配方案的鄰域，首先需要選取待調(diào)整作業(yè)組合(i,j)，其選取的規(guī)則為：若作業(yè)i、j不存在優(yōu)先關(guān)系約束且兩作業(yè)的開(kāi)始時(shí)間和結(jié)束時(shí)間滿足STi

將每一階段解碼后模板計(jì)劃工期最優(yōu)的裝配人員交換操作作為下一步交換操作的禁忌對(duì)象，禁忌次數(shù)在[tabu2min,tabu2max]間隨機(jī)生成，設(shè)置禁忌搜索最大循環(huán)次數(shù)為iter2.

算法具體步驟如下：

步驟1輸入作業(yè)列表L. 記最優(yōu)模板計(jì)劃工期為T(mén)best=M(M為足夠大的數(shù)).

步驟2令階段k=1采用HQL規(guī)則生成初始裝配人員分配方案Ck.

步驟4采用SSGS生成模板計(jì)劃，記模板計(jì)劃工期為T(mén)Ck. 若Tbest>TCk，則令Tbest=TCk.

步驟5令階段k=k+1，調(diào)用人員分配搜索模塊搜索人員配置的鄰域N(Ck). 若列表C′∈N(Ck)未被禁忌，則調(diào)用SVR預(yù)測(cè)模型預(yù)測(cè)各作業(yè)裝配質(zhì)量，并采用SSGS求解模板計(jì)劃；否則跳過(guò)該列表.

步驟6找出C*∈N(Ck)具有最小模板計(jì)劃工期. 若Tbest>TC*，則Tbest=TC*.

步驟7令k=k+1，構(gòu)建新鄰域N(Ck)=N(C*).

步驟8若達(dá)到終止條件，則輸出Tbest；否則，轉(zhuǎn)步驟5.

3 實(shí)例應(yīng)用及分析

3.1 實(shí)驗(yàn)平臺(tái)

本文以某型號(hào)支線客機(jī)前機(jī)身、后機(jī)身和機(jī)身尾軸裝配工位的部分裝配流程和歷史裝配數(shù)據(jù)為例對(duì)算法進(jìn)行驗(yàn)證. 上述裝配流程分別包含21、32和42項(xiàng)裝配作業(yè)，其中第一和最后道作業(yè)為虛擬作業(yè)，所涉及的裝配人員按水平可劃分為高級(jí)技工、中級(jí)技工和初級(jí)技工3類. 本文所有測(cè)試實(shí)驗(yàn)均運(yùn)用python3.7編程實(shí)現(xiàn)，測(cè)試實(shí)驗(yàn)在Internet Core i7處理器，3.4GHz主頻，8G內(nèi)存的測(cè)試平臺(tái)上進(jìn)行.

3.2 SVR預(yù)測(cè)模型效果驗(yàn)證

為了驗(yàn)證SVR預(yù)測(cè)模型的準(zhǔn)確性，本文分別從上述3個(gè)不同規(guī)模算例中選取裝配作業(yè)的歷史裝配質(zhì)量信息生成訓(xùn)練樣本，并為裝配作業(yè)建立SVR預(yù)測(cè)模型. 實(shí)驗(yàn)為除虛擬作業(yè)外的每一道作業(yè)生成M=1 000組訓(xùn)練樣本Si={(Xim,Yim)|?i∈I,m=1,2,...,M}，同時(shí)根據(jù)2.1節(jié)中總結(jié)的步驟將其輸入模型中進(jìn)行學(xué)習(xí). 經(jīng)交叉驗(yàn)證后的SVR模型平均準(zhǔn)確率可達(dá)95%以上. 圖5為3個(gè)算例S21、S32、S42的預(yù)測(cè)準(zhǔn)確率平均值，其中當(dāng)裝配人員的最高水平為中級(jí)時(shí)，作業(yè)質(zhì)量預(yù)測(cè)準(zhǔn)確率最低，但與實(shí)測(cè)值相比誤差仍然能夠控制在5%以內(nèi). 因此，該SVR模型能夠較好地用于裝配作業(yè)質(zhì)量的預(yù)測(cè)，為模板調(diào)度計(jì)劃的制定提供可靠的依據(jù).

圖5 SVR預(yù)測(cè)模型準(zhǔn)確率Fig.5 Accuracy of SVR prediction model

3.3 兩階段循環(huán)迭代搜索算法效果驗(yàn)證

為了有效地評(píng)價(jià)本文所提出的兩階段循環(huán)迭代搜索算法(記為T(mén)SD)的有效性，本文基于另外3種生成模板調(diào)度計(jì)劃的方法，通過(guò)對(duì)作業(yè)的實(shí)際工件質(zhì)量添加隨機(jī)擾動(dòng)，模擬不同場(chǎng)景下裝配線的實(shí)際情況，并統(tǒng)一采用右移算法(right shift, RS)來(lái)評(píng)價(jià)各模板計(jì)劃應(yīng)對(duì)隨機(jī)擾動(dòng)時(shí)的能力. 其他3種模板調(diào)度計(jì)劃生成方法包括：1)CPLEX. 通過(guò)CPLEX軟件求解各算例在靜態(tài)環(huán)境下，即不考慮作業(yè)發(fā)生返工；2)CPLEX-RANDOM. 保留CPLEX軟件所得最優(yōu)調(diào)度計(jì)劃的各作業(yè)執(zhí)行順序，并采用隨機(jī)規(guī)則為各作業(yè)安排裝配人員，通過(guò)SVR預(yù)測(cè)模型重新計(jì)算各作業(yè)執(zhí)行時(shí)間；3)CPLEX-TS. 在CPLEX-RANDOM基礎(chǔ)上，增加2.2.2節(jié)的人員分配搜索模塊優(yōu)化人員配置.

本文為3個(gè)算例S21、S32、S42各生成s=1,2,...,10組實(shí)驗(yàn)，每組實(shí)驗(yàn)中各作業(yè)的工件質(zhì)量服從正態(tài)分布N(ETAsi,σsi|?s,?i). 右移算法為實(shí)際生產(chǎn)中常用的一種簡(jiǎn)單有效的修復(fù)規(guī)則，所有作業(yè)順延至各自前道作業(yè)全部完成后開(kāi)始執(zhí)行. 每組實(shí)驗(yàn)隨機(jī)擾動(dòng)次數(shù)設(shè)為50次. 各模板調(diào)度計(jì)劃應(yīng)對(duì)隨機(jī)擾動(dòng)的評(píng)價(jià)指標(biāo)包含項(xiàng)目實(shí)際工期和作業(yè)開(kāi)始時(shí)間偏差兩類，其中作業(yè)開(kāi)始時(shí)間偏差為

3.3.1 模板調(diào)度計(jì)劃實(shí)驗(yàn)結(jié)果

CPLEX、CPLEX-RANDOM、CPLEX-TS以及TSD方法所求得的模板調(diào)度計(jì)劃實(shí)驗(yàn)結(jié)果如表1～3所示，在模板計(jì)劃工期方面，因?yàn)镃PLEX僅用到靜態(tài)環(huán)境下的作業(yè)執(zhí)行時(shí)間信息，因此其所得Eo值最小且各組別均相等.

相較其他3種方法，TSD求解所得Eo均值最小，CPLEX-TS次之，而采用隨機(jī)規(guī)則進(jìn)行人員配置的CPLEX-RANDOM最大，其原因?yàn)椋合啾菴PLEX-RANDOM，CPLEX-TS可以通過(guò)內(nèi)嵌的人員分配搜索模塊優(yōu)化初期不合理的人員配置，減少作業(yè)因質(zhì)量問(wèn)題發(fā)生返工的情況，進(jìn)而降低模板調(diào)度計(jì)劃的工期；由于CPLEX-TS延續(xù)CPLEX在靜態(tài)環(huán)境中所求得的作業(yè)最優(yōu)執(zhí)行順序，而在考慮作業(yè)返工的情況下無(wú)法保證該執(zhí)行順序的最優(yōu)性. 因此TSD通過(guò)基于作業(yè)列表禁忌搜索框架進(jìn)一步優(yōu)化作業(yè)執(zhí)行順序，從而獲得最小的Eo均值.

表1 S21數(shù)值實(shí)驗(yàn)結(jié)果Tab.1 Numerical results of S21

注：Eo為模板計(jì)劃工期；G為Eo值與CPLEX方法Eo值之間差距；TCPU為各方法的運(yùn)算時(shí)間，下表同.

表2 S32數(shù)值實(shí)驗(yàn)結(jié)果Tab.2 Numerical results of S32

表3 S42數(shù)值實(shí)驗(yàn)結(jié)果Tab.3 Numerical results of S42

3.3.2 右移算法實(shí)驗(yàn)結(jié)果

本節(jié)實(shí)驗(yàn)通過(guò)生成工件質(zhì)量的隨機(jī)擾動(dòng)，并采用右移算法獲得調(diào)整后的裝配計(jì)劃來(lái)評(píng)價(jià)各方法所得模板計(jì)劃的優(yōu)劣性. 考慮到CPLEX方法事先未制定人員分配計(jì)劃，因此在采用右移方法時(shí)通過(guò)隨機(jī)規(guī)則為其安排裝配人員. 右移算法所求得的實(shí)驗(yàn)結(jié)果如表4～6所示.

在裝配計(jì)劃實(shí)際工期方面，雖然CPLEX方法求得的模板計(jì)劃工期最小，但在隨機(jī)環(huán)境下其平均實(shí)際執(zhí)行工期要大于CPLEX-TS和TSD，其原因在于不合理的人員分配計(jì)劃導(dǎo)致作業(yè)的裝配質(zhì)量降低，從而使得作業(yè)返工現(xiàn)象發(fā)生頻次增加，致使項(xiàng)目整體工期增加；而相較CPLEX-TS，TSD方法能夠通過(guò)基于作業(yè)列表禁忌搜索框架優(yōu)化作業(yè)的執(zhí)行順序，降低作業(yè)延期對(duì)項(xiàng)目整體工期的影響. 在偏差方面，在小規(guī)模算例中，CPLEX方法在隨機(jī)環(huán)境下的裝配計(jì)劃偏差最大，CPLEX-RANDOM方法最小. 隨著算例規(guī)模的增大，TSD方法求得裝配計(jì)劃偏差的增幅最小且在S42算例中為各方法的最小值，而其余方法均有較大的增幅.其原因在于CPLEX方法在生成模板計(jì)劃時(shí)未考慮到作業(yè)質(zhì)量對(duì)作業(yè)執(zhí)行時(shí)間的影響，因此在隨機(jī)環(huán)境下波動(dòng)較大的作業(yè)實(shí)際執(zhí)行時(shí)間使得裝配計(jì)劃偏差快速增加；對(duì)于CPLEX-RANDOM、CPLEX-TS和TSD，影響裝配計(jì)劃偏差的因素主要包括模板調(diào)度計(jì)劃的魯棒性和人員分配的合理性. 在算例規(guī)模較小時(shí)，模板調(diào)度計(jì)劃的魯棒性對(duì)裝配計(jì)劃偏差影響較大，導(dǎo)致CPLEX-RANDOM求解效果更為理想；隨著算例規(guī)模的增加，人員分配合理性影響逐漸增大，使得TSD求得的裝配計(jì)劃偏差表現(xiàn)更優(yōu).

表4 S21右移算法數(shù)值實(shí)驗(yàn)結(jié)果Tab.4 Numerical results of S21 h

注：Em為調(diào)整后裝配計(jì)劃的實(shí)際工期；Ed為裝配計(jì)劃與模板裝配計(jì)劃之間各作業(yè)開(kāi)始時(shí)間的偏差之和，下表同.

表5 S32右移算法數(shù)值實(shí)驗(yàn)結(jié)果Tab.5 Numerical results of S32 h

表6 S42右移算法數(shù)值實(shí)驗(yàn)結(jié)果Tab.6 Numerical results of S42 h

4 結(jié) 論

1)分析裝配人員水平、工件質(zhì)量等因素對(duì)實(shí)際飛機(jī)裝配作業(yè)質(zhì)量的影響，構(gòu)建飛機(jī)裝配質(zhì)量在作業(yè)間的傳遞耦合關(guān)系，并以歷史質(zhì)量數(shù)據(jù)為基礎(chǔ)構(gòu)造SVR預(yù)測(cè)模型. 通過(guò)在SVR預(yù)測(cè)模型中引入多輸出回歸方法，實(shí)現(xiàn)對(duì)多維度輸出數(shù)據(jù)的有效表達(dá).

2)針對(duì)時(shí)間決策和資源決策相互耦合的情況，提出兩階段循環(huán)迭代搜索算法. 算法上層在作業(yè)列表編碼的基礎(chǔ)上，通過(guò)構(gòu)建禁忌搜索框架來(lái)加強(qiáng)對(duì)作業(yè)列表的深度搜索能力；算法下層采用串行調(diào)度求解作業(yè)實(shí)際開(kāi)始時(shí)間，并通過(guò)內(nèi)嵌人員分配搜索模塊對(duì)人員組合進(jìn)行搜索，實(shí)現(xiàn)人員配置的優(yōu)化.

3)數(shù)值實(shí)驗(yàn)結(jié)果表明,SVR預(yù)測(cè)模型對(duì)實(shí)際飛機(jī)裝配質(zhì)量的預(yù)測(cè)具有良好的適用性；兩階段循環(huán)迭代搜索算法在隨機(jī)環(huán)境中具有良好的求解性能，說(shuō)明了該算法的有效性和可行性，能為飛機(jī)裝配過(guò)程構(gòu)建合理的前攝調(diào)度計(jì)劃.

4)未來(lái)可以從動(dòng)態(tài)調(diào)度的角度出發(fā)，進(jìn)一步研究零件加工質(zhì)量和裝配人員水平等質(zhì)量相關(guān)因素對(duì)飛機(jī)動(dòng)態(tài)調(diào)度計(jì)劃的影響.