考慮周期預防性維護的異速并行機集成調度研究

江才林，陸志強，崔維偉

（1.同濟大學機械與能源工程學院，上海201804；2.上海交通大學機械與動力工程學院，上海200240）

考慮周期預防性維護的異速并行機集成調度研究

江才林1，陸志強1，崔維偉2

（1.同濟大學機械與能源工程學院，上海201804；2.上海交通大學機械與動力工程學院，上海200240）

針對異速并行機系統，考慮機器具有周期預防性維護的不可用約束，建立生產調度與預防性維護集成優化的混合整數規劃模型。基于改進LPT的機器負載均衡技術與基于最小裝箱松弛法的單機調度優化算法，設計了有效的啟發式算法HCA，與Cplex的數據試驗比較表明，對于中小規模問題其解與最優解或低界的百分比誤差小于10%。設計了結合裝箱算法的混合遺傳算法HGA，與HCA對比的數據試驗表明，對于大規模問題HGA表現更加優異。通過與獨立決策比較的數據實驗證明了生產調度與設備維護的聯合決策模型效果更優，可有效協調車間生產與維修的總體計劃。

異速并行機調度；預防性維護；整數規劃；啟發式算法；混合遺傳算法

生產實際中隨著設備老化，機器需要預防性維護以改善機器性能或者故障后維修以恢復機器功能。由于定期執行預防性維護可降低設備發生意外故障的概率以提高系統的穩定性，近年來集成預防性維護策略的生產調度得到了研究者的普遍關注。根據計劃期內維護的次數不同，研究主要分為2類：一類是在計劃期內設備僅有一次維護，另一類是在計劃期內設備需要進行多次周期性維護。對于第1類研究，針對單機系統，一般假設工件不可中斷，研究各個不同調度目標如makespan等，提出各類啟發式如SPT等并證明其誤差邊界或者設計分支定界等精確算法求解［1-3］。對于并行機系統，主要有各個機器需要同時進行預防性維護，或者其中一臺進行預防性維護2種假設，求解方法為提出相應啟發式算法［4-6］。對于第2類研究，針對單機系統，文獻［7］考慮計劃期內具有多個預防性維護，建立了整數規劃模型。在此基礎上，文獻［8-12］研究了機器惰化效應，學習效應、計件維護以及柔性時間窗維護的拓展問題。文獻［13］首先將維修成本、makespan、加權完成時間以及加權總延遲時間作為優化目標，采用多目標遺傳算法進行優化。文獻［14］考慮設備的失效函數，以總成本最小為目標。針對并行機系統，有學者分別研究了2臺同型機和m臺同型并行機的調度問題，并提出相應的改進啟發式規則［15-16］。文獻［17］則研究了的帶有近似周期預防性維護的調度問題，目標為最小化最后一個維護活動的完成時間，證明其啟發式算法的界小于2T＇／T。

從以上文獻綜述可以看到，考慮機器具有周期預防性維護的可用度約束，單機調度文獻較多而并行機調度文獻有限，且系統為同速并行機。實際車間中由于機器屬性不同或機器新舊差異，導致其工件加工速率、預防性維護的周期以及維護所需時間均不同。本文旨在考慮異速并行機系統內各機器具有不同周期的周期性不可用約束，以最小化工件最大完工時間為目標，建立生產調度與設備維護的聯合優化數學規劃模型，并設計有效啟發式算法對問題進行優化求解。

1 問題描述

將含有n個工件的工件集J＝｛J1，J2，…，Jn｝分配到m臺機器M＝｛M1，M2，…，Mm｝上加工，目標為最小化工件的最大完工時間。所有工件在零時刻到達，工件基本加工時間為（i＝1，2，…，n），工件在加工過程中不允許中斷；機器Mj加工速率為sj（i＝1，2，…，m），工件Ji的實際加工時間為＝／sj；機器需要周期性預防性維護，2次維護的間隔時間為Tj（i＝1，2，…，m），維護時間長度為tj（i＝1，2，…，m）。按照調度三元組表示法，問題可記為Qm／pm－nr／Cmax。圖1為示例問題甘特圖。

