陸志強， 朱宏偉， 廖怡娜

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

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

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

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

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

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

1.1 問題描述

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

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

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

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

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

1.2 數(shù)學模型

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

(1)

(2)

(3)

(4)

(5)

(6)

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

(7)

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

(8)

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

2 算法設計

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

2.1 SVR預測模型

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

圖2 多輸出目標SVR模型訓練及預測過程Fig.2 Training and prediction processes of multi-output SVRmodel

綜上所述，多輸出SVR預測模型的訓練主要包含如下步驟：

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

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

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

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

鑒于考慮質量預測前攝調度問題耦合了時間和資源兩類決策，本文采用兩階段循環(huán)迭代搜索算法構建模板計劃. 其中，考慮到禁忌搜索算法在求解效率和搜索深度的優(yōu)勢，兩階段算法在上、下兩層中均采用禁忌搜索算法來實現(xiàn)時間和資源的決策. 算法上層借鑒陸志強等[2]求解靜態(tài)RCPSP問題時采用的作業(yè)列表編碼方法設計禁忌搜索框架對作業(yè)執(zhí)行順序進行深度搜索；鑒于傳統(tǒng)串行調度(serial schedule generation scheme, SSGS)在解碼時缺乏對人員合理安排的機制，下層在傳統(tǒng)串行調度基礎上內嵌人員分配搜索模塊，通過對人員分配編碼進行深度搜索來獲取較優(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è)編號，編碼過程要求：1)第一個編碼位和最后一個編碼位分別為虛擬初始作業(yè)和虛擬結束作業(yè)；2)后一編碼位中不得包含前一編碼位的直接或間接前道作業(yè). 只有前一編碼位的作業(yè)被執(zhí)行完成后，后一編碼位的作業(yè)才可以安排開始.

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

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

算法具體步驟如下：

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

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

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

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

步驟5若達到終止條件，則輸出Sbest；否則，轉步驟2.

2.2.2 內嵌人員分配搜索模塊串行調度

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

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

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

算法具體步驟如下：

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

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

步驟4采用SSGS生成模板計劃，記模板計劃工期為TCk. 若Tbest>TCk，則令Tbest=TCk.

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

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

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

步驟8若達到終止條件，則輸出Tbest；否則，轉步驟5.

3 實例應用及分析

3.1 實驗平臺

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

3.2 SVR預測模型效果驗證

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

圖5 SVR預測模型準確率Fig.5 Accuracy of SVR prediction model

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

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

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

3.3.1 模板調度計劃實驗結果

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

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

表1 S21數(shù)值實驗結果Tab.1 Numerical results of S21

注：Eo為模板計劃工期；G為Eo值與CPLEX方法Eo值之間差距；TCPU為各方法的運算時間，下表同.

表2 S32數(shù)值實驗結果Tab.2 Numerical results of S32

表3 S42數(shù)值實驗結果Tab.3 Numerical results of S42

3.3.2 右移算法實驗結果

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

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

表4 S21右移算法數(shù)值實驗結果Tab.4 Numerical results of S21 h

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

表5 S32右移算法數(shù)值實驗結果Tab.5 Numerical results of S32 h

表6 S42右移算法數(shù)值實驗結果Tab.6 Numerical results of S42 h

4 結 論

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

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

3)數(shù)值實驗結果表明,SVR預測模型對實際飛機裝配質量的預測具有良好的適用性；兩階段循環(huán)迭代搜索算法在隨機環(huán)境中具有良好的求解性能，說明了該算法的有效性和可行性，能為飛機裝配過程構建合理的前攝調度計劃.

4)未來可以從動態(tài)調度的角度出發(fā)，進一步研究零件加工質量和裝配人員水平等質量相關因素對飛機動態(tài)調度計劃的影響.