機(jī)器帶故障的三臺(tái)機(jī)排序問(wèn)題的兩個(gè)近似算法

葉賽英,徐弼軍

(浙江科技學(xué)院 理學(xué)院，杭州 310023)

?

機(jī)器帶故障的三臺(tái)機(jī)排序問(wèn)題的兩個(gè)近似算法

葉賽英,徐弼軍

(浙江科技學(xué)院 理學(xué)院，杭州 310023)

摘要:機(jī)器帶故障的m臺(tái)機(jī)的目標(biāo)函數(shù)為最小化誤工工件數(shù)的排序問(wèn)題，在m≥2時(shí)是NP(nondeterministic polynomial)困難的問(wèn)題，對(duì)m=3，當(dāng)工件轉(zhuǎn)移時(shí)間t=0和t≠0兩種情況，提出了和的近似算法，以及對(duì)應(yīng)的漸進(jìn)性能比，且證明了其界是緊的。

關(guān)鍵詞:排序；性能比；最小化誤工工件數(shù)；機(jī)器帶故障中斷；近似算法

在經(jīng)典的平行機(jī)排序問(wèn)題中，通常要求多臺(tái)機(jī)器性能完全相同，給定一個(gè)任意的等待加工的工件集，在滿足特定的約束條件下，求解一個(gè)排序，使給定的某個(gè)目標(biāo)函數(shù)最優(yōu)。單臺(tái)機(jī)下的誤工工件數(shù)最小化的問(wèn)題是有最優(yōu)算法的，按照Moore 算法可以得到問(wèn)題的最優(yōu)解[1-2]。如果考慮兩臺(tái)平行機(jī)，由于意外或不可抗力導(dǎo)致其中一臺(tái)機(jī)器發(fā)生故障中斷，那么，在該機(jī)器上加工的工件只能轉(zhuǎn)移到另外一臺(tái)正常工作的機(jī)器上去加工[3]，在目標(biāo)函數(shù)為最小化誤工工件數(shù)要求下，該問(wèn)題是NP(nondeterministic polynomial)困難的[4],文獻(xiàn)[5-7]給出了不同情況下兩臺(tái)機(jī)帶故障的近似算法。由于兩臺(tái)機(jī)問(wèn)題是NP困難的，從而三臺(tái)機(jī)問(wèn)題也是NP困難的[8]，本研究討論三臺(tái)機(jī)帶故障中斷下，目標(biāo)函數(shù)為誤工工件數(shù)最小化的問(wèn)題。

1問(wèn)題的提出

現(xiàn)有三臺(tái)相同的機(jī)器，將三臺(tái)機(jī)器上正在加工的工件集設(shè)為：

I={J11,J12,…,J1n1;J21,J22,…,J2n2;J31,J32,…,J3n3}，

其中，Jij為中斷前計(jì)劃在機(jī)器Mi上加工的第j個(gè)工件，加工時(shí)間為pij，n1+n2+n3=n。設(shè)機(jī)器Mi在初始的0時(shí)刻發(fā)生故障中斷，且中斷的持續(xù)時(shí)間很長(zhǎng)，在該機(jī)器上未完工的工件不可能等待機(jī)器恢復(fù)正常后再加工，不妨設(shè)中斷時(shí)長(zhǎng)D=∞，構(gòu)造0—1變量

定義1設(shè)在中斷發(fā)生時(shí)機(jī)器上正在加工的工件為跨越工件。

當(dāng)中斷發(fā)生時(shí)M1上未完成的工件集為S1，M2上的跨越工件為J2r，M2上未完成的工件集為S2，M3上的跨越工件為J3s，M3上未完成的工件集為S3。如圖1所示，其中灰色為中斷時(shí)三臺(tái)機(jī)上未完成的工件。

圖1　機(jī)器M1,M2,M3上原排序Fig.1　Original scheduling of machine M1,M2,M3

