考慮柔性維修的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]提出的問題分解方法降低了問題的求解難度。……