維修時點預測的動態車間調度問題

匡鵬　吳盡昭

摘要：針對制造業中生產計劃的不確定問題，提出一種維修時點預測與自適應的遺傳模擬退火算法相結合的優化調度方法。該方法首先利用差分自回歸移動平均模型預測設備未來的故障率，然后借助電氣設備的威布爾（Weibull）分布模型逆向求出設備未來故障發生時刻，最后將此作為約束條件，利用自適應的遺傳模擬退火算法解決傳統的生產調度問題。結合工廠實際情況，主要分析了設備有無維修的隨機調度問題，以最小化最大完工時間為目標，獲取每一個任務的調度計劃以及每一臺設備的維修時點，確定出最佳調度方案。實驗表明自適應的遺傳模擬退火算法的性能較好。在河北某工廠的生產車間中，設備在運行調度方法后三個月的平均故障率比運行前相對降低了3.46%。

關鍵詞：自回歸移動平均模型；設備故障率；遺傳算法；模擬退火算法；生產調度

中圖分類號：TP277.3

文獻標志碼：A

0引言

隨著工業4.0時代的到來，互聯網與工業的融合將完全顛覆現有模式，包括供應鏈體系、生產體系以及售后體系。這就意味著在生產環節將實現更大的柔性和可變性、模塊化與自主性以及自主產品與自主生產系統等。因此要實現工廠的智能生產、提高智能工廠的運行效率，智能調度系統就必須提供優化決策。生產調度[1]是目前生產管理中最為薄弱的環節，也是最困難的一環，已成為目前計算機集成制造系統研究中的一個瓶頸。

其次，制造業中設備的故障率和維修率[2]越來越受關注，特別是在生產過程中導致訂單無法正常交付、工廠受到損失，因此工廠對于設備維修時點[3]的確定非常需要。以往的研究大多假設為理想的調度環境，但在實際的制造系統中，常常存在許多不確定的因素，如工件的加工時間不確定[4]、機器故障、緊急插單或者更改交貨期等。流水型企業中生產車間的優化調度問題[5]已經成為提高企業生產效率的核心問題。

雖然目前智能調度的研究與實踐不斷取得新的進展，但是數據的完整性缺乏，導致了很多研究只是關注系統研究以及算法優化，鮮有關注設備層面的優化，沒有考慮設備的負載率，沒有將機器預防性維修與生產調度相結合。設備運行制定合理的動態維修方案才是生產車間所需要的?；谝陨戏治霰疚闹攸c討論將設備的維修時點作為一個因素考慮到生產調度中，結合實際的車間安排確定出最佳的設備維修時點以及生產任務。

1問題描述

1.1原問題描述

在傳統的生產車間內，成品必須經過每一道工序，每一道工序在同一類型的設備上加工。只有設備正常運轉，成品才能按時按量交付給客戶。傳統工廠中通過設備的月度維修或季度維修來維持設備的正常運轉，一般都是車間管理人員基于實踐經驗或有限的計算分析來確定每個月或每個季度的維修時點，實際效果很難保證設備的正常運轉。目前對不確定問題主要采用隨機變量、擬合、時間序列分析以及統計學等進行描述。用隨機變量描述不確定因素，需知道其概率分布函數，由設備歷史加工數據分析出設備的加工時間服從指數分布。時間序列分析是根據系統觀測得到的時間序列數據，通過曲線擬合和參數估計來建立數學模型的理論和方法。對設備的歷史故障率數據采用時間序列分析模擬出差分自回歸移動平均模型（AutoRegressive Integrated Moving Average model， ARIMA）[6]。對設備歷史維修時點分析滿足威布爾（Weibull）分布模型，通過對參數進行有效估計，確定維修時點函數。因此本文采用隨機變量、時間序列分析以及統計學的方法對設備維修時點進行預測，從而達到降低設備故障率的目標，促進生產。

本文在充分考慮制造型企業車間中的不確定因素的前提下，建立不確定車間調度問題模型。目前對于不確定調度問題，主要采用遺傳算法[7]、蟻群算法[8]、模擬退火算法[9]以及混合算法[10]等進行優化。本文針對車間調度問題模型，采取兩種不同的交叉和變異策略設計出了基于自適應模擬退火遺傳算法。假定情境為m臺機器n個不同的任務，每個任務有m道工序，以相同的順序在m臺機器上加工。對于生產調度問題約束條件為：工件在同一類型的設備上只能被加工一次；任何時刻某一臺機器只能加工一個工件；每一個產品的加工過程不允許插隊加工。在實際生產中，本文通過此算法優化隨機流水車間調度問題。仿真結果顯示，改進算法具有更好的優化性能，其效果可行有效，能對實際生產起到一定的指導作用。

1.2條件假設

