考慮柔性維修的job-shop調(diào)度問(wèn)題及啟發(fā)式算法①

摘 要:機(jī)器設(shè)備在計(jì)劃調(diào)度期間需要一段固定的時(shí)間去從事維修，這種情況在機(jī)械制造、IC測(cè)試等領(lǐng)域是經(jīng)常發(fā)生的。文章首先對(duì)考慮柔性維修的job-shop調(diào)度問(wèn)題的進(jìn)行了分析并證明該問(wèn)題是NP-hard，然后對(duì)最優(yōu)方案的選擇進(jìn)行了證明。文章提出的調(diào)度目標(biāo)是最小化最大完工時(shí)間。針對(duì)本問(wèn)題的特性，提出了啟發(fā)式算法并編寫(xiě)程序進(jìn)行計(jì)算實(shí)驗(yàn)。

關(guān)鍵詞:job-shop調(diào)度柔性維修啟發(fā)式算法

中圖分類號(hào):TP301文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1674-098X(2011)06(c)-0044-01

在計(jì)劃調(diào)度期間機(jī)器設(shè)備經(jīng)常會(huì)因?yàn)楦鞣N原因需要進(jìn)行維修而出現(xiàn)不能使用的情況，類似問(wèn)題也經(jīng)常發(fā)生在集成電路測(cè)試等領(lǐng)域的作業(yè)調(diào)度中[1]。本文的研究目標(biāo)是尋找考慮柔性維修的job-shop調(diào)度問(wèn)題的最小化最大完工時(shí)間，并作出如下假設(shè)。

(1)機(jī)器的維修期是已經(jīng)預(yù)先安排的，是進(jìn)行維修時(shí)機(jī)器啟動(dòng)(或停止)的最早(或最遲)時(shí)間。(2)機(jī)器停下來(lái)進(jìn)行維修或調(diào)整所需要的時(shí)間是固定的且不長(zhǎng)于維修期(如)。(3)機(jī)器不能使用的時(shí)間是已知的且不允許作業(yè)優(yōu)先權(quán)。

本文首先對(duì)提出的問(wèn)題的復(fù)雜性進(jìn)行討論并證明其為NP-hard，同時(shí)提出考慮柔性維修的最優(yōu)調(diào)度方案的優(yōu)選規(guī)則，然后提出啟發(fā)式算法并進(jìn)行數(shù)值計(jì)算以證明其運(yùn)算效率。

1 考慮柔性維修的job-shop調(diào)度方案

本節(jié)首先對(duì)考慮維修的單機(jī)調(diào)度問(wèn)題的復(fù)雜性進(jìn)行分析，并證明該問(wèn)題是NP-hard。代表機(jī)器需要處理的作業(yè)。

定理1 擬議的問(wèn)題是NP-hard。

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

分割:給定正整數(shù)的，如果存在一個(gè)子集，那么？

對(duì)于給定的分割，模擬問(wèn)題的實(shí)例如下。

(1)

(2)

下面將證明有且僅有分割上述實(shí)例有最大完工時(shí)間的最優(yōu)調(diào)度方案時(shí)，分割有相應(yīng)解。

如果分割有一個(gè)解，那么就會(huì)有一個(gè)最大完工時(shí)間為的最優(yōu)調(diào)度方案。如果分割沒(méi)有解，那么將證明上述實(shí)例的任何調(diào)度方案的最大完工時(shí)間將大于。

對(duì)于任何給定的調(diào)度方案，

。假設(shè)不允許作業(yè)優(yōu)先且分割沒(méi)有解，對(duì)于，我們將得到

(3)

因此如果分割沒(méi)有解，那么最大完工時(shí)間就大于。也就是說(shuō)，有且只有最優(yōu)調(diào)度方案的最小最大完工時(shí)間時(shí)，分割才會(huì)有解。

定理2 如果且在之后按任意順序指派作業(yè)，那么所產(chǎn)生的調(diào)度方案就是最優(yōu)調(diào)度。