先考慮轉(zhuǎn)移時(shí)間為t1=t2=0的情況。

1)將工件集I1=S1∪S2∪S3按交工期限的單調(diào)非減順序排好;將排好序的工件按Moore算法依次分配給M2加工，記在M2上按期完工工件集為P2;將I1P2中工件按Moore算法依次分配給M3加工，記M3上按期完工工件集為P3;最后將I1{P2∪P3}中的工件以任意順序安排給M2或M3加工(M2先加工S2P2中工件，M3先加工S3P3中工件)，對(duì)應(yīng)序記為σ1。

2)將工件集I2=S1∪(S2{J2r})∪S3按交工期限的單調(diào)非減順序排好;將排好序的工件按Moore算法依次分配給M2在工件J2r后加工，記M2上按期完工工件集為D2;將I2D2中工件按Moore算法依次分配給M3加工，記M3上按期完工工件集為D3。最后將I2(D2∪D3)中工件以任意順序安排給M2或M3加工(M2先加工S2D2中工件，M3先加工S3D3中工件)，對(duì)應(yīng)序記為σ2。

3)將工件集I2=S1∪S2∪(S3{J2s})按交工期限的單調(diào)非減順序排好;將排好序的工件按Moore算法依次分配給M2加工，記M2上按期完工工件集為E2;將I2E2中工件按Moore算法依次分配給M3在工件J3s后加工，記M3上按期完工工件集為E3。最后將I2(E2∪E3)中工件以任意順序安排給M2或M3加工(M2先加工S2E2中工件，M3先加工S3E3中工件)，對(duì)應(yīng)序記為σ3。

4)將工件集I2=S1∪(S2{J2r})∪(S3{J3s})按交工期限的單調(diào)非減順序排好;將排好序的工件按Moore算法依次分配給M2在工件J2r后加工，記M2上按期完工工件集為F2;將I2F2中工件按Moore算法依次分配給M3在工件J3s后加工，記M3上按期完工工件集為F3。將I2(F2∪F3)中工件以任意順序安排給M2或M3加工(M2先加工S2F2中工件，M3先加工S3F3中工件)，對(duì)應(yīng)序記為σ4。

證明設(shè)在算法1中σi(1≤i≤4)下的M2上按期完工工件集為{Jp1,…,Jpk}，而由算法1最終得到的M2上按期完工工件集至多為A1={Jp1,…Jpk+1}，在算法1中σi(1≤i≤4)下的M3上按期完工工件集為Jq1,…,Jqr，由算法1最終得到M3上按期完工工件集至多為A2={Jq1,…Jqr+1}。

(1)

(2)

綜上所述，總有

(3)

又由

則

(4)

綜合式(3)、(4)得

(5)

此時(shí)，

(6)

式(6)成立。

故當(dāng)OPT(I)→+∞時(shí)，必有k→+∞，?ε>0,?正整數(shù)N;當(dāng)OPT(I)≥N時(shí),必有

(7)

此時(shí)，

(8)

上述證明說(shuō)明，不論何種情況發(fā)生，總有

(9)

證明設(shè)M2，M3上無(wú)跨越工件，設(shè)中斷發(fā)生時(shí)三臺(tái)機(jī)未完成工件依原最優(yōu)序排列為，S1={J11}，S2={J21,J22},S3={J31,J32}，p31=1，p11=p21=p22=2，p32=4，由此可知，C11=C21=2，C22=4，C31=1，C32=5。

按算法1，將J31，J22安排在M2上加工，J11安排在M3上加工，J21，J32為誤工工件，以任意序最后安排在M2或M3上加工。

考慮t1≠t2的情況，為不失一般性，不妨設(shè)t1

