不同預防性維護方式下的兩臺并行機調度問題

董恩來 譚園園

摘要：在企業實際的生產調度中，設備的維護是不可或缺的。本文以具有不同預防性維護方式的兩臺并行機調度為研究對象。以最小化最大加工時間為目標建立數學模型，確定工件的加工設備及其加工順序。將海明距離與自適應步長結合，提出改進的人工魚群算法，提升算法的性能。最后在不同算例規模的情況下進行仿真實驗，并引入遺傳算法（GA）作為對照，將AFSA、AFSA-C與GA進行性能對比，其結果表明改進的人工魚群算法（AFSA-C）性能最優。

關鍵詞：兩臺并行機;生產調度;預防性維護;人工魚群算法;組合優化

中圖分類號：TP278? ? ? 文獻標識碼：A

文章編號：1009-3044（2021）28-0160-04

開放科學（資源服務）標識碼（OSID）：

The Scheduling Problem of Two Parallel Machines under Different Preventive Maintenance Methods

DONG En-lai， TAN Yuan-yuan

（School of Artificial Intelligence， Shenyang University of Technology， Shenyang 110870， China）

Abstract： In the actual production scheduling of an enterprise， equipment maintenance is indispensable. This paper takes two parallel machine scheduling with different preventive maintenance methods as the research object. With the goal of minimizing the maximum processing time， a mathematical model is established to determine the processing equipment of the workpiece and its processing sequence. Combining the Hamming distance with the adaptive step size， an improved artificial fish school algorithm is proposed to improve the performance of the algorithm. Finally， a simulation experiment was carried out under different scales of calculation examples， and genetic algorithm （GA） was introduced as a control， and the performance of AFSA， AFSA-C and GA was compared. The results showed the performance of the improved artificial fish school algorithm （AFSA-C） Optimal.

Key words： two parallel machine; production scheduling; preventive maintenance; artificial fish school algorithm; combinatorial optimization

1 引言

調度的產生是由于資源的有限性和稀缺性，有限的資源無法同時滿足企業的需求。在實際生產中，企業需要讓生產的機器維持高效運轉。但是無法避免在運行中出現故障，而導致整個生產計劃停滯。此時需要重新調整調度計劃或者機器修復完畢才能恢復生產，會耽誤一定的時間和增加一定的成本。由此可知，在進行生產調度計劃制定過程中，假定設備是一直可以運行的，忽略設備的可靠性、設備的預防性維護是不合理的。需要將預防性維護與生產調度聯合起來進行考慮。對這個問題，有很多學者進行了研究。并行機可以看作單機的組合，對于單機調度與預防性維護，馬英[1]對單機模型與預防性維護進行了分析，因為維護時長可變可固定，維護時段可變可固定，所以有四種情形。作者對這四種情形進行了分析，提出啟發式算法，對最壞情況界進行分析，證明問題的NP難性質。并將求解問題的思路推廣到多機系統，驗證了所提啟發式算法的有效性。Ji M[2]等對單機定周期維護，維護時長為固定值t的問題進行了研究，證明了LPT算法的最壞情況界是2，并且通過證明除非此問題為P=NP的，否則不會存在比LPT更好的算法。在并行機與預防性維護方面，江才林等[3]根據異速并行機的特點，在考慮周期性預防性維護的情況下，提出HGA算法，發現對于大規模問題，HGA算法性能優異。徐德華等[4]人研究了具有周期性維護的并行機問題，并且根據非搶占作業問題，對比了LPT算法和LS算法的優劣。Mosheiov等[5]以無關聯并行機調度系統為研究內容，假定所有設備的預防性維護作業需要同時進行，以總完工時間為目標，維護作業的時間窗口為[0， T]，維護時間長度為常數t的模型進行了研究。楊曉霞[6]考慮了平行機系統下的維護計劃，對平行機系統中的設備采用同樣的維護約束條件，基于貪婪機制進行求解。

針對預防性維護下并行機調度問題研究的特點以及其不足之處，本文考慮具有兩臺不同維護方式的單機調度組成的并行機系統，以最小化最大加工時間為目標，針對每臺設備的維護特點，建立數學模型。決策工件的加工位置和加工順序。

2 問題描述

