混合周期維護平行機調(diào)度問題

程貞敏, 陳先康

(貴州大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院, 貴陽 550025)

0 引 言

早在1974年, Baker[1]將調(diào)度問題定義為“完成若干項任務(wù)而對資源按時間進行分配的問題”,換句話說“調(diào)度問題是將資源分配給一定時間內(nèi)不同任務(wù),本質(zhì)上是對任務(wù)合理地安排以達到某種條件下的最優(yōu)結(jié)果的一個決策過程”[2]。

調(diào)度問題的研究在過去很長一段時間內(nèi)都集中于經(jīng)典調(diào)度問題的研究,也就是說通?？紤]機器在加工的過程中不需要進行周期維護,但在現(xiàn)實生活中的情況往往比較復(fù)雜,有時就要求考慮機器維護的問題。關(guān)于機器維護的問題過去也有很多學(xué)者研究過。2007年, Ji[3]等討論了帶周期性維護且目標(biāo)函數(shù)為最小化時間表長的單機排序問題,并證明了經(jīng)典LPT算法的最壞情況界為2,且該問題不存在最壞情況界小于2的多項式時間算法。同年,宣競[4]討論了帶周期性維護時間的平行機排序問題,并證明了P1|periodic-maintenance|Cmax在線情況的最優(yōu)算法,算法競爭比為2。2012年,喬鈺[5]討論了機器具有不可用區(qū)間的平行機排序問題,其中第1臺機器上有一段不可用區(qū)間,而第2臺機器可以連續(xù)使用,工件在加工過程中不可以中斷,目標(biāo)函數(shù)為極小化時間表長。 喬鈺在文中給出了精確算法和FPTAS算法來解決這個問題,并證明FPTAS算法的時間復(fù)雜性是o(n4/ε3)。2014年,Yu等[6]考慮了具有周期維護和不可中斷的單機調(diào)度問題,目標(biāo)函數(shù)是最小化時間表長,結(jié)果表明經(jīng)典的列表算法(LS)、最長時間表長優(yōu)先算法(LPT)和改進的最長時間優(yōu)先算法(MLPT)算法對于所考慮的問題都具有相同的最壞情況比和相同的計算復(fù)雜度。2015年,王婷[7]研究了一個帶有工具更換和固定周期維護的混合型平行機最小化時間表長調(diào)度問題,最后給出了一個基于經(jīng)典的LPT算法的啟發(fā)式算法LPTP和一個基于經(jīng)典的LS算法的啟發(fā)式算法LSP。2016年,Xu等[8]研究了具有固定維修周期或柔性維修周期的預(yù)防性維修的單機調(diào)度問題,生產(chǎn)計劃中的2個共同目標(biāo)最小化時間表長和總流程時間都被用來評估生產(chǎn)和維護計劃的集成。根據(jù)裝箱問題,給出了2種方案和2種目標(biāo)的4種配方。

類似的研究[9-12]近幾年也是愈來愈多,不過從上面可以看出,都只是基于機器有限的情況作出分析,甚至有的假設(shè)工件的數(shù)量小于機器的數(shù)量,或者是簡單的給出了一個下界等。本研究主要考慮了部分機器需要維護,工件加工時間相同且不允許中斷,同時工件數(shù)量嚴格大于機器數(shù)量,目標(biāo)函數(shù)為最小化時間表長的調(diào)度問題。這對于一些車間甚至是企業(yè)在預(yù)先判斷交貨時間方面有著重要的理論意義。

1 問題描述

有m臺機器,其中有m1臺機器需要周期維護,而余下的m-m1臺機器不需要周期維護,不失一般性,不妨設(shè)機器M1,M2,…,Mm1需要周期維護,各自的維護周期相同且記為T,維護時長也相同記為w,而機器Mm1+1,…,Mm不需要周期維護,現(xiàn)將n(n>m)個加工時長都為p的工件放在m臺機器上加工,工件在加工的過程中不可以中斷,目標(biāo)函數(shù)是最小化時間表長。

上述調(diào)度問題用三元法[13]表示為Pm,Pm1PM|pj=p|Cmax,其中Pm1PM表示有m1臺機器需要周期維護。工件加工需滿足如下條件:

1)n>m,即工件的個數(shù)嚴格多于機器的臺數(shù);

2) 同一時刻,每個工件最多在一臺機器上加工且一臺機器最多加工一個工件;

3) 所有的工件在零時刻是隨時準備加工的。

2 根據(jù)維護機器數(shù)量的不同將調(diào)度問題分3種情況討論

2.1 設(shè)m臺機器中沒有機器需要維護

當(dāng)m臺機器中沒有機器需要維護時,即m1=0,則調(diào)度問題Pm,Pm1PM|pj=p|Cmax就轉(zhuǎn)化為經(jīng)典的調(diào)度問題Pm|pj=p|Cmax[14],對于m1=0的情況有如下的算法:

算法1

步驟2 把n個任務(wù)按任意順序排成一列,將這一列分為m部分,當(dāng)1≤i≤n-zm時,第i部分為[(i-1)(z+1)p,i(z+1)p];當(dāng)n-zm+1≤i≤m時,第i部分為[(i-1)zp+(n-zm)p,izp+(n-zm)p],轉(zhuǎn)入步驟4。

步驟3 把n個任務(wù)按任意順序排成一列,將這一列平均分為m部分,即第(1≤i≤m)部分為[(i-1)zp,izp],轉(zhuǎn)入步驟4。

步驟4 把第i(其中i=1,…,m)部分放在處理機Pi上加工直至完成。

2.2 設(shè)m臺機器中有部分機器需要進行周期維護

當(dāng)m臺機器中有部分機器需要周期維護時,有0