設(shè)機(jī)器M1在0時(shí)刻發(fā)生中斷，中斷發(fā)生后，一方面，由于M1上未完成的工件轉(zhuǎn)移到當(dāng)中其他一臺(tái)機(jī)器，最快也要t1時(shí)刻，從而機(jī)器M1上按原序所安排的t1時(shí)刻之前開工的工件沒(méi)來(lái)得及轉(zhuǎn)移就已經(jīng)誤工了，由此只需要考慮M1上按原序所安排的t1時(shí)刻之后加工的工件。另一方面，由于t2>t1，機(jī)器M1上原序所安排的t1時(shí)刻之后且t2時(shí)刻之前開工的工件來(lái)不及轉(zhuǎn)移就已經(jīng)誤工了，把這些來(lái)不及開工的工件記為啞工件，并記這些工件組成的集合為R。

記M1上t1時(shí)刻未完成的工件組成工件集為S1，在t1時(shí)刻機(jī)器M2上未完成的工件集為S2，此時(shí)設(shè)M2上的跨越工件為J2r，在t2時(shí)刻機(jī)器M3上未完成的工件集為S3，此時(shí)設(shè)M3上的跨越工件為J3s。如圖2所示，其中灰色為中斷時(shí)三臺(tái)機(jī)上未完成的工件。

圖2　機(jī)器M1,M2,M3上原排序Fig.2　Original scheduling of machine M1,M2,M3

1)將工件集I1=S1∪S2∪S3按交工期限的單調(diào)非減順序排好;在t1時(shí)刻將排好序的工件按Moore算法依次分配給M2加工(若首個(gè)工件為J2r，則繼續(xù)，不中斷之)，記在M2上按期完工工件集為P2;將I1(P2∪R)中工件在t2時(shí)刻按Moore算法依次分配給M3加工(若首個(gè)工件為J3s，則繼續(xù)，不中斷之)，記在M3上按期完工工件集為P3;最后以任意順序安排給M2或M3加工I1{P2∪P3}及所有啞工件，對(duì)應(yīng)序記為σ1。

2)將工件集I1=S1∪(S2{J2r})∪S3按交工期限的單調(diào)非減順序排好;在C2r時(shí)刻將排好序的工件按Moore算法依次分配給M2加工，記在M2上按期完工工件集為D2;將I1(D2∪R)中工件在t2時(shí)刻按Moore算法依次分配給M3加工(若首個(gè)工件為J3s，則繼續(xù)，不中斷之)，記在M3上按期完工工件集為D3;最后以任意順序安排給M2或M3加工I1{D2∪D3}及所有啞工件，對(duì)應(yīng)序記為σ2。

3)將工件集I1=S1∪S2∪(S3{J3s})按交工期限的單調(diào)非減順序排好;在t1時(shí)刻將排好序的工件按Moore算法依次分配給M2加工(若首個(gè)工件為J2r，則繼續(xù)，不中斷之)，記在M2上按期完工工件集為E2;將I1(E2∪R)中工件在C3s時(shí)刻按Moore算法依次分配給M3加工(若首個(gè)工件為J3s，則繼續(xù)，不中斷之)，記在M3上按期完工工件集為E3;最后以任意順序安排給M2或M3加工I1{E2∪E3}及所有啞工件，對(duì)應(yīng)序記為σ3。

4)將工件集I1=S1∪(S2{J2r})∪(S3{J3s})按交工期限的單調(diào)非減順序排好;在C2r時(shí)刻將排好序的工件按Moore算法依次分配給M2加工，記在M2上按期完工工件集為F2;將I1(F2∪R)中工件在C3s時(shí)刻按Moore算法依次分配給M3加工，記在M3上按期完工工件集為F3;最后以任意順序安排給M2或M3加工I1{F2∪F3}及所有啞工件，對(duì)應(yīng)序記為σ4。

證明分兩種情況討論。

故

(10)

(11)

綜上所述，不管發(fā)生何種情況，不等式

(12)

總成立，而A(I)=(k+1)+(r+1),故此時(shí)必有

定理證畢。

4算法的計(jì)算復(fù)雜性