1）假設工件的首道工序的實際開始時間為0；

2）假設每道工序在指定的機器類型上加工；

3）假設每一臺設備同一時刻只能加工一件工件；

4）假設每一工件的工藝路線是已知的；

5）假設任何工件各道工序加工的前提是該工件前一道工序必須加工完成；

6）假設每臺設備每個月必須維修一次，且維修時長確定。

2.3設備維修時點動態調整

2.3.1設備故障率預測

借助可編程邏輯控制器（Programmable Logic Controller， PLC）數據庫獲取的設備歷史故障率數據，分析設備故障的預測，從而為設備維修策略提供初始數據，最終提高設備利用率。本文研究的故障率數據取自中間數據庫，中間庫是對不同設備的PLC數據庫進行抽取來得到有效的數據。針對復雜的數據，本文主要利用時間序列的方法建立預測模型，把設備歷史故障率數據看成時間序列的一組動態數據，這些動態數據是非平穩的，需要考慮對序列進行平穩化處理。本文利用差分的方法對數據進行平穩化處理，建立ARIMA模型進行預測分析。利用隨機序列的自相關和偏相關函數圖判斷ARIMA模型的階次p和q的取值范圍。

圖2中表明數據的平穩性較好。對此數據進行自相關函數和偏相關函數分析，由圖3中的自相關圖可以看到，在第8步滯后的自相關系數顯著不為零，而第8步之后都接受“系統為零“的假設，故有在圖2中，在顯著性水平α=0.05時，接受原假設系統為零的95%的置信區間。由圖3知在第8步之后都接受系數為零的假設，得出

0≤q≤8。同理，由偏相關函數圖可知0≤p≤11。利用赤池信息量準則（Akaike Information Criterion， AIC）判定較為理想的模型。通過比較得模型ARIMA（7，6）的AIC值是最小的，即ARIMA（7，6）模型是更為理想的預測模型。

通過理想模型計算第81個故障率數據的預測值，為7.637%，利用遞推的方法可以實現對后19個數據進行預測。預測出的后20個數據與實際的20個數據的對比如圖4所示。計算出預測值與實際值的擬合優度R2=0.6003，實驗結果顯示效果是可觀的。

2.3.3設備加工時間不固定

由歷史數據分析知，設備的加工時間在區間內小范圍地波動，數據趨勢服從指數分布。

2.4情況分析

通過對設備維修時點的三種情況分析可以發現，沒有維修時點是理想的狀況。工件最小完工時間是否無限接近理想狀況是本研究評判的一個標準。因為實際情況只要涉及設備維修一定會占用設備運轉的時間，也會對當天的產量有影響，以致于訂單的交貨期不得不向后延期。因此本文將設備的維修時點設定為動態可變，以此保證設備的運轉更符合實際情況。實驗不斷地對模型的參數進行調節，使得維修時點被合理地安排，既可以保證訂單的按時完成，同時也能提高設備的運行效率。

3混合算法設計

以最大完工時間Cmax為目標，采用遺傳算法和模擬退火算法相結合的方式，提出了一種

自適應的遺傳模擬退火算法

（Adaptive algorithm of Genetic Algorithm and Simulated Annealing algorithm， AGASA），該算法將模擬退火算法嵌入到自適應遺傳算法的循環體中，以利用模擬退火算法具有較強的局部搜索能力、并且能夠使搜索過程避免陷入局部最優解的特點。

3.1優化庫的建立

優化庫建立的目的主要是存儲優秀種群，本文設計了三種不同類型的庫：第一種是初始種群庫，用來存儲各種狀態下最后一次迭代所產生的種群；第二種是分類索引庫，用來將每次迭代后產生的種群劃分為若干類，并以此時的狀態、溫度作為索引；第三種是優化結果庫，用來存儲每次優化計算后所得到的溫度調節參數和最優解。

3.2遺傳算法設計

1）初始值。采用自然數編碼，用一段順序碼表示工件處理的優先級順序，數字表示工件號。初始種群一部分采用隨機方法產生，另一部分利用機器學習[12]方法產生，以提高初始種群的適應性。

2）計算適應值。直接把目標值Cmax作為適應值，即：f=Cmax。

3）遺傳操作。交叉操作有以下兩類：

第一類在第二個任務列中隨機選擇一個交叉區域，將第二個任務列中的交叉區域加到第一個任務列對應的位置，刪除第一個任務列中已存在第二個任務列的交叉區域中出現過的工件序號。

第二類對父代以適應度函數值進行排序，適應度小的與適應度小的配對，適應度大的與適應度大的配對；然后利用混沌序列確定交叉點的位置，最后對確定的交叉項進行交叉。

4實驗結果分析

