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

匡鵬　吳盡昭

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

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

中圖分類號：TP277.3

文獻(xiàn)標(biāo)志碼：A

0引言

隨著工業(yè)4.0時代的到來，互聯(lián)網(wǎng)與工業(yè)的融合將完全顛覆現(xiàn)有模式，包括供應(yīng)鏈體系、生產(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è)中設(shè)備的故障率和維修率[2]越來越受關(guān)注，特別是在生產(chǎn)過程中導(dǎo)致訂單無法正常交付、工廠受到損失，因此工廠對于設(shè)備維修時點[3]的確定非常需要。以往的研究大多假設(shè)為理想的調(diào)度環(huán)境，但在實際的制造系統(tǒng)中，常常存在許多不確定的因素，如工件的加工時間不確定[4]、機器故障、緊急插單或者更改交貨期等。流水型企業(yè)中生產(chǎn)車間的優(yōu)化調(diào)度問題[5]已經(jīng)成為提高企業(yè)生產(chǎn)效率的核心問題。

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

1問題描述

1.1原問題描述

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

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

1.2條件假設(shè)

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

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

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

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

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

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

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

2.3.1設(shè)備故障率預(yù)測

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

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

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

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

2.3.3設(shè)備加工時間不固定

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

2.4情況分析

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

3混合算法設(shè)計

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

自適應(yīng)的遺傳模擬退火算法

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

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

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

3.2遺傳算法設(shè)計

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

2）計算適應(yīng)值。直接把目標(biāo)值Cmax作為適應(yīng)值，即：f=Cmax。

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

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

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

4實驗結(jié)果分析

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

4.1設(shè)備加工時間固定且不考慮設(shè)備維修

目前工廠中生產(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}}。

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

4.2設(shè)備加工時間固定且維修時點固定

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

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

4.3設(shè)備加工時間與維修時點都不固定

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

4.4故障率效果

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

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

5結(jié)語

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

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

參考文獻(xià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模型在設(shè)備故障預(yù)測中的應(yīng)用[J].科技信息（學(xué)術(shù)版），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ìn)蟻群算法的智能調(diào)度系統(tǒng)設(shè)計與開發(fā)[J].浙江工業(yè)大學(xué)學(xué)報，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ìn)研究[J].信息技術(shù)，2013（2）： 176-178. （SHI L P. Research on simulated annealing algorithm and improvement [J]. Information Technology， 2013（2）： 176-178.）

[10]張揚，楊松濤，張香芝.一種模擬退火遺傳算法的傳感器網(wǎng)絡(luò)數(shù)據(jù)融合技術(shù)研究[J].計算機應(yīng)用研究，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)強.基于改進(jìn)遺傳退火算法的生產(chǎn)智能調(diào)度系統(tǒng)[J].計算機工程與設(shè)計，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].吉林大學(xué)學(xué)報（工學(xué)版），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)度中的應(yīng)用[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.）