由于各個機器需要進行周期預防性維護，一個完整調度方案應包含工件的加工順序和維護位置2個部分。若將2個預防性維護之間的工件集合稱為一個批次，用Bjk表示機器j的第k加工批次的所有工件集合，則對應于這個批次的工件有其相應的開始時間以及完工時間。因此一個調度方案π是由m個子集πj（i＝1，2，…，m）構成，每個子集為工件批次集合和維護的組合πj＝（Bj1，PMj，Bj2，PMj…Bjkj），其中PMj代表機器j的維護時段，kj表示機器j的加工批次序號。用Pjk表示機器j的第k加工批次內所有工件的加工時間總和，用Gjk表示機器j的第k加工批次內的松弛時間，則有Gjk＝Tj－Pjk。

圖1 考慮周期預防性維護的異速并行機調度示例Fig.1 An example of uniform machine scheduling with periodic maintenance

模型決策變量：xijk為0／1變量，如果工件i在第j機器第k加工批次加工，則取1，否則取0；yjk為0／1變量，如果機器j的第k加工批次有加工的工件，則取1，否則取0；zjk為0／1變量，如果機器j的第k加工批次為最后一個有加工工件實批次，則取1，否則取0。M為無窮大的正整數。約束（1）表示并行機系統的最大完工時間為所有機器完工時間的最大值；約束（2）表示每個工件僅由一臺確定的機器加工一次；約束（3）表示若此批次有加工工件為“實批次”，則此批次的工件數量為1～n；約束（4）保證了當第j機器的第k加工批次為實批次，則之前的k－1加工批次也必為實批次；約束（5）、（6）表示分配到機器各個批次工件加工時間總和小于維護周期T；約束（7）、（8）表示當第j機器的第k加工批次為其最后一個實批次，則后續所有批次均為沒有加工工件的“虛批次”；約束（9）表示每臺機器至少存在一個實批次；約束（10）表示各個機器的最大完工時間由最后一個實批次的加工時間總和及其加工批次數量決定。

上述數學模型具有較好的擴展性，對于不同維護策略下的并行機調度問題，可通過相關變量的調整獲得。例如，對于同速型的具有周期預防性維護的并行機調度問題Pm／pm－nr／Cmax只需要把約束（5）中的sj設置為1即可。

2 算法設計

由于此問題的強NP難性質，無法獲得多項式時間的精確算法，雖可用Cplex等商用軟件進行求解，但僅能求解小規模問題，無法在有效時間內解決大規模問題。本文提出基于改進LPT規則與最小裝箱松弛法的構造型啟發式算法HCA以及結合裝箱算法的混合遺傳算法HGA，可快速有效的解決此組合優化問題。

2.1 啟發式算法HCA

由于機器具有可用度約束，本問題可以分解為2個子問題：1）工件分配即機器選擇問題，應使得機器的負載均衡化。對于這類問題，當不考慮機器可用度時，LPT［1］規則為較好的啟發式規則，其是指在零時刻將m個最長的工件分配到m臺機器。此后，任一臺機器空閑，剩下的工件中加工時間最長的將分配給這臺空閑機器；2）當工件分配到機器后的單機工件排序問題。由約束（10）可知，機器Mj上，當機器具有最少加工批次以及最后加工實批次的工件加工時間最少時獲得問題的最優解。由此，問題轉化為變型的一維裝箱問題。對于這類問題，由Gupta等提出的最小裝箱松弛法（minimum bin slack，MBS）［18］采用遞歸方法在迭代的過程中不斷減少非最后一個箱子的松弛量，使箱子的總數量減少的同時也降低最后一個箱子的容量。HCA首先通過改進LPT規則將工件均衡分配到各個機器上；繼而將分配到機器的工件按照MBS規則重新排列使單機松弛時間最小，實現單臺機器的局部優化；隨后將每臺機器的最后一批工件與其他機器的非最后一批工件進行交換，通過局域搜索實現各臺機器間的平衡優化；最后將所有機器的最后一個加工批次的所有工件作為新工件集J＇，轉化為沒有可用度約束的小規模并行機調度問題并采用CPLEX求解，進一步均衡各臺機器以提升解的質量。具體步驟如下：

1）生成初始調度方案。

①將工件集J按照加工時間長度降序排列，形成優先列表集合L＝｛J1，J2，…，Jn｝。

②將Ji按照列表L順序逐一安排到能將其最先完工的機器上。即針對每臺機器Mj，搜索工件Ji的最早允許加工時間為，并計算其完工時間，將工件分配到可以最早完工的機器上，生成一個初始調度方案π0＝｛，，…，｝。

2）對初始調度方案π0＝｛，，…，的每一個子集進行MBS重新排列得到一個新的調度方案π1＝｛，…，｝。

