求解具有預(yù)防性維護(hù)的并行機(jī)調(diào)度的遺傳算法

李同玲，王 宏，林 丹

（天津大學(xué) 理學(xué)院，天津 300072）

1 概述

假設(shè)機(jī)器持續(xù)不斷工作的生產(chǎn)計劃在現(xiàn)實中根本無法實施。由于設(shè)備極其昂貴和復(fù)雜，實際生產(chǎn)中，設(shè)備發(fā)生故障會給整個生產(chǎn)車間帶來影響，進(jìn)而降低生產(chǎn)效率。文獻(xiàn)[1]指出對設(shè)備進(jìn)行有效的預(yù)防性維護(hù)就能夠提高生產(chǎn)效率和生產(chǎn)的安全性能。因此在編制生產(chǎn)計劃的過程中應(yīng)考慮機(jī)器的維護(hù)。近年來很多學(xué)者在此方面進(jìn)行了許多研究，并得到了很多重要的結(jié)論。

Liao等[2]設(shè)計了一個分支定界算法和啟發(fā)式算法求解以最小化最大延誤時間為目標(biāo)的單機(jī)周期維護(hù)問題。Ji[3]討論了目標(biāo)為最小化總工期的周期性單機(jī)排序問題，指出最長加工時間是最優(yōu)離線算法。周炳海等[4]研究了集成生產(chǎn)與預(yù)防性維護(hù)的流水線車間的調(diào)度問題，并設(shè)計了一個簡單啟發(fā)式算法對其進(jìn)行求解。Sbih等[5]分別提出啟發(fā)式算法和分支定界方法求解關(guān)于單機(jī)周期維護(hù)和彈性的周期維護(hù)的調(diào)度問題。文獻(xiàn)[6]研究了彈性周期性維護(hù)的單機(jī)調(diào)度問題，將周期維護(hù)的生產(chǎn)過程看作是一個裝箱問題，提出的六種啟發(fā)式算法進(jìn)行求解，實驗結(jié)果表明，加工時間降序排列的最先適配法的效果最好。文獻(xiàn)[7]提出了用粒子群算法算法來解決單機(jī)定期維修活動調(diào)度問題。文獻(xiàn)[8]分別研究了周期性和決策性兩種預(yù)防性維護(hù)的兩臺并行機(jī)調(diào)度問題，并對兩種維護(hù)分別進(jìn)行降序最先適配啟發(fā)式和最短加工時間啟發(fā)式的分析。

預(yù)防性維護(hù)問題分為兩種：周期性維護(hù)和決策性維護(hù)。周期性維護(hù)是指維護(hù)任務(wù)的時間表在編制工件調(diào)度方案之前已經(jīng)確定。決策性維護(hù)指維護(hù)任務(wù)的時間和工件調(diào)度同時編制[8]。以上文獻(xiàn)研究的問題多集中在周期性維護(hù)上，而大多數(shù)文獻(xiàn)都假設(shè)訂單在0時刻均可以加工，實際上訂單是動態(tài)到達(dá)的。本文將研究工件帶有釋放時間的預(yù)防性維護(hù)的并行機(jī)調(diào)度問題，并對該問題設(shè)計了一種遺傳算法尋找最優(yōu)工件序列，對于給定的工件序列設(shè)計了最先適配啟發(fā)式算法求其最優(yōu)時間表。

2 問題描述