在本文的實驗中，實驗數據采集河北某工廠的歷史數據。根據歷史數據設定設備的加工時間在區間[5，10]（單位：min）內隨機波動，每一個工件都需要經過5道工序。在算法設計中取種群數為40，交叉概率為0.65，變異概率為0.15，t0=100℃，λ=0.95，Pr=0.93，N=1，終止溫度為0.0001℃。

4.1設備加工時間固定且不考慮設備維修

目前工廠中生產一件產品需要經過5道工序，實驗選取10個待加工工件，已知工件i在機器j上的加工的時間為T，初始化為：T={tij|1≤i≤n，1≤j≤m}={{8，6，9，5，8}，{11，5，6，6，9}，{8，7，5，8，6}，{12，5，5，7，5}，{9，6，7，6，8}，{10，10，8，8，7}，{9，8，6，9，5}，{11，5，7，8，8}，{10，9，5，6，5}，{8，7，5，10，9}}。

實驗結果表明此問題的最優值結果為75，工件的加工次序依次為：1—5—2—10—8—6—3—4—7—9。即5臺機器同時加工，將這10個工件全部加工完畢最快需要75min。為此本文將75定義為最優值，將76定義為次優值。表1是混合遺傳模擬退火算法、遺傳算法與模擬退火算法在解決此類問題時的測試結果。

4.2設備加工時間固定且維修時點固定

流程工廠一般都是選擇一個固定的時間按照設備類型選擇某一個時間段進行設備維修。實驗中假設所有設備統一維修，且需要單位時間（假設為1）進行維修。需要對下一道工序的設備維修的時間與下一個工件的開始加工時間進行判斷。通過混合算法算出此問題的最優值結果為75，次優值為76，然后通過反復的迭代，表2表明混合算法的效果較好。

對比表1和表2可以看出，當設備需要維修時，有可能不影響全部工件的加工，如果設計的搜索算法能找到此時刻，就達到了本文的目的。通過AGASA的搜索，最優值的比例降低了13.79%，效果還是比較可觀的。

4.3設備加工時間與維修時點都不固定

將設備的加工時間設定為隨機，維修時點按照本文預測的結果動態變化。維修時點是根據往常的設備故障率模擬出設備未來的維修時點，實際情況一般在預測維修時點的前后5個單位時間（本文采用單位為小時）內波動，即預測的時間前后相差5個單位時間左右為正常維修時點。任務數有6個時，根據智能調度方法得出最優排序：1—3—6—4—5—2；任務數為30時的最優排序：15—25—30—9—13—24—7—12—27—1—3—6—18—19—21—4—5—10—11—16—17—22—23—28—29—2—8—14—20—26。

通過表3分析得知，有無維修的方差在同種情況下的變化率分別為11.05%、10.06%、15.22%。從數據上分析是相對穩定的，說明在有維修情況下對整體任務的完成影響度是比較可靠的。

4.4故障率效果

在生產車間實際運行本文策略三個月之后，通過圖6數據可以發現設備的故障率得到了一定程度的下降。將本文的策略在工廠中實踐之后，6月故障率確實有明顯上升，這主要是由于設備的工作量比之前要大，設備預測的效果也不是很好，但是實驗參數經過調整之后，后面2個月的故障率有明顯下降。

運行本文策略后三個月的運行結果與未運行該策略的前三個月相比，設備的平均故障率相對降低了3.46%。

5結語

本文首先通過PLC采集河北某膠管工廠設備的故障率數據，并設計了一種預測設備故障發生時刻的模型，并通過模擬實際的數據，契合效果較好。本文結合遺傳算法和模擬退火這兩種算法的優缺點，提出了一種自適應的智能調度算法，并分析了此算法在車間調度問題中的應用，結果表明該算法能更好地繼承父代的優良特征產生的新解，而且該算法結合設故障率預測方法應用到實際工廠中也取得了較好的效果。

本文對設備的故障模擬效果還不是最佳，由于車間設備的故障影響因子非常復雜，維修時長也不確定，因此仍然有許多問題需要進一步研究和完善。車間調度理論模型是在一些假設情況下得到的，與實踐之間也還有一些差距；而且生產車間的生產線增加，調度方案是否仍具有穩定的可擴展性也是下一步要研究的問題。

參考文獻：

[1]JIN Y L， JIANG Z H， HOU W R. Multi-objective integrated optimization research on preventive maintenance planning and production scheduling for a single machine [J]. The International Journal of Advanced Manufacturing Tcchnology， 2008， 39（9）： 954-964.

[2]WEINSTEIN L， CHUNG C-H. Integrating maintenance and production decisions in a hierarchical production planning environment [J]. Computers and Operation Research，1999， 26（10/11）： 1059-1074.

[3]ALCAIDE D， RODRIGUEZ-GONZALEZ A， SICILIA J. An approach to solve the minimum expected makespan flow-shop problem subject to breakdowns [J]. European Journal of Operation Research， 2002， 140（2）： 384-398.

