維修時點預測的動態(tài)車間調(diào)度問題

匡鵬　吳盡昭

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

關鍵詞：自回歸移動平均模型；設備故障率；遺傳算法；模擬退火算法；生產(chǎn)調(diào)度

中圖分類號：TP277.3

文獻標志碼：A

0引言

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

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

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

1問題描述

1.1原問題描述

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

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

1.2條件假設

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

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

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

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

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

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

2.3設備維修時點動態(tài)調(diào)整

2.3.1設備故障率預測

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

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

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

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

2.3.3設備加工時間不固定

由歷史數(shù)據(jù)分析知，設備的加工時間在區(qū)間內(nèi)小范圍地波動，數(shù)據(jù)趨勢服從指數(shù)分布。

2.4情況分析

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

3混合算法設計

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

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

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

3.1優(yōu)化庫的建立

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

3.2遺傳算法設計

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

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

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

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

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

4實驗結果分析

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

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

目前工廠中生產(chǎn)一件產(chǎn)品需要經(jīng)過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}}。

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

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

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

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

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

將設備的加工時間設定為隨機，維修時點按照本文預測的結果動態(tài)變化。維修時點是根據(jù)往常的設備故障率模擬出設備未來的維修時點，實際情況一般在預測維修時點的前后5個單位時間（本文采用單位為小時）內(nèi)波動，即預測的時間前后相差5個單位時間左右為正常維修時點。任務數(shù)有6個時，根據(jù)智能調(diào)度方法得出最優(yōu)排序：1—3—6—4—5—2；任務數(shù)為30時的最優(yōu)排序：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%。從數(shù)據(jù)上分析是相對穩(wěn)定的，說明在有維修情況下對整體任務的完成影響度是比較可靠的。

4.4故障率效果

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

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

5結語

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

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

參考文獻：

[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]李素粉，朱云龍，尹朝萬.具有隨機加工時間和機器故障的流水車間調(diào)度[J].計算機集成制造系統(tǒng)，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]黃亞平，王萬良，熊婧.基于改進蟻群算法的智能調(diào)度系統(tǒng)設計與開發(fā)[J].浙江工業(yè)大學學報，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]張揚，楊松濤，張香芝.一種模擬退火遺傳算法的傳感器網(wǎng)絡數(shù)據(jù)融合技術研究[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]馬存寶，李柯，包羽.故障時間觀測的機電系統(tǒng)可靠性估計[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]曾樑，周丹晨，周戰(zhàn)強.基于改進遺傳退火算法的生產(chǎn)智能調(diào)度系統(tǒng)[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]鄧輝，吳盡昭.線性半代數(shù)變遷系統(tǒng)的近似互模擬等價[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]劉紅軍，趙帥.一種基于混合遺傳算法的車間生產(chǎn)調(diào)度的研究[J].制造業(yè)自動化，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]趙衛(wèi).模擬退火遺傳算法在車間作業(yè)調(diào)度中的應用[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.）