本文研究的問題描述如下：N個獨立的工件i∈{1, 2, , N}在M臺并行機(jī)j∈{1, 2, , M}上加工。工件是動態(tài)到達(dá)的，即工件i的釋放時間ri不全為0，每個工件i的加工時間是Pi。在生產(chǎn)加工過程中，每臺機(jī)器同時只能加工一個工件，機(jī)器持續(xù)工作一段時間BL后必須進(jìn)行預(yù)防性維護(hù)，每一次機(jī)器的維護(hù)時間是m。本文考慮預(yù)防性維護(hù)中的一種——決策性維護(hù)。目標(biāo)是確定各工件i在機(jī)器上的開始時間STi和完工時間CTi及機(jī)器的維護(hù)時間表，使得總工期Cmax最小。本文規(guī)定Pi≤BL；并把在每臺機(jī)器上連續(xù)加工的工件記為一個批次k (k=1, 2, , K) ，機(jī)器j上的第k批次的開始時間和完工時間分別記為SMkj和CMkj；每個工件在任何一臺機(jī)器上加工不允許中斷；工件的加工時間和釋放時間、機(jī)器維護(hù)時間都已知。

3 給定工件序列的單機(jī)調(diào)度算法

對求解帶有釋放時間的工件在具有預(yù)防性維護(hù)的并行機(jī)調(diào)度問題，本文分為兩部分構(gòu)成，首先確定每臺并行機(jī)上的工件序列，然后分別根據(jù)工件序列來確定每個工件的開工和完工時間，即確定每個工件的時間表。本節(jié)主要介紹已知機(jī)器j上的工件序列來確定工件時間表的一種啟發(fā)式算法，此方法類似于裝箱問題的最先適配算法。算法如下：

初始化：令批次k＝1，SMkj＝0，機(jī)器的當(dāng)前完工時間CM＝0。

1）從k＝1批次開始，依照工件序列的優(yōu)先順序檢查所有未被排產(chǎn)的工件i是否可以放到第一批次進(jìn)行加工。若工件i的釋放時間ri和機(jī)器的當(dāng)前完工時間CM中較大者加上其加工時間Pi不大于機(jī)器可持續(xù)加工時間BL，即max{ri, CM}+Pi≤BL，則工件i可放到第一批次加工，工件i的開工時間STi＝max{ri, CM}，完工時間CTi＝STi+Pi，此時機(jī)器的當(dāng)前完工時間CM＝CTi；否則工件i不可在第一批次加工。重復(fù)直到所有工件檢查完。若所有工件都已安排完，算法停止；否則，批次k加工完畢，則CMkj＝CM，轉(zhuǎn)2）。

2）進(jìn)行第k批次的機(jī)器維護(hù)，從CMkj開始維護(hù)，維護(hù)的完工時間為CMkj＋m ，機(jī)器的當(dāng)前完工時間CM＝CMkj。接著機(jī)器開始下一批次的加工，令k＝k＋1，則SMkj＝CM。

3）依照工件序列的優(yōu)先順序檢查所有未被安排的工件i是否可以放到批次k中進(jìn)行加工。若工件的釋放時間ri和機(jī)器的當(dāng)前完工時間CM最大者減去批次k的開始時間SMkj加上該工件的加工時間Pi不大于BL，即max{ri, CM}-SMkj＋Pi≤BL，則工件i可放到第k批次上加工，其開工時間STi＝max{ri, CM}，完工時間CTi＝STi＋Pi，此時機(jī)器的當(dāng)前完工時間CM＝CTi；否則工件i不可放到第k批次加工。重復(fù)直到所有工件檢查完。若所有工件都已安排，算法停止；否則，批次k加工完成，則CMkj＝CM，轉(zhuǎn)2）。

4 遺傳算法

遺傳算法基于達(dá)爾文的自然選擇原理，通過對候選解進(jìn)行選擇、交叉、變異等操作，模擬自然界的“優(yōu)勝劣汰”的自然選擇過程，反復(fù)迭代自動尋優(yōu)，最終得到問題的最優(yōu)解。根據(jù)工件加工調(diào)度問題的特點,具體設(shè)計了相應(yīng)的編碼、解碼方案及其遺傳算子。

4.1 編碼方案

用遺傳算法解決排序問題的首要任務(wù)就是對問題進(jìn)行編碼，即把一個解表示成一條染色體。假設(shè)有N個工件，M臺機(jī)器，則一條染色體I由兩部分組成，可表示為：

