考慮柔性維修的job-shop調度問題及啟發式算法①

摘 要:機器設備在計劃調度期間需要一段固定的時間去從事維修，這種情況在機械制造、IC測試等領域是經常發生的。文章首先對考慮柔性維修的job-shop調度問題的進行了分析并證明該問題是NP-hard，然后對最優方案的選擇進行了證明。文章提出的調度目標是最小化最大完工時間。針對本問題的特性，提出了啟發式算法并編寫程序進行計算實驗。

關鍵詞:job-shop調度柔性維修啟發式算法

中圖分類號:TP301文獻標識碼:A文章編號:1674-098X(2011)06(c)-0044-01

在計劃調度期間機器設備經常會因為各種原因需要進行維修而出現不能使用的情況，類似問題也經常發生在集成電路測試等領域的作業調度中[1]。本文的研究目標是尋找考慮柔性維修的job-shop調度問題的最小化最大完工時間，并作出如下假設。

(1)機器的維修期是已經預先安排的，是進行維修時機器啟動(或停止)的最早(或最遲)時間。(2)機器停下來進行維修或調整所需要的時間是固定的且不長于維修期(如)。(3)機器不能使用的時間是已知的且不允許作業優先權。

本文首先對提出的問題的復雜性進行討論并證明其為NP-hard，同時提出考慮柔性維修的最優調度方案的優選規則，然后提出啟發式算法并進行數值計算以證明其運算效率。

1 考慮柔性維修的job-shop調度方案

本節首先對考慮維修的單機調度問題的復雜性進行分析，并證明該問題是NP-hard。代表機器需要處理的作業。

定理1 擬議的問題是NP-hard。

證明 首先證明文獻[2]提出的問題分解方法降低了問題的求解難度。下面是一個眾所周知的NP-hard完全問題:

分割:給定正整數的，如果存在一個子集，那么？

對于給定的分割，模擬問題的實例如下。

(1)

(2)

下面將證明有且僅有分割上述實例有最大完工時間的最優調度方案時，分割有相應解。

如果分割有一個解，那么就會有一個最大完工時間為的最優調度方案。如果分割沒有解，那么將證明上述實例的任何調度方案的最大完工時間將大于。

對于任何給定的調度方案，

。假設不允許作業優先且分割沒有解，對于，我們將得到

(3)

因此如果分割沒有解，那么最大完工時間就大于。也就是說，有且只有最優調度方案的最小最大完工時間時，分割才會有解。

定理2 如果且在之后按任意順序指派作業，那么所產生的調度方案就是最優調度。

證明 如果，那么我們很容易發現在之前沒有作業可以被處理，并且機器的最小準備時間為。因此，在之后按任意順序指派作業是最優調度方案。

定理3 如果且在0之后按任意順序指派作業，那么定理2產生的調度方案就是最優調度。

證明 如果，那么我們很容易發現在之前所有作業都是可以處理的。因此，在0之后按任意順序指派作業是最優調度方案。

2 啟發式算法及算例

針對生產實際中機器維修以及其他多項約束條件的情況，本節提出了最小化最大完工時間的job-shop調度問題的啟發式算法，具體如下。

步驟1 采用LPT規則確定作業排序

采用最長處理時間(LPT)規則對作業進行排序，即按照加工時間的遞減順序對作業進行排序。為不失一般性，令代表LPT規則對作業的排序。

令，然后轉步驟2。

步驟2 確定次優的作業排序

如果，那么在中指派作業k，否則在中指派作業k。

令并進入步驟3。

步驟3 確定完工時間

如果，則轉到步驟2。否則，停止該算法并計算完工時間

(4)

步驟1、步驟2的復雜性分別為、，故該算法的復雜度是。同時我們注意到反復使用本算法也可以解決超過一個維修周期間隔的延長情況。

3 啟發式算法的效率評價

為了評價上節提出的啟發式算法的計算效率，啟發式算法程序采用Visual Basic編寫，在Pentium4 3.0G個人電腦上運行。對于下面提出的所有測試問題，本算法的計算時間均少于1秒。

首先根據以下假設條件以隨機生成測試用的360個問題，每種類型有30個實驗問題。

(1)n等于10，20，30，40，50，60，70，80，90，100，150或200。

(2)是[5，15]區間的均勻分布。

(3)r 是[1，15]或[16，30]的均勻分布。

(4)，，。

(5)t 等于。

對于這些隨機問題計算其百分比誤差，其中是啟發式算法計算出來的最大完工時間。假設機器的作業加工是連續進行的，是最大完工時間的下界并由下式進行估計:

。

由于本問題是NP-hard，所以這個計算結果是令人滿意的。

4 結論

本文的研究目標是尋找考慮柔性維修的job-shop調度問題的最小化最大完工時間。本文首先對該問題的復雜性進行了分析，并證明該問題是NP-hard，然后對最優方案的選擇進行了證明。針對本問題的特性，本文提出了啟發式算法并編寫程序進行計算實驗。從計算實驗結果可知，該算法的性能是令人滿意的，可以為解決大型復雜調度問題提供一個有效的求解程序。

參考文獻

[1]Pinedo，M. Scheduling:Theory，Algorithms and System[M]. Prentice Hall，Englewood Cliffs，New Jersey，1995.