不同預(yù)防性維護(hù)方式下的兩臺并行機(jī)調(diào)度問題

董恩來 譚園園

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

關(guān)鍵詞：兩臺并行機(jī);生產(chǎn)調(diào)度;預(yù)防性維護(hù);人工魚群算法;組合優(yōu)化

中圖分類號：TP278? ? ? 文獻(xiàn)標(biāo)識碼：A

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

開放科學(xué)（資源服務(wù)）標(biāo)識碼（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 引言

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

針對預(yù)防性維護(hù)下并行機(jī)調(diào)度問題研究的特點以及其不足之處，本文考慮具有兩臺不同維護(hù)方式的單機(jī)調(diào)度組成的并行機(jī)系統(tǒng)，以最小化最大加工時間為目標(biāo)，針對每臺設(shè)備的維護(hù)特點，建立數(shù)學(xué)模型。決策工件的加工位置和加工順序。

2 問題描述

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

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

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

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

3 模型的建立

3.1參數(shù)說明

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

3.2 決策變量

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

3.3 數(shù)學(xué)模型

針對不同預(yù)防性維護(hù)方式下的兩臺并行機(jī)調(diào)度問題，建立了如下的調(diào)度模型：

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）表示本文研究問題的目標(biāo)函數(shù)。式（3）表示工件只能在一臺機(jī)器上進(jìn)行加工。式（4）表示工件有且只有一個前繼工件。式（5）表示工件有且只有一個后繼工件。式（6）對工件的開始時間進(jìn)行約束，其中U是一個非常大的正數(shù)。式（7）表示機(jī)器M2的維護(hù)時長和機(jī)器M2的維護(hù)之后的持續(xù)加工時長成函數(shù)關(guān)系。式（8）表示工件j開始時刻和完成時刻的關(guān)系。式（9）表示維護(hù)的開始時刻和完成時刻關(guān)系。式（10）表示在機(jī)器Mi維護(hù)后的連續(xù)工作時間不能超過最大時間ti。式（11）表示工件j1在工件j2之前加工時，機(jī)器Mi的連續(xù)工作時間λi，j。

4 算法設(shè)計

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

4.1編碼與解碼

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

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

4.2 人工魚行為

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

覓食行為：由人工魚此刻的狀態(tài)及其感知范圍。算法會隨機(jī)選擇一個狀態(tài)，對其進(jìn)行判斷，若其比當(dāng)前狀態(tài)優(yōu)秀，則向其進(jìn)行隨機(jī)移動，否則不進(jìn)行移動。直到達(dá)到嘗試次數(shù)，將移動后的狀態(tài)進(jìn)行記錄。

聚群行為：由人工魚此刻的狀態(tài)及其感知范圍。判斷其附近人工魚的數(shù)量。計算其中心狀態(tài)，若中心狀態(tài)較優(yōu)，則根據(jù)此狀態(tài)的方位進(jìn)行隨機(jī)移動，否則，不移動，執(zhí)行其他行為。將移動后的狀態(tài)進(jìn)行記錄。

追尾行為：由人工魚此刻的狀態(tài)，判斷其感知范圍內(nèi)人工魚的數(shù)量。隨后計算附近人工魚對應(yīng)的狀態(tài)，選擇其中的最優(yōu)狀態(tài)。若此狀態(tài)比人工魚此刻的狀態(tài)優(yōu)秀，就根據(jù)此狀態(tài)的方位進(jìn)行隨機(jī)移動，否則不進(jìn)行移動。將移動后的狀態(tài)進(jìn)行記錄。

上述三種行為，本文選擇直接對編碼進(jìn)行上述操作，根據(jù)不同編碼的位數(shù)不同，進(jìn)行相應(yīng)的改進(jìn)，來達(dá)到人工魚的移動效果。進(jìn)行上述三種行為后，需要進(jìn)行行為評價，從上述行為中挑選移動之后的最優(yōu)狀態(tài)，作為最終的移動狀態(tài)。

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

4.3 自適應(yīng)步長

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

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

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

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

由上式可知，將步長與距離進(jìn)行統(tǒng)一，可以將公式化簡，算法也就進(jìn)行了相應(yīng)的簡化處理。

5 仿真實驗

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

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

本文認(rèn)為迭代停止的條件：算法最后輸出的結(jié)果在第幾代不再變化，就認(rèn)為算法在該代已經(jīng)停止迭代。其對比結(jié)果如下：

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

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

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

6 總結(jié)

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

參考文獻(xiàn)：

[1] 馬英.考慮維護(hù)時間的機(jī)器調(diào)度問題研究[D].合肥：合肥工業(yè)大學(xué)，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] 江才林，陸志強，崔維偉.考慮周期預(yù)防性維護(hù)的異速并行機(jī)集成調(diào)度研究[J].哈爾濱工程大學(xué)學(xué)報，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] 楊曉霞.考慮設(shè)備維護(hù)的平行機(jī)調(diào)度應(yīng)用研究[D].重慶：重慶大學(xué)，2018.

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

【通聯(lián)編輯：梁書】