[4]ALLAHVERDI A， MITTENTHAL J. Scheduling on a two-machine flow shop subject to random breakdowns with a makespan objective function [J]. European Journal of Operation Research， 1995， 81（2）： 376-387.

[5]李素粉，朱云龍，尹朝萬.具有隨機加工時間和機器故障的流水車間調度[J].計算機集成制造系統，2005，11（10）：1425-1429. （LI S F， ZHU Y L， YIN C W. Flow shop scheduling with stochastic processing times and machine breakdowns [J]. Computer Integrated Manufacturing Systems， 2005， 11（10）： 1425-1429.）

[6]卞曉靈.ARIMA模型在設備故障預測中的應用[J].科技信息（學術版），2008（8）：42-45. （BIAN X L.The application of equipment failure prediction ARIMA model[J].Science & Technology Information， 2008（8）： 42-45.）

[7]PERKGOZ C， AZARON A， KATAGIRI H， et al. A multi-objective lead time control problem in multi-stage assembly systems using genetic algorithms [J]. European Journal of Operational Research， 2007， 180（1）： 292-308.

[8]黃亞平，王萬良，熊婧.基于改進蟻群算法的智能調度系統設計與開發[J].浙江工業大學學報，2010，38（3）：251-256. （HUANG Y P， WANG W L， XIONG J. Design and implementation of intelligent scheduling system based on improved ant colony algorithm [J]. Journal of Zhejiang University of Technology， 2010， 38（3）： 251-256.）

[9]石利平.模擬退火算法及改進研究[J].信息技術，2013（2）： 176-178. （SHI L P. Research on simulated annealing algorithm and improvement [J]. Information Technology， 2013（2）： 176-178.）

[10]張揚，楊松濤，張香芝.一種模擬退火遺傳算法的傳感器網絡數據融合技術研究[J].計算機應用研究，2012，29（5）：1860-1866. （ZHANG Y， YANG S T， ZHANG X Z. Research on wireless sensor networks data aggregation on simulated annealing genetic algorithm [J]. Application Research of Computers， 2012， 29（5）： 1860-1866.）

[11]馬存寶，李柯，包羽.故障時間觀測的機電系統可靠性估計[J].機械與電子，2012（9）：3-6. （MA C B， LI K， BAO Y. Reliability estimation of mechanical and electrical system based on the observed failure time [J]. Machinery & Electronics， 2012（9）： 3-6.）

[12]YANG Z， QI C. Preventive maintenance of a multi-yield deteriorating machine： using reinforcement learning [J]. System Engineering — Theory & Practice， 2013， 33（7）： 1647-1653.

[13]NOURELFATH M， CHTELET E. Integrating production，inventory and maintenance planning for a parallel system with dependent components [J]. Reliability Engineering and System Safety， 2012， 101： 59-66.

[14]FITOUHI M-C， NOURELFATH M. Integrating noncyclical preventive maintenance scheduling and production planning for a single machine [J]. Reliability Engineering and System Safety， 2012， 136（2）： 344-351.

[15]MADUREIRA A， PEREIRA I. Intelligent bio-inspired system for manufacturing scheduling under uncertainties [C]// Proceedings of the 2010 10th International Conference on Hybrid Intelligent System. Piscataway， NJ： IEEE， 2010： 109-112.

[16]曾樑，周丹晨，周戰強.基于改進遺傳退火算法的生產智能調度系統[J].計算機工程與設計，2011，32（10）：3504-3506. （ZENG L， ZHOU D C， ZHOU Z Q. Intelligent production scheduling system based on improved genetic annealing algorithm [J]. Computer Engineering and Design， 2011， 32（10）： 3504-3506.）

[17]鄧輝，吳盡昭.線性半代數變遷系統的近似互模擬等價[J].吉林大學學報（工學版），2013，43（4）：1052-1058. （DENG H， WU J Z. Approximate bisimulation for linear semi-algebraic transition systems[J].Journal of Jilin University （Engineering and Technology Edition）， 2013， 43（4）： 1052-1058.）

[18]劉紅軍，趙帥.一種基于混合遺傳算法的車間生產調度的研究[J].制造業自動化，2011（17）：33-35，59. （LIU H J， ZHAO S. Study on job-shop scheduling based on hybrid genetic algorithm [J]. Manufacturing Automation， 2011（17）： 33-35，59.）

[19]趙衛.模擬退火遺傳算法在車間作業調度中的應用[J].計算機仿真，2011，28（7）：361-364. （ZHAO W. Job-shop scheduling based on genetic algorithm and simulated annealing algorithm [J]. Computer Simulation， 2011， 28（7）： 361-364.）