有n個獨立的工件j1，j2，…，jn安排到兩臺并行機M1，M2上加工。其中對M1進行工具更換維護，兩次相鄰的維護之間的最大時間間隔是t1，為柔性周期維護。機器M2進行周期維護，每兩次相鄰的維護之間的時間間隔事先給定為t2，針對該問題，有下面的幾個條件：（1）工件j1， j2， …， jn的加工時長分別是p1， p2， …， pn ;（2）所有的加工工件在加工時都是不可以中斷的，并且在零時刻都已到達生產線，到達后可以立即進行工件加工;（3）兩臺機器在開始加工前都已經完成了一次維護，機器到達生產線后可以馬上啟動機器對工件進行加工;（4）對于機器M1的維護時間長度w1，設置為固定的正常數，對于機器M2的維護時間長度，設定為與M2加工負載有關的函數w2=F（λ2，j）， 其中λ2，j表示為在機器M2上加工的工件j和上一次維護后的在工件j之前所有已經加工工件的加工時長之和（負載），為非負增加的線性函數;（5）工件的加工時間pj≤max{t1， t2}， j=1，…， n，否則不可加工該工件。

本文考慮以最小化最大加工時間Cmax為目標。本文的決策任務是（1）指派工件的加工設備、確定在同一設備上加工工件的順序;（2）工件加工的開始時刻與結束時刻;（3）機器M1上維護的開始時刻與結束時刻;（4）機器M2上維護的時長、維護的開始時刻和結束時刻。機器運行情況如下圖1、圖2所示。

在圖1中，t1為最晚開始維護的時間間隔;λ1，j為機器M1上的工件j到上一次維護結束時所有工件加工時間的累加;維護的時長w1為常數。若在加工完工件j之后，機器M1的 λ1，j+ pj+1>t1，則工件j+1不能直接在工件j之后進行加工，需要等維護結束后再進行加工，此時維護可以直接在加工完工件j之后開始。

在圖2中，t2為相鄰兩次維護的時間間隔，為常數;λ2，j為機器M1上的工件j到上一次維護結束時所有工件加工時常求和，也就是負載;維護的時長w2隨著負載λ2，j呈非負增加關系。若在加工完工件j之后，機器M2的pj+1+ λ2，j >t2 ，則工件j+1不能直接在工件j之后進行加工，需要等維護結束后再進行加工，此時維護需要等到t2才可開始。

3 模型的建立

3.1參數說明

j ： 工件j的編號，j = 0...n+1;其中j =0 和j = n+1;均表示虛擬工件;pj ：工件j的加工時間;m ： 機器的數量，本問題m=2;i ： 機器的編號， i=1，2;t1 ：機器M1的最大連續加工時間;t2 ：機器M2上相鄰兩次維護的時間間隔;w1j： 機器M1的維護時間;λi，j ：在機器i上，上一次維護之后到工件j之前加工的工件以及工件的加工時間總和。

3.2 決策變量

sj： 工件j的開始時刻;cj： 工件j的結束時刻;sijm：機器i加工完工件j之后進行維護的開始時刻;cijm：? 機器i加工完工件j之后進行維護的結束時刻;w2j ： 機器M2進行維護的維護時間;若工件j分配給機器M1進行加工，不在機器M2上進行加工，則xi，j為1，否則為0;若在機器Mi上，加工完工件j之后，進行維護，則yi，j為1，否則為0;若在機器i上，工件j1 在工件j2 之前加工，則ei，j1，j2為1，否則為0。

3.3 數學模型

針對不同預防性維護方式下的兩臺并行機調度問題，建立了如下的調度模型：

obj： min Cmax? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（1）

[Cmax=maxnj=1cj]? ? ? ? ? ? ? ? ? ? ? ? ? （2）

s.t.

[i=12xi，j=1]， j = 1，…，n? ? ? ? ? ? ? ? ? ? ? ? ?（3）

[j1=0nei，j1，j2=1]， i=1， 2，? [j2=0，…，n]? ? ? ? ? ? ? ? ? ?（4）

[j2=0n+1ei，j1，j2=1]， i=1，2，? [j1=1，…，n+1]? ? ? ? ? ? ? ? （5）

[sj2+（3-xi，j1-xi，j2-ei，j1，j2）U-yi，j1wij≥cj1]， i=1，2，? j1，j2 = 1，…，n，? （6）

[w2，j=F（λ2，j）]， j = 1，…，n，? ? ? ? ? ? ? ? ? ? ? ?（7）

[cj=sj+pj]， j = 1，…，n? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （8）

[cmij=smij+wij]， i=1，2，? j = 1，…，n? ? ? ? ? ? ? ? ? ? ? （9）