其中A＝(J1, J2, , JN)，Ji∈{1, 2, , N}為一個工件序列向量，表示所有工件的一個排列。R＝(MJ1, MJ2, , MJN)，MJi∈{1, 2, , N}為機(jī)器向量，表示工件序列向量中各工件對應(yīng)的加工機(jī)器。A和R中的基因分別稱為工件基因和機(jī)器基因?？芍旧w一旦確定，則工件分配的機(jī)器和每臺機(jī)器上的工件序列就可確定。如工件J1在機(jī)器 MJ1上加工，…，工件Ji在機(jī)器MJi上加工，…，依次類推。

4.2 解碼方案

每條染色體需要進(jìn)行解碼以得到每個工件的開始加工時間、完工時間及每臺機(jī)器維護(hù)時間。按照本文的編碼方法，每臺機(jī)器上的工件序列已經(jīng)固定，因此，對于每臺機(jī)器上工件的時間表可以按照第3節(jié)介紹的最先適配算法求解。

4.3 產(chǎn)生初始種群

設(shè)種群規(guī)模為popsize，初始種群中的每個染色體按照如下方法產(chǎn)生：首先隨機(jī)產(chǎn)生一個工件序列A＝(J1, J2, , JN)，每個工件基因均為1到N的整數(shù)；然后對于A中每個工件Ji從其機(jī)器集合(1, 2, , M)中隨機(jī)選擇一機(jī)器MJi組成機(jī)器向量R。

4.4 選擇

本文采用精英選擇策略，即從當(dāng)前群體中選擇h＝popsize×15%個最好的個體組成高質(zhì)量解集HQS，為了保持多樣性，需要設(shè)置一個閾值t，使HQS中每個個體之間的距離不小于t，其中兩個個體I1和I2間的距離d (I1, I2)定義為：

其中 ：

HQS被直接復(fù)制到下一代。若在當(dāng)前群體中沒有h個滿足條件的個體，則可以按照初始群體產(chǎn)生的方法隨機(jī)產(chǎn)生一些個體放到HQS中，以確保HQS中包含h個個體。

4.5 交叉

參與交叉的兩個個體，一個從種群中隨機(jī)選取，另一個從高質(zhì)量解集HQS中按順序依次選取。采用一點交叉方法進(jìn)行交叉，設(shè)參與交叉操作的兩個個體一個為母體，另一個為父體，經(jīng)交叉操作后產(chǎn)生兩個個體，一個為女兒，一個為兒子。具體操作為：隨機(jī)選擇一個正整數(shù)c (1＜c＜N)作為交叉點，女兒的工件序列向量和機(jī)器向量的前c個位置基因分別繼承母體的工件序列向量和機(jī)器向量的前c個基因，而女兒的工件鏈表的后N-c位置的基因來源于父體的機(jī)器向量，其中在女兒中已有的工件不再考慮，且保持其在父體中的相對位置；女兒后N-c位置的機(jī)器基因繼承其相應(yīng)位置的工件基因在父體中對位置的機(jī)器基因。產(chǎn)生兒子的方法與此相類似，只需交換父體和母體的位置即可。

4.6 變異

本文設(shè)計對染色體進(jìn)行兩次獨立變異， 變異1：染色體I中的工件序列向量A及機(jī)器向量中相應(yīng)的每個基因依變異概率發(fā)生變異，首先隨機(jī)產(chǎn)生兩個整數(shù)i, j∈{1, 2, , N}且i≠j，然后交換工件序列向量和機(jī)器向量中i和j位置上的基因。變異2：對染色體I中機(jī)器向量中每個機(jī)器基因MJi依變異概率發(fā)生變異，從機(jī)器集合{1, 2, , M}中隨機(jī)選一機(jī)器替換MJi。

5 實驗結(jié)果