Moore算法復(fù)雜性為O(nlogn)，由于算法1中4次利用Moore算法，從而算法1的時(shí)間復(fù)雜性為O(nlogn)。算法2也是4次利用Moore算法，從而算法2的時(shí)間復(fù)雜性仍為O(nlogn)。

5結(jié)語(yǔ)

目前在機(jī)器故障中斷的問(wèn)題上，國(guó)內(nèi)外相關(guān)研究成果并不太多，而該問(wèn)題具有廣泛的現(xiàn)實(shí)意義，且待研究的問(wèn)題還有很多。筆者認(rèn)為，可以結(jié)合機(jī)器有不同就緒時(shí)間的問(wèn)題和工件有就緒時(shí)間的問(wèn)題，在P(polynomial)問(wèn)題上尋求新的最優(yōu)算法及對(duì)NP困難問(wèn)題尋求更好的近似算法。

參考文獻(xiàn):

[1]MOOREJM.Annjob,onemachinesequencingalgorithmforminimizingthenumberoflatejobs[J].ManagementScience,1968,15(3):102.

[2]王方,趙傳立.具有學(xué)習(xí)效應(yīng)的且加工時(shí)間可控的單機(jī)排序問(wèn)題[J].沈陽(yáng)師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，2013(4):471.

[3]唐國(guó)春,張峰,羅守成,等.現(xiàn)代排序論[M].上海:上?？茖W(xué)普及出版社，2003.

[4]LEECY,YUG.Singlemachineschedulingunderpotentialdisruption[J].OperationsResearchLetters,2007(35):1.

[5]沈?yàn)?，楊啟?兩臺(tái)機(jī)器及時(shí)完工工件數(shù)最大化問(wèn)題的近似算法[J].高校應(yīng)用數(shù)學(xué)學(xué)報(bào):A輯,2003，18(2)：207.

[6]葉賽英，沈?yàn)?，魏小蘭.機(jī)器帶故障的兩臺(tái)機(jī)排序問(wèn)題的一個(gè)近似算法[J].杭州電子科技大學(xué)學(xué)報(bào),2008，28(2)：90.

[7]葉春花,沈?yàn)?機(jī)器帶中斷的誤工問(wèn)題的近似排序算法[J].杭州電子科技大學(xué)學(xué)報(bào),2010，30(1):96.

[8]魏飛,劉守鵬.工件帶拒絕費(fèi)用的三臺(tái)單機(jī)排序問(wèn)題研究[J].山東科學(xué),2013(6):9.

[9]盧開澄.算法與復(fù)雜性[M].北京：高等教育出版社，1995.

Two approximation algorithms for three parallel machines scheduling with machine disruptions

YE Saiying, XU Bijun

(School of Sciences, Zhejiang University of Science and Technology, Hangzhou 310023, China)

Abstract:We discuss the problem of m parallel machines scheduling with disruptions with the objective of minimizing the sum of unit penalties. If m≥2, the problem is NP-hard. When m=3 and transfer time is t=0 and t≠0, two approximation algorithms are proposed for the problems of and respectively. And the paper proves that the upper bound is tight respectively.

Keywords:scheduling; worst-case ratio; minimizing the sum of unit penalties; machine disruptions; approximation algorithm

中圖分類號(hào):O223

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1671-8798(2016)01-0012-07

作者簡(jiǎn)介:葉賽英(1980—), 女, 浙江省松陽(yáng)人, 講師, 碩士, 主要從事排序問(wèn)題研究。

基金項(xiàng)目:浙江省《基礎(chǔ)數(shù)學(xué)》重點(diǎn)學(xué)科建設(shè)學(xué)術(shù)研究子項(xiàng)目(20131029)

收稿日期:2015-11-01

doi:10.3969/j.issn.1671-8798.2016.01.003

浙江科技學(xué)院學(xué)報(bào),第28卷第1期,2016年2月

Journal of Zhejiang University of Science and Technology

Vol.28 No.1, Feb. 2016