[λi，j≤ti]， i=1，2，? j = 1，…，n? ? ? ? ? ? ? ? ? ? ?（10）

[λi，j2=（2-ei，j1，j2-yi，j1）λi，j1+pj2]，? i=1，2，? j = 1，…，n? ? ? ? ? ?（11）

其中，式（1）～（2）表示本文研究問題的目標函數。式（3）表示工件只能在一臺機器上進行加工。式（4）表示工件有且只有一個前繼工件。式（5）表示工件有且只有一個后繼工件。式（6）對工件的開始時間進行約束，其中U是一個非常大的正數。式（7）表示機器M2的維護時長和機器M2的維護之后的持續加工時長成函數關系。式（8）表示工件j開始時刻和完成時刻的關系。式（9）表示維護的開始時刻和完成時刻關系。式（10）表示在機器Mi維護后的連續工作時間不能超過最大時間ti。式（11）表示工件j1在工件j2之前加工時，機器Mi的連續工作時間λi，j。

4 算法設計

2002年，李曉磊[7]通過觀察魚類群體的行為活動，提出了人工魚群算法。人工魚群算法具有良好的性能，可以用來求解調度問題。

4.1編碼與解碼

本文采用0-1編碼來對機器進行編碼，其中，0代表機器M1，1代表機器M2。那么，對于一個包含10個工件的調度問題，其編碼方式如下表1所示：

針對本文研究的問題，解碼時先根據算法求得的0-1序列，將工件的加工設備確定好，此時工件被分為兩組。將分配在機器M1上進行加工的工件，根據先后約束式對工件排序，隨后根據上文中圖1所示的運行情況，依次將待加工的工件進行判斷，決定工件的加工時間與結束時間，最后判斷加工此工件后是否進行維護，直到所有分配在此的工件判斷并加工完畢，求得機器M1對應的Cmax1;將分配在機器M2上進行加工的工件，根據先后約束式對工件排序，隨后根據上文中圖2所示的運行情況，依次將待加工的工件進行判斷，決定工件的加工時間與結束時間，最后判斷加工此工件后是否進行維護，直到所有分配在此的工件判斷并加工完畢，求得機器M2對應的Cmax2;最后將Cmax1與Cmax2比較，將較大的那個作為最終結果。

4.2 人工魚行為

對于一條人工魚來說，其狀態可以用向量X =（x1，x2，x3，…，xn）來表示;人工魚狀態的求解結果用Y = F（X）表示;人工魚個體之間的距離di，j;Visual表示的是人工魚的感知范圍;Step為人工魚的最大移動距離，又稱步長;δ為擁擠度因子。

覓食行為：由人工魚此刻的狀態及其感知范圍。算法會隨機選擇一個狀態，對其進行判斷，若其比當前狀態優秀，則向其進行隨機移動，否則不進行移動。直到達到嘗試次數，將移動后的狀態進行記錄。

聚群行為：由人工魚此刻的狀態及其感知范圍。判斷其附近人工魚的數量。計算其中心狀態，若中心狀態較優，則根據此狀態的方位進行隨機移動，否則，不移動，執行其他行為。將移動后的狀態進行記錄。

追尾行為：由人工魚此刻的狀態，判斷其感知范圍內人工魚的數量。隨后計算附近人工魚對應的狀態，選擇其中的最優狀態。若此狀態比人工魚此刻的狀態優秀，就根據此狀態的方位進行隨機移動，否則不進行移動。將移動后的狀態進行記錄。

上述三種行為，本文選擇直接對編碼進行上述操作，根據不同編碼的位數不同，進行相應的改進，來達到人工魚的移動效果。進行上述三種行為后，需要進行行為評價，從上述行為中挑選移動之后的最優狀態，作為最終的移動狀態。

公告牌：公告牌是記錄魚群中最優個體的。在迭代中，每條人工魚都會進行一次尋優，隨后將尋優結果與公告牌進行比對。若比公告牌優秀，則進行公告牌的刷新，否則，不進行更改。這是進行算法尋優的必須操作，直到魚群中的所有魚都完成一次刷新，才開始進行下一輪迭代。

4.3 自適應步長

