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

程貞敏, 陳先康

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

0 引 言

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

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

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

1 問題描述

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

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

1)n>m,即工件的個(gè)數(shù)嚴(yán)格多于機(jī)器的臺(tái)數(shù);

2) 同一時(shí)刻,每個(gè)工件最多在一臺(tái)機(jī)器上加工且一臺(tái)機(jī)器最多加工一個(gè)工件;

3) 所有的工件在零時(shí)刻是隨時(shí)準(zhǔn)備加工的。

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

2.1 設(shè)m臺(tái)機(jī)器中沒有機(jī)器需要維護(hù)

當(dāng)m臺(tái)機(jī)器中沒有機(jī)器需要維護(hù)時(shí),即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個(gè)任務(wù)按任意順序排成一列,將這一列分為m部分,當(dāng)1≤i≤n-zm時(shí),第i部分為[(i-1)(z+1)p,i(z+1)p];當(dāng)n-zm+1≤i≤m時(shí),第i部分為[(i-1)zp+(n-zm)p,izp+(n-zm)p],轉(zhuǎn)入步驟4。

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

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

2.2 設(shè)m臺(tái)機(jī)器中有部分機(jī)器需要進(jìn)行周期維護(hù)

當(dāng)m臺(tái)機(jī)器中有部分機(jī)器需要周期維護(hù)時(shí),有0

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

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

化簡有

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

(1)

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

化簡有

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

(2)

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

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

對于類型Ⅰ中最后一個(gè)工件在維護(hù)機(jī)器上加工時(shí)有下面的不等式

化簡有

即

(3)

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

0

進(jìn)一步化簡得

-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是唯一的。

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

算法2

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

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

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

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

對于類型Ⅰ中最后一個(gè)工件在非維護(hù)機(jī)器上加工時(shí)有下面的不等式

化簡有

(7)

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

0

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

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

(9)

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

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

k2p-p-k(T+w)

化簡有

(10)

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

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

算法3

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

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

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

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

2.3 設(shè)m臺(tái)機(jī)器中全部機(jī)器需要進(jìn)行周期維護(hù)

算法4

步驟2 把n個(gè)任務(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個(gè)任務(wù)按任意順序排成一列,將這一列分為m部分,即第i(1≤i≤m)部分為[(i-1)zp,izp],轉(zhuǎn)入步驟4。

3 結(jié) 語

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