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

董恩來 譚園園

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

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

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

2 問題描述

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

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

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

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

3 模型的建立

3.1參數(shù)說明

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

3.2 決策變量

sj： 工件j的開始時(shí)刻;cj： 工件j的結(jié)束時(shí)刻;sijm：機(jī)器i加工完工件j之后進(jìn)行維護(hù)的開始時(shí)刻;cijm：? 機(jī)器i加工完工件j之后進(jìn)行維護(hù)的結(jié)束時(shí)刻;w2j ： 機(jī)器M2進(jìn)行維護(hù)的維護(hù)時(shí)間;若工件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ù)方式下的兩臺(tái)并行機(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）表示工件只能在一臺(tái)機(jī)器上進(jìn)行加工。式（4）表示工件有且只有一個(gè)前繼工件。式（5）表示工件有且只有一個(gè)后繼工件。式（6）對工件的開始時(shí)間進(jìn)行約束，其中U是一個(gè)非常大的正數(shù)。式（7）表示機(jī)器M2的維護(hù)時(shí)長和機(jī)器M2的維護(hù)之后的持續(xù)加工時(shí)長成函數(shù)關(guān)系。式（8）表示工件j開始時(shí)刻和完成時(shí)刻的關(guān)系。式（9）表示維護(hù)的開始時(shí)刻和完成時(shí)刻關(guān)系。式（10）表示在機(jī)器Mi維護(hù)后的連續(xù)工作時(shí)間不能超過最大時(shí)間ti。式（11）表示工件j1在工件j2之前加工時(shí)，機(jī)器Mi的連續(xù)工作時(shí)間λi，j。

4 算法設(shè)計(jì)

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

4.1編碼與解碼

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

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

4.2 人工魚行為

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

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

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

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

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

公告牌：公告牌是記錄魚群中最優(yōu)個(gè)體的。在迭代中，每條人工魚都會(huì)進(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)之間的接近程度。若其差距大，則距離就大，此時(shí)應(yīng)該對步長進(jìn)行適當(dāng)增大的處理，才能讓不同狀態(tài)之間較快的相互靠近。若其差距小，則距離就小，此時(shí)相應(yīng)的步長可以適當(dāng)減小，避免在極值點(diǎn)附近發(fā)生震蕩，導(dǎo)致算法性能減弱。

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

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

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

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

5 仿真實(shí)驗(yàn)

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

本次實(shí)驗(yàn)主要對改進(jìn)的人工魚群算法（AFSA-C）、人工魚群算法（AFSA）與遺傳算法GA進(jìn)行性能比較，主要有三個(gè)維度，分別是算法的運(yùn)行結(jié)果、算法停止迭代的次數(shù)與算法的運(yùn)行時(shí)間。對上述的算法采用JAVA語言進(jìn)行編程實(shí)現(xiàn)，程序的運(yù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可以看出，在算法的運(yùn)行時(shí)間方面，改進(jìn)的人工魚群算法所需時(shí)長最短，算法運(yùn)行效率較高。

由圖5圖6以看出，在算法迭代停止的次數(shù)方面，改進(jìn)的人工魚群算法的停止迭代次數(shù)最低，證明該算法在初期就在很短的時(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ù)方式下的兩臺(tái)并行機(jī)調(diào)度問題，建立相應(yīng)的數(shù)學(xué)模型，針對人工魚群算法的不足之處，設(shè)計(jì)了自適應(yīng)步長的方式進(jìn)行改進(jìn)，通過實(shí)驗(yàn)對比分析，本文改進(jìn)的人工魚群算法，在算法運(yùn)行時(shí)間、算法迭代停止的次數(shù)與算法的運(yùn)行的結(jié)果方面具有顯著優(yōu)勢。并且隨著問題規(guī)模的擴(kuò)大，算法的性能優(yōu)勢更加明顯，是一種有效求解不同類型預(yù)防性維護(hù)下的兩臺(tái)并行機(jī)調(diào)度問題的方法。

參考文獻(xiàn)：

[1] 馬英.考慮維護(hù)時(shí)間的機(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] 江才林，陸志強(qiáng)，崔維偉.考慮周期預(yù)防性維護(hù)的異速并行機(jī)集成調(diào)度研究[J].哈爾濱工程大學(xué)學(xué)報(bào)，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)編輯：梁書】