針對本文所采用的編碼方式，選擇采用海明距離來對不同人工魚之間的距離進行求解。海明距離又被稱為碼距。可以有效衡量本文編碼所確定的人工魚狀態之間的接近程度。若其差距大，則距離就大，此時應該對步長進行適當增大的處理，才能讓不同狀態之間較快的相互靠近。若其差距小，則距離就小，此時相應的步長可以適當減小，避免在極值點附近發生震蕩，導致算法性能減弱。

本文選擇將距離與步長進行相等處理，由于不同的人工魚均是在其視野范圍內發現的，所以符合最長步長小于視野的約束條件。此時設此刻人工魚的狀態為Xi。若在其視野范圍內存在人工魚Xj，使得對應的食物濃度Yj比Yi優秀，則計算出Xi與Xj之間的海明距離di，j ，根據海明距離di，j計算人工魚Xi的移動距離，公式如下：

[Step=di，j]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（12）

[Xi|next=Xi+Step·Random]? ? ? ? ? ? （13）

由上式可知，將步長與距離進行統一，可以將公式化簡，算法也就進行了相應的簡化處理。

5 仿真實驗

本文采用遺傳算法作為改進的人工魚群的對比算法，遺傳算法的編碼、解碼與種群大小及其初始化的操作與人工魚群保持一致。交叉方式選擇兩點交叉，將染色體分為三部分，隨后把不同染色體的后兩部分分別進行交叉操作。單點變異方式。采用輪盤賭為最優個體的選擇方式。

本次實驗主要對改進的人工魚群算法（AFSA-C）、人工魚群算法（AFSA）與遺傳算法GA進行性能比較，主要有三個維度，分別是算法的運行結果、算法停止迭代的次數與算法的運行時間。對上述的算法采用JAVA語言進行編程實現，程序的運行環境保持一致。對算法設置參數如下：AFSA-C的魚群大小為50，迭代次數為500次，擁擠度因子為45，嘗試次數設置為3，視野為10。AFSA的步長設置為5，其他參數與AFSA-C相同。GA的種群大小為50，迭代次數為500，交叉概率為0.6，變異概率為0.2。研究的調度問題工件數n分別為n = 20，n = 50，n = 100，n = 200，n=500，n = 1000。

本文認為迭代停止的條件：算法最后輸出的結果在第幾代不再變化，就認為算法在該代已經停止迭代。其對比結果如下：

由圖3與圖4可以看出，在算法的運行時間方面，改進的人工魚群算法所需時長最短，算法運行效率較高。

由圖5圖6以看出，在算法迭代停止的次數方面，改進的人工魚群算法的停止迭代次數最低，證明該算法在初期就在很短的時間內的收斂到最優值附近，收斂效果很棒。

由上圖7可知，隨著問題規模的擴大，即工件數量的增加，AFSA與AFSA-C二者的差值越來越大，由此可見，在求解精度方面，改進的人工魚群算法明顯占有優勢。所以在求解大規模的問題是，可以采用本文所改進的人工魚群算法來進行求解，以獲得更好的效果。

6 總結

本文考慮不同預防性維護方式下的兩臺并行機調度問題，建立相應的數學模型，針對人工魚群算法的不足之處，設計了自適應步長的方式進行改進，通過實驗對比分析，本文改進的人工魚群算法，在算法運行時間、算法迭代停止的次數與算法的運行的結果方面具有顯著優勢。并且隨著問題規模的擴大，算法的性能優勢更加明顯，是一種有效求解不同類型預防性維護下的兩臺并行機調度問題的方法。

參考文獻：

[1] 馬英.考慮維護時間的機器調度問題研究[D].合肥：合肥工業大學，2010.

[2] Ji M，He Y，Cheng T C E.Single-machine scheduling with periodic maintenance to minimize makespan[J].Computers & Operations Research，2007，34（6）：1764-1770.

[3] 江才林，陸志強，崔維偉.考慮周期預防性維護的異速并行機集成調度研究[J].哈爾濱工程大學學報，2014，35（11）：1409-1414，1421.

[4] Xu D H，Sun K B，Li H X.Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan[J].Computers & Operations Research，2008，35（4）：1344-1349.

[5] Mosheiov G，Sarig A.A note：Simple heuristics for scheduling a maintenance activity on unrelated machines[J].Computers & Operations Research，2009，36（10）：2759-2762.

[6] 楊曉霞.考慮設備維護的平行機調度應用研究[D].重慶：重慶大學，2018.

[7] 李曉磊.一種新型的智能優化方法-人工魚群算法[D].杭州：浙江大學，2003.

【通聯編輯：梁書】