3）對新調度方案進行鄰域交換以進一步改善。

①根據調度π1，機器Mj共包含kj個加工批次，集合記為Bj，Gjk為Mj的第k個批次的松弛時間。求得各機器的完工時間Cmjax，并記完工時間最長的機器為Ml。

②Ml的最后一個批次的工件數量為nl，并將工件按照加工時間降序排列，記J［i］為該批次的第i個工件。

③令i＝1。

④在機器集合｛M／Ml｝中，按照機器編號依次搜索機器Mj，在Mj中按照批次編號依次搜索各批次的最短加工時間工件J*，若交換J［i］、J*后不會違反Gjk約束，則交換兩工件并轉入⑤；若遍歷結束之后沒有交換成功，轉入⑥。

⑤工件交換后，得到新調度π*，π*→π1，轉入①。

⑥令i＝i＋1，若i≤nl，則轉入④；否則轉入步驟4）。

4）根據調度π1，將各臺機器的最后一批工件取出，作為一個新的工件集J＇，將每臺機器的前kj－1加工批次的結束時間作為機器的釋放時間，此時轉化為不帶可用度約束的小規模純調度問題，建立模型并導入Cplex求得最終解，算法結束。

為了進一步改善大規模下解的質量，本文設計了混合遺傳算法HGA如2.2節所示。

2.2 混合遺傳算法HGA

2.2.1 染色體編碼與初始種群生成

選用實數編碼，染色體的長度為n＋m－1，用－1～（－m＋1）作為劃分不同機器的標識。圖2為將9個工件分配到3臺機器上加工的一條染色體示例。種群規模設為100，為保證種群多樣性，采用隨機生成的方法產生初始種群。

圖2 編碼示例Fig.2 An example of coding

2.2.2 解的改進

如圖2所示，任一條染色體均包括m臺機器的工件加工序列。對于機器Mj，預防性維護時間段已知，將各工件依次插入其最早允許加工的時間間隙內，可求得對應機器的最大完工時間。由2.1節子問題2可知，在工件分配到機器后該問題轉化為變型的一維裝箱問題，而MBS和降序首次適應算法（first fit decreasing，FFD）［15］均是較好的求解裝箱問題算法，其中FFD是指將物品按照體積大小進行降序排列，然后按照順序將物品放到第一個能裝下它的箱子去。因此在GA的種群進化過程中，對每個新個體均執行如下Education操作，對個體進行改進。

Education：針對染色體中各個機器Mj（i＝1，2，…，m）的工件序列，將其所有工件分別按照FFD、MBS規則重新排列得到、，計算3個序列的Cmjax并取最小值的工件排序為最終序列πj，繼而將所有機器的πj組合為新染色體。

2.2.3 遺傳算子

由于本文采取實數編碼方式，選擇順序交叉法對2個染色體進行交叉操作，選取互換變異進行變異操作。遺傳算法中交叉概率一般取0.4～0.99，變異概率一般取為0.000 1～0.1。通過預實驗調整，本算法選取交叉概率Pc＝0.8，變異概率Pm＝0.1。

2.2.4 適應度函數與種群進化機制

本文選取f（x）＝1／z作為適應度函數并進行指數尺度轉換f＇（x）＝exp［（n＋m）f（x）］；通過輪盤賭方式進行選擇操作，假設f（xi）為第i染色體的適應度值，染色體數量為N，則個體被選中的概率為；采用精英策略，使每一代最優個體能不參與交配直接保留下一代中。

3 仿真實驗

本文運用優化軟件ILOG CPLEX 12.1對線性整數規劃模型進行求解，使用Visual C＃平臺實現兩類啟發式算法，仿真環境為內存2.0 GB、主頻2.1 GHz的便攜式計算機。

3.1 算法驗證

本文中，將2類算法結果Ch與最優解Co的百分比誤差e＝（Ch－Co）·100／Co以及算法的運行時間作為指標來評估算法性能，并首先測試構造型啟發式算法HCA的性能。考慮到不同問題規模以及參數設置可能對算法結果產生影響，參照文獻［7］中的調度問題算例生成方法并進行適當調整，生成如下測試算例：工件規模n∈［20，30，50，100，200，500，1 000］；機器規模m∈［2，3，5，10，20，30，50］；工件的加工時間pi服從［10，30］的均勻分布；每種問題規模隨機生成10組不同算例。在參數設置時，對于機器的加工速率參數分別設置sj∈［1.0，2.0］、sj∈［1.0，1.5］；預防性維護周期參數選取Tj設置；預防性維護時間長度參數也有tj＝Tj、tj＝Tj／5、tj＝Tj／10這3種設置，則共有18種參數設置。采用控制因子法，即在測試機器加工速率sj對算法影響時，對于每個sj將9種參數設置下共90個隨機算例的平均值作為輸出結果。同理，對于每個參數Tj、tj試驗時分別將6種參數設置下的60組隨機算例的平均值作為輸出結果。數據測試結果如表1～3所示。