證明 如果，那么我們很容易發(fā)現(xiàn)在之前沒(méi)有作業(yè)可以被處理，并且機(jī)器的最小準(zhǔn)備時(shí)間為。因此，在之后按任意順序指派作業(yè)是最優(yōu)調(diào)度方案。

定理3 如果且在0之后按任意順序指派作業(yè)，那么定理2產(chǎn)生的調(diào)度方案就是最優(yōu)調(diào)度。

證明 如果，那么我們很容易發(fā)現(xiàn)在之前所有作業(yè)都是可以處理的。因此，在0之后按任意順序指派作業(yè)是最優(yōu)調(diào)度方案。

2 啟發(fā)式算法及算例

針對(duì)生產(chǎn)實(shí)際中機(jī)器維修以及其他多項(xiàng)約束條件的情況，本節(jié)提出了最小化最大完工時(shí)間的job-shop調(diào)度問(wèn)題的啟發(fā)式算法，具體如下。

步驟1 采用LPT規(guī)則確定作業(yè)排序

采用最長(zhǎng)處理時(shí)間(LPT)規(guī)則對(duì)作業(yè)進(jìn)行排序，即按照加工時(shí)間的遞減順序?qū)ψ鳂I(yè)進(jìn)行排序。為不失一般性，令代表LPT規(guī)則對(duì)作業(yè)的排序。

令，然后轉(zhuǎn)步驟2。

步驟2 確定次優(yōu)的作業(yè)排序

如果，那么在中指派作業(yè)k，否則在中指派作業(yè)k。

令并進(jìn)入步驟3。

步驟3 確定完工時(shí)間

如果，則轉(zhuǎn)到步驟2。否則，停止該算法并計(jì)算完工時(shí)間

(4)

步驟1、步驟2的復(fù)雜性分別為、，故該算法的復(fù)雜度是。同時(shí)我們注意到反復(fù)使用本算法也可以解決超過(guò)一個(gè)維修周期間隔的延長(zhǎng)情況。

3 啟發(fā)式算法的效率評(píng)價(jià)

為了評(píng)價(jià)上節(jié)提出的啟發(fā)式算法的計(jì)算效率，啟發(fā)式算法程序采用Visual Basic編寫(xiě)，在Pentium4 3.0G個(gè)人電腦上運(yùn)行。對(duì)于下面提出的所有測(cè)試問(wèn)題，本算法的計(jì)算時(shí)間均少于1秒。

首先根據(jù)以下假設(shè)條件以隨機(jī)生成測(cè)試用的360個(gè)問(wèn)題，每種類型有30個(gè)實(shí)驗(yàn)問(wèn)題。

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

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

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

(4)，，。

(5)t 等于。

對(duì)于這些隨機(jī)問(wèn)題計(jì)算其百分比誤差，其中是啟發(fā)式算法計(jì)算出來(lái)的最大完工時(shí)間。假設(shè)機(jī)器的作業(yè)加工是連續(xù)進(jìn)行的，是最大完工時(shí)間的下界并由下式進(jìn)行估計(jì):

。

由于本問(wèn)題是NP-hard，所以這個(gè)計(jì)算結(jié)果是令人滿意的。

4 結(jié)論

本文的研究目標(biāo)是尋找考慮柔性維修的job-shop調(diào)度問(wèn)題的最小化最大完工時(shí)間。本文首先對(duì)該問(wèn)題的復(fù)雜性進(jìn)行了分析，并證明該問(wèn)題是NP-hard，然后對(duì)最優(yōu)方案的選擇進(jìn)行了證明。針對(duì)本問(wèn)題的特性，本文提出了啟發(fā)式算法并編寫(xiě)程序進(jìn)行計(jì)算實(shí)驗(yàn)。從計(jì)算實(shí)驗(yàn)結(jié)果可知，該算法的性能是令人滿意的，可以為解決大型復(fù)雜調(diào)度問(wèn)題提供一個(gè)有效的求解程序。

參考文獻(xiàn)

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