根據(jù)最優(yōu)調(diào)度中最后一個工件的完工時刻是否在機器的維護時間段內(nèi),可以將問題分作2類,當(dāng)最后一個工件的完工時刻在非維護段時記為類型Ⅰ,當(dāng)最后一個工件的完工時刻在維護段時記為類型Ⅱ。

對于類型Ⅰ,k滿足以下不等式:

化簡有

最終得到對應(yīng)類型Ⅰ關(guān)于k的不等式為

(1)

對于類型Ⅱ,k滿足以下不等式:

化簡有

最終得到對應(yīng)類型Ⅱ關(guān)于k的不等式為

(2)

定理2 滿足不等式(1)或者不等式(2)的正整數(shù)k如果存在,則k是唯一的。反之,給定一組加工時間相等的工件和一組部分需要維護的機器,則工件在機器上加工的最優(yōu)時間表長Cmax一定滿足類型Ⅰ和類型Ⅱ中的一種,并且對應(yīng)于類型Ⅰ或者類型Ⅱ的正整數(shù)k是唯一的。

對于類型Ⅰ,根據(jù)最后的最優(yōu)時間表長Cmax是否處于維護機器又可細分為2種情況,記最后一個工件在維護機器上加工時為情況一,最后一個工件在非維護機器上加工時為情況二。另外記k1為所有需周期維護的機器中在最后一個非維護時間段上加工工件數(shù)量最多的個數(shù),k2為所有非維護機器中加工完所有工件時加工工件最多的個數(shù)。

對于類型Ⅰ中最后一個工件在維護機器上加工時有下面的不等式

化簡有

即

(3)

另外對于類型Ⅰ中最后一個工件在維護機器上加工時還應(yīng)滿足

0

進一步化簡得

-k(T+w)

(4)

由式(3)和式(4)得到關(guān)于k1的不等式有

(5)

和k一樣,如果這樣的k1存在,則k1是唯一的,由于工件在加工過程中不可中斷,則k1都只能取正整數(shù),而且關(guān)于k1的不等式(5)右邊與左邊之差小于1,所以k1是唯一的。

對于k2由不等式(4)則有

(6)

同理k2也只能取正整數(shù),并且如果這樣的k2存在則由不等式(6)知k2是唯一的。

歸納上述推理,最終得到一個當(dāng)最后一個工件在維護機器上加工時的算法,具體如下:

算法2

步驟1 根據(jù)不等式(1)、(5)、(6)以及k,k1,k2的唯一性計算k,k1,k2,如果k,k1,k2都存在,則繼續(xù)步驟2,否則終止。

步驟2 驗證不等式(3)、(4),如果不等式(3)、(4)都成立則繼續(xù)步驟3,否則終止。

定理3 對于給定的工件和機器數(shù)量,如果滿足不等式(5)、(6)的k1,k2存在,且不等式(3)、式(4)也成立,則由算法2得到的時間表長為最優(yōu)時間表長且Cmax=k(T+w)+k1p。

證明 由不等式(3)～(6)的推導(dǎo)可知定理成立。

對于類型Ⅰ中最后一個工件在非維護機器上加工時有下面的不等式

化簡有

(7)

除此之外,另外對于類型Ⅰ中最后一個工件在非維護機器上加工時還應(yīng)滿足

0

綜合以上推斷可得到下面的不等式

化簡上述不等式(8),最后得到關(guān)于k2的不等式為

(9)

如果這樣的k2存在,則k2是唯一的,由于工件在加工過程中不可中斷,則k2只能取正整數(shù),而且由不等式(9)知k2是唯一的。

對于k1則由不等式(8)可以得到

k2p-p-k(T+w)

化簡有

(10)

由不等式(10)知k1也是存在唯一的。

歸納上述,最終得到一個當(dāng)最后一個工件在非維護機器上加工時的算法,具體如下:

算法3

步驟1 根據(jù)不等式(1)、(9)、(10)以及k,k1,k2的唯一性計算k,k1,k2,如果k,k1,k2存在,則繼續(xù)步驟2,否則終止。

步驟2 驗證不等式(7)、(8),如果不等式(7)、(8)都成立則繼續(xù)步驟3,否則終止。

定理4 對于給定的工件和機器數(shù)量,如果存在滿足不等式(9)、(10)的k1,k2,且不等式(7)、(8)也成立,則由算法3得到的時間表長為最優(yōu)時間表長,且Cmax=k2p。

證明 由不等式(7)～(10)的推導(dǎo)過程知定理成立。

2.3 設(shè)m臺機器中全部機器需要進行周期維護

算法4

步驟2 把n個任務(wù)按任意順序排成一列,將這一列分為m部分,其中第i(1≤i≤n-zm)部分為[(i-1)(z+1)p,i(z+1)p],第i(n-zm+1≤i≤m)部分為[(i-1)zp+(n-zm)p,izp+(n-zm)p],轉(zhuǎn)入步驟4。

步驟3 把n個任務(wù)按任意順序排成一列,將這一列分為m部分,即第i(1≤i≤m)部分為[(i-1)zp,izp],轉(zhuǎn)入步驟4。

3 結(jié) 語

文章主要研究了加工時長相等,且在加工過程中不可中斷的n個工件被放在m臺平行機上加工的調(diào)度問題,其中m臺機器中部分機器需要周期維護,目標(biāo)函數(shù)為最小化時間表長的平行機調(diào)度問題Pm,Pm1PM|pj=p|Cmax。本文根據(jù)周期維護的機器數(shù)量不同,提出了相應(yīng)的求解的4個算法,并證明了通過相應(yīng)的算法得到的時間表長為最優(yōu)時間表長。后續(xù)將對工件具有不同加工時間的周期維護問題作進一步思考。