考慮設備故障的魯棒調度計劃模板的建模優化

方 佳， 陸志強

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

飛機移動裝配線因其較高的裝配效率和相對穩定的裝配過程被越來越多的飛機制造企業所采納.飛機裝配是飛機制造過程中的重要環節，對飛機裝配過程中的作業實現科學的調度有助于提高飛機制造行業的生產效率并降低生產成本.

飛機移動裝配生產線的調度問題可以抽象為資源受限項目的調度問題.對確定性環境下的資源受限項目調度問題的研究已經比較充分，算法主要分為精確算法、啟發式算法和元啟發式算法[1-2].但確定性環境中的調度問題研究對作業工期、物料供應情況、機器設備狀態等的假設都較為理想化，不符合項目執行過程中干擾及不確定因素較多的實際情況.因此，近幾年的研究主要圍繞不確定環境下的調度問題展開[3].

為了解決不確定因素影響下的調度問題，現有文獻提出的方法主要有兩種，即反應式調度方法和前攝型調度方法.反應式調度方法的相關研究中，Elloumi等[4]在多模式資源受限項目調度問題的基礎上，考慮模式切換受干擾的場景，以項目執行總工期和穩定性評價指標為目標，建立了多目標模型并提出新的啟發式進化算法修復調度計劃.Paprocka等[5]建立了流水車間多目標模型，設計了一種混合多目標免疫反應調度算法以應對操作出現中斷的情況，為流水車間的動態調度研究提供了新的思路.

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

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

本文考慮裝配現場自動化機器設備的隨機故障以及修復對裝配作業計劃開始時間的影響，提出一種群體智能算法——依賴感知器的果蠅優化算法，為生成魯棒模板調度計劃提供了一定的思路.

1 問題描述及數學模型

1.1 問題描述

考慮機器設備故障與修復的飛機移動裝配線調度問題的假設與說明如下.

圖1 飛機移動裝配線布局示意圖

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

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

1.2 數學模型

構建考慮機器設備故障與修復的飛機移動裝配線調度問題的數學模型，此模型中的決策變量為0-1變量，即xji={0,1}, ?j∈J, ?ti∈D.如果作業j在時刻ti開始，則xji=1，否則xji=0.以最小化所有作業的懲罰值之和Z為目標函數，建立的數學模型如下.

(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 算法設計

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

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

2.1 代理指標的設計

目標函數Z是基于Nsce個場景來評價調度計劃的優劣的，基于場景的評價方式具有動態性，因此需要借助抽樣仿真，但直接將抽樣仿真嵌入算法來評價每個解的好壞會大大增加該算法的迭代尋優消耗時長.相比較而言，設計一個靜態的代理指標評價中間方案的優劣更加簡便而且快速.因此，只有在對比實驗部分才涉及抽樣仿真，算法主體部分不采用抽樣仿真的方式.基于Lambrechts等[14]設計的代理指標，設計與本文算法配套的代理指標如下式所示：

(11)

(12)

2.2 果蠅種群初始化

圖2 編碼以及解碼示意圖

2.3 窄域感知器搜索模塊

(13)

(14)

(15)

圖3 嗅覺搜索操作優化機制

對果蠅進行窄域嗅覺搜索操作的完整步驟如下：

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

圖4 窄域視覺搜索流程圖

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

2.4 寬域感知器搜索模塊

3 數值實驗

3.1 實例參數和實驗平臺

圖5 仿真實驗調度結果圖

在進行對比實驗之前，先通過預實驗收集了 1 200 個(Z,ZA)樣本對，每30對計算一個Pearson相關系數ξ，Pearson相關系數箱型圖如圖6所示.

圖6 皮爾遜相關系數箱型圖

由圖6可知，40個Pearson相關系數的均值為-0.61，且其中75%的值分布在區間[-0.79,-0.55]中，進一步說明了ZA與Z之間有較強的負相關性，驗證了代理指標設置的合理性.

3.2 不同作業規模仿真結果與禁忌搜索算法結果的對比

將PDFOA與文獻[14]中的禁忌搜索(TS)算法進行對比，對每個算例獲得的模板計劃取Nsce=100組完整的執行場景，并計算此算例的目標函數值Z.同一作業規模的算例進行5次實驗，每次實驗計算這一規模下10個算例所獲得的Z平均值，并統計算法所用的平均時間進行對比.

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

表1 小規模作業實驗結果對比

3.2.2大規模作業實驗結果對比 在作業規模為60,90和120的情況下，PDFOA相比TS算法在時間和結果上的優勢都較為明顯，實驗結果如表2所示.由表2可知，各作業規模下的5組實驗中均沒有出現GAP為負數的情況.隨著作業規模的增大，GAP值也有變大的趨勢，進一步體現出在大規模作業下PDFOA能夠在較短的時間內獲得魯棒性較高的模板計劃.

表2 大規模任務實驗結果對比

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

以上實驗通過比較GAP均值的方法驗證所提算法的有效性，但弊端在于個別表現特別優異的算例或實驗組會對整體均值產生影響進而干擾判斷.而表1和表2中，不同作業規模下的優勝比例基本都大于0.6，進一步說明了PDFOA的有效性.

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

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

圖7 單個算例在不同γ下的表現

3.3 不同作業規模仿真結果與其他智能算法結果的對比

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

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

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

表4 PDFOA與GA、IPSO算法在不同作業規模算例下的對比結果

圖8 3種算法下代理指標的收斂過程

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

4 結論

(1) 以飛機移動裝配線為實際應用背景，考慮設備的故障與修復對飛機裝配作業計劃穩定性可能產生的影響，為生成具有魯棒性的模板調度計劃提供了思路和方法.

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

(3) 后續將基于自動化設備的狀態進行調度，前端與機器學習結合實現數據驅動.