由表1～3可知，不同參數設置對啟發式算法HCA結果影響甚微，算法百分比誤差表現主要取決于問題規模的大小。在規模小于時50×5時該算法可以在運行時間小于2 s獲得與最優解百分比誤差在5%以內，當問題的規模達到200×10時，算法與CPLEX獲得的低界的百分比誤差接近10%。針對這一特點，本文提出了結合裝箱算法的混合遺傳算法對大規模問題下的解進一步改善。

表1 不同機器速率sj設置下HCA算法性能表現Table 1 The performance of HCA algorithm under different sjsetting

表2 不同預防性維護周期Tj參數設置下算法HCA性能表現Table 2 The performance of HCA algorithm under different Tjsetting

表3 不同維護時間長度tj參數設置下算法HCA性能表Table 3 The performance of HCA algorithm under different tjsetting

表4 啟發式算法HCA與混合遺傳算法HGA比較Table 4 The comparison between heuristic HCA and improved genetic algorithm HGA

3.2 模型驗證

生產實際中，生產計劃與維護計劃往往單獨決策，首先采用傳統的啟發式規則如MULTIFIT［19］得到一個生產部分的工件加工順序，繼而依據預防性維護周期T，得到完整的調度方案。

表5 聯合決策和單獨決策的算法結果比較Table 5 The comparison between joint decision-making and independent decision-making

圖3 聯合決策方法相對于單獨決策方法提升百分比GFig.3 The improvement of joint decision-making compared with independent decision-making

表5顯示了各類問題規模下聯合決策優化模型優化方法相對于單獨決策模型優化方法的數據實驗比較，可以看出聯合決策模型的方法在犧牲少量運算時間的情況下可得到更優的解。圖3顯示了聯合決策的優化方法HCA和HGA相對于單獨決策的優化方法MULTIFIT的目標值提升百分比，可以看出隨著問題規模的增大，聯合決策的優化方法優勢愈加明顯，特別是HGA在問題規模為1 000×50時較單獨決策的目標值提升超過22%。

4 結論

本文針對具有周期預防性維護的異速并行機集成調度問題進行研究，建立了相應的整數規劃模型，得到結論如下：

1）Cplex軟件能在可接受的時間內（2 h）對問題模型進行求解，獲取工件與機器規模為50×5問題的最優解。

2）通過與求得的精確解或低界比較，表明本文提出的構造型啟發式算法HCA能快速的求得中小規模問題的滿意解，其GAP小于10%。而混合遺傳算法HGA在求解大規模問題時效果更優，其解得到明顯的改善。

3）與單獨決策的調度模型相比較，集成預防性維護的聯合決策方法較單獨決策方法的優勢明顯，更有利于車間總體決策。

［1］LEE C Y.Machine scheduling with an availability constraint［J］.Journal of Global Optimization，1996，9（3）：395-416.

［2］MOSHEIOV G，SARIG A.Scheduling a maintenance activity to minimize total weighted completion time［J］.Computers and Mathematics with Applications，2009，57（4）：619-623.

［3］YANG S J.Minimizing total completion time on a single machine with a flexible maintenance activity［J］.Computers＆Operations Research，2011，38（4）：755-757.

［4］LIAO L W.Parallel machine scheduling with machine availability and eligibility constraints［J］.European Journal of Operational Research，2008，184（2）：458-467.

［5］RACEM M.Identical parallel machine scheduling under availability constraints to minimize the sum of completion times［J］.European Journal of Operational Research，2009，197（3）：1150-1165.

［6］TAN Z Y，CHEN Y.On the exact bounds of SPT for scheduling on parallel machines with availability constraints［J］.International Journal of Production Economics，2013，146（1）：293-299.

［7］CHOU J H，LOW C Y.A single-machine scheduling problem with maintenance activities to minimize makespan［J］.Applied Mathematics and Computation，2010，215（11）：3929-3935.

