求解具有預防性維護的并行機調度的遺傳算法

李同玲，王 宏，林 丹

（天津大學 理學院，天津 300072）

1 概述

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

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

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

2 問題描述

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

3 給定工件序列的單機調度算法

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

初始化：令批次k＝1，SMkj＝0，機器的當前完工時間CM＝0。

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

2）進行第k批次的機器維護，從CMkj開始維護，維護的完工時間為CMkj＋m ，機器的當前完工時間CM＝CMkj。接著機器開始下一批次的加工，令k＝k＋1，則SMkj＝CM。

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

4 遺傳算法

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

4.1 編碼方案

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

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

4.2 解碼方案

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

4.3 產生初始種群

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

4.4 選擇

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

其中 ：

HQS被直接復制到下一代。若在當前群體中沒有h個滿足條件的個體，則可以按照初始群體產生的方法隨機產生一些個體放到HQS中，以確保HQS中包含h個個體。

4.5 交叉

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

4.6 變異

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

5 實驗結果

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

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

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

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

6 結束語

本文研究了多臺并行機工件動態到達的調度模型，對于預防性維護最小總完工時間問題，首先建立最先適配算法的模型對工件進行安排，然后設計一種遺傳算法尋找工件的最優排序，通過大量實驗與SPT+FF進行了比較，說明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]. 大連海事大學報,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] 孫凱彪, 李金權, 王加銀. 兩臺同型機多階段維護調度問題的若干結果 [J]. 北京師范大學學報(自然科學版),2008-04, 44(4): 343-347.