為了驗證本文設(shè)計算法的有效性，隨機(jī)產(chǎn)生了280個算例，實驗設(shè)計的參數(shù)主要有訂單數(shù)N＝10, 20, 30, 50, 100, 150, 200；機(jī)器數(shù)M＝1, 2, 4,6。對于這兩個參數(shù)采用因子實驗設(shè)計法共設(shè)計28個實驗，對于每個實驗隨機(jī)產(chǎn)生10個算例，則共有280個算例。每個例子中訂單的加工時間服從區(qū)間[10, 35]均勻分布的整數(shù)，釋放時間服從區(qū)間[0, 48]的整數(shù)，機(jī)器最長持續(xù)工作時間BL＝40，機(jī)器維修時間為m＝3。

為了方便，稱采用最先適配算法解碼的遺傳算法為GA+FF。文獻(xiàn)[8]提出了求解帶有決策維護(hù)的并行機(jī)調(diào)度問題的啟發(fā)式算法，該算法是將各工件的加工時間按升序進(jìn)行排列，然后按照此排列的順序號除以機(jī)器數(shù)所得的余數(shù)加 ，作為對應(yīng)工件所進(jìn)行加工的機(jī)器號，最后每臺機(jī)器按照加工時間升序進(jìn)行排序計算各個工件的時間表。我們將此算法進(jìn)行了修改：分配給每臺機(jī)器的工件及工件序列方法與該算法相同，只是最后計算各工件的時間表時采用本文3節(jié)介紹的最先適配算法。將修改后的算法簡記為SPT+FF。

表1列出了GA+FF和SPT+FF兩個算法分別計算每個實驗中10個算例的總工期平均值。通過比較可以看出，GA+FF的計算結(jié)果都優(yōu)于算法SPT+FF。

表1 GA+FF和SPT+FF的總工期平均值

6 結(jié)束語

本文研究了多臺并行機(jī)工件動態(tài)到達(dá)的調(diào)度模型，對于預(yù)防性維護(hù)最小總完工時間問題，首先建立最先適配算法的模型對工件進(jìn)行安排，然后設(shè)計一種遺傳算法尋找工件的最優(yōu)排序，通過大量實驗與SPT+FF進(jìn)行了比較，說明GA+FF可以很好的解決該問題。

[1] R. H. P. M. ArtS, G. M. Knapp, M. J. Lawrence. Some aspects of measuring maintenance in the process industry[J]. Journal of Quality in Maintenance Engineering, 1998,4: 6-11.

[2] C.J. Liao, W. J. Chen. Single-machine scheduling with periodic maintenance and nonredeemable jobs [J].Computers and Operations Research, 2003, 30: 1335-1347.

[3] M. Ji, Y. He, T. C. E. Cheng. Single-machine scheduling with periodic maintenance to minimize makespan [J].Computers & Operations Research, 2007, 34: 764-1770.

[4] 周炳海, 蔣舒宇, 王世進(jìn), 吳斌, 奚立峰. 集成生產(chǎn)與預(yù)防性維護(hù)的流水線車間調(diào)度算法 [J]. 大連海事大學(xué)報,2007, 33(3): 32-35.

[5] M. Sbihi, C. Varnier. Single-machine scheduling with periodic and flexible periodic maintenance to minimize maximum tardiness [J]. Computers & Industrial Engineering, 2008, 55: 830-840.

[6] C. Low, M. Ti, Ch-J Hsu, Ch-T Su. Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance [J]. Applied mathematical modeling , 2010, 34: 334-342.

[7] Ch. Low, Ch-J Hsu , Ch-T Su. A modified particle swarm optimization algorithm for a single-machine scheduling problem with periodic maintenance [J]. Expert Systems with Applications.2010. 37: 6429-6434.

[8] 孫凱彪, 李金權(quán), 王加銀. 兩臺同型機(jī)多階段維護(hù)調(diào)度問題的若干結(jié)果 [J]. 北京師范大學(xué)學(xué)報(自然科學(xué)版),2008-04, 44(4): 343-347.