［8］XUEP F.Single machine scheduling with piece-rate maintenance and interval constrained position-dependent processing times［J］.Applied Mathematics and Computation 2014，226：415-417.

［9］LEE J Y.Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance［J］.Computers＆Operations Research，2012，39（9）：2196-2205.

［10］YANG S J.Single-machine scheduling problems simultaneously with deterioration and learning effects under deteriorating multi-maintenance activities consideration［J］.Computers＆Industrial Engineering，2012，62（1）：271-275.

［11］蔣志高，董明.考慮維護且加工時間可變的單機調度問題研究［J］.工業工程與管理，2011，16（3）：68-74.JIANG Zhigao，DONG Ming.Study on single machine problem with maintenance and variable processing time［J］.Industrial Engineering and Management，2011，16（3）：68-74.

［12］CHEN J S.Scheduling of non-resumable jobs and flexible maintenance activities on a single machine to minimize makespan［J］.European Journal of Operational Research，2008，190：90-120.

［13］金玉蘭，蔣祖華.預防性維修計劃和生產調度的多目標優化［J］.哈爾濱工程大學學報，2011，32（9）：1205-1209.JIN Yulan，JIANG Zuhua.Multi-objective optimization research on preventive maintenance and production scheduling［J］.Journal of Harbin Engineering University，2011，32（9）：1205-1209.

［14］崔維偉，陸志強.單機系統的生產調度與預防性維護的集成優化［J］.上海交通大學學報，2012，46（12）：2009-2013. CUI Weiwei，LU Zhiqiang.Integrating production scheduling and preventive maintenance planning for a single machine［J］.Journal of Shanghai Jiaotong University，2012，46（12）：2009-2013.

［15］SUN K B.Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines［J］.International Journal of Production Economics，2010，124（1）：151-158.

［16］程貞敏，李洪興.最小化時間表長的平行機調度近似算法研究［J］.北京師范大學學報，2012，48（1）：11-15.CHENG Zhenmin，LI Hongxin.Approximated algorithm for identical machine scheduling with minimized makespan［J］.Journal of Beijing Normal University，2012，48（1）：11-15.

［17］XU D H.Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan［J］.Computers＆Operations Research，2008，35（4）：1344-1349.

［18］GUPTA J N D.A new heuristic algorithm for the one-dimensional bin-packing problem［J］.Production Planning＆Control，1999，10（6）：598-603.

［19］BURKARD R E.A note on MULTIFIT scheduling for uniform machines［J］.Computing，1998，61（1）：277-283.

Integrated uniform machine scheduling with periodic preventive maintenance

JIANG Cailin1，LU Zhiqiang1，CUI Weiwei2
（1.School of Mechanical and Energy Engineering，Tongji University，Shanghai 201804，China；2.School of Mechanical and Power Engineering，Shanghai Jiaotong University，Shanghai 200240，China）

A mixed integer programming model integrating the production scheduling and preventive maintenances is proposed to solve the unavailability constraints of uniform machine scheduling system problem.Specifically，a constructive heuristic algorithm（HCA）has been developed based on load balancing technology of improved longest processing time（LPT）rule and single machine optimization method of minimum bin slack heuristic.The numerical experiment compared with Cplex showed that the gap between the solution of HCA and optimal solution（low bound）is less than 10%for the small and medium scale problems.Furthermore，a hybrid genetic algorithm（HGA）combining bin-packing algorithm is proposed.The numerical experiment compared with HCA showed that the performance of HGA is better than HCA for large scale problems.Finally，the data experiments indicated that the joint decision-making model integrating production scheduling and machine maintenance appears to perform better than the independent decision-making model，as well as coordinate the overall plan of the production and maintenance effectively.

uniform machine scheduling；preventive maintenance；integer programming；heuristic algorithm；hybrid genetic algorithm

10.3969／j.issn.1006-7043.201307059

http：／／www.cnki.net／kcms／doi／10.3969／j.issn.1006-7043.201307059.html

F224

A

1006-7043（2014）11-1409-06

2013-07-22.網絡出版時間：2014-09-25.

國家自然科學基金資助項目（71171130）；上海市自然科學基金資助項目（12ZR1414400）.

江才林（1989-），男，碩士研究生；陸志強（1968-），男，教授，博士生導師.

陸志強，E-mail：zhiqianglu＠tongji.edu.cn.