董恩來 譚園園

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

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

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

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

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

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

2 問題描述

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

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

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

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

3 模型的建立

3.1參數(shù)說明

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

3.2 決策變量

sj： 工件j的開始時刻;cj： 工件j的結(jié)束時刻;sijm：機器i加工完工件j之后進行維護的開始時刻;cijm：? 機器i加工完工件j之后進行維護的結(jié)束時刻;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 數(shù)學(xué)模型

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

4 算法設(shè)計

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

4.1編碼與解碼

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

針對本文研究的問題，解碼時先根據(jù)算法求得的0-1序列，將工件的加工設(shè)備確定好，此時工件被分為兩組。將分配在機器M1上進行加工的工件，根據(jù)先后約束式對工件排序，隨后根據(jù)上文中圖1所示的運行情況，依次將待加工的工件進行判斷，決定工件的加工時間與結(jié)束時間，最后判斷加工此工件后是否進行維護，直到所有分配在此的工件判斷并加工完畢，求得機器M1對應(yīng)的Cmax1;將分配在機器M2上進行加工的工件，根據(jù)先后約束式對工件排序，隨后根據(jù)上文中圖2所示的運行情況，依次將待加工的工件進行判斷，決定工件的加工時間與結(jié)束時間，最后判斷加工此工件后是否進行維護，直到所有分配在此的工件判斷并加工完畢，求得機器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)及其感知范圍。算法會隨機選擇一個狀態(tài)，對其進行判斷，若其比當前狀態(tài)優(yōu)秀，則向其進行隨機移動，否則不進行移動。直到達到嘗試次數(shù)，將移動后的狀態(tài)進行記錄。

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

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

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

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

4.3 自適應(yīng)步長

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

本文選擇將距離與步長進行相等處理，由于不同的人工魚均是在其視野范圍內(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）

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

5 仿真實驗

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

本次實驗主要對改進的人工魚群算法（AFSA-C）、人工魚群算法（AFSA）與遺傳算法GA進行性能比較，主要有三個維度，分別是算法的運行結(jié)果、算法停止迭代的次數(shù)與算法的運行時間。對上述的算法采用JAVA語言進行編程實現(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。

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

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

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

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

6 總結(jié)

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

參考文獻：

[1] 馬英.考慮維護時間的機器調(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ù)防性維護的異速并行機集成調(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è)備維護的平行機調(diào)度應(yīng)用研究[D].重慶：重慶大學(xué)，2018.

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

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