機(jī)器帶中斷的誤工問(wèn)題的近似排序算法

葉春花,沈 灝

(杭州電子科技大學(xué)理學(xué)院,浙江杭州310018)

0 引 言

本文研究生產(chǎn)計(jì)劃制定后機(jī)器突發(fā)故障時(shí)的應(yīng)急排序問(wèn)題。文獻(xiàn)1提出了考慮工件移機(jī)運(yùn)輸時(shí)間的機(jī)器帶故障的兩臺(tái)平行機(jī)排序問(wèn)題。文獻(xiàn)2考慮了機(jī)器中斷,但沒(méi)有考慮不確定因素。文獻(xiàn)3提出了P2|D=∞,T≠0|∑U′ij問(wèn)題的一個(gè)差界算法。文獻(xiàn)4提出了單臺(tái)機(jī)誤工工件數(shù)最小化問(wèn)題的算法,這個(gè)算法稱為Moore-Hodgson算法。文獻(xiàn)5給出Moore-Hodgson算法最優(yōu)性的證明。本文考慮一般的中斷時(shí)間D,分別討論T=0和T≠0情況下的排序問(wèn)題P2|D,T|∑U′ij。

1 問(wèn)題介紹

考察如下排序問(wèn)題:設(shè)有兩臺(tái)平行機(jī)M1,M2。Jij為中斷前計(jì)劃在機(jī)器Mi上加工的第j個(gè)工件,Jij的加工時(shí)間為Pij。其中一臺(tái)機(jī)器在不可知情況下中斷,假設(shè)中斷開(kāi)始時(shí)間為t1,終止時(shí)間為t2,持續(xù)時(shí)間為D=t2-t1。設(shè)Cij表示原計(jì)劃中 Jij的完工時(shí)間,表示重新排序后 Jij的完工時(shí)間,令 U′ij=決策者在t=t1重新排序,目標(biāo)使∑U′ij為最小。不失一般性,假設(shè)M 1中斷 ,M 1工件可以轉(zhuǎn)移到M2加工 ,M1恢復(fù)后 ,M2工件也可以轉(zhuǎn)移到M1加工 ,轉(zhuǎn)移時(shí)間為T,分兩種情況討論:問(wèn)題1,P2|D,T=0|∑U′ij;問(wèn)題2,P2|D,T≠0|∑U′ij。

2 算法及定理

2.1 問(wèn)題1 P2|D=∞,T=0|的算法

設(shè)t1時(shí)刻,M1,M 2上正在加工的工件為J1s,J2e。t2時(shí)刻,M1,M2上正在加工的工件為J1t,J2f。若C1t≤C2f,如圖 1所示,若 C1t＞C2f,如圖2所示。

步驟1 若C1t＞C2f,那么在工件J2f后依次選取h個(gè)M2工件使得將前h-1個(gè)工件轉(zhuǎn)移到M1上從t2時(shí)刻開(kāi)始按M2上的先后序加工。若C2e-t1≥P1s,則轉(zhuǎn)步驟2,否則轉(zhuǎn)步驟3;

圖1 C1t≤C2f的示意圖

圖 2 C1t＞C2f的示意圖

步驟2 工件集{J1s,J1,s+1,…,J1t,J2e,J2,e+1,…,J2f}在t1時(shí)刻開(kāi)始在機(jī)器M2上按單臺(tái)機(jī)最優(yōu)算法Moore-Hodgson算法排序,誤工工件按任意順序在J1n1或J2n2后加工;

步驟3 工件集{J1s,J1,s+1,…,J1t,J2,e+1,…,J2f}在C2e時(shí)刻開(kāi)始在機(jī)器M2上按單臺(tái)機(jī)最優(yōu)算法Moore-Hodgson算法排序,誤工工件按任意順序在J1n1或J2n2后加工。

2.2 問(wèn)題2 P2|D,T≠0|的算法

引理 若π*中在 r時(shí)刻之前開(kāi)工的工件都是M2工件,則π*為P2|D,T≠0|的最優(yōu)排序。

定義2 稱π*中r時(shí)刻正在機(jī)器M 2上加工且尚未完工的工件為跨越工件,記跨越工件在r時(shí)刻之后加工的時(shí)間長(zhǎng)度為T1,記在時(shí)刻之前開(kāi)工的工件集為A1,在r時(shí)刻或之后開(kāi)工的工件集為A2。

設(shè)r=t1+T,由于考慮運(yùn)輸時(shí)間,原來(lái)M1上r時(shí)刻前開(kāi)工的工件沒(méi)轉(zhuǎn)移就已誤工,稱為啞工件,如圖3所示。對(duì)于圖2,M2工件轉(zhuǎn)移到M1加工至少有一個(gè)工件誤工,而考慮M2工件轉(zhuǎn)移到M1加工,至多可以減少J1t這個(gè)工件的誤工可能性,所以,圖2不需要考慮M2工件轉(zhuǎn)移到M1加工的情況。

設(shè)π*中在r時(shí)刻前開(kāi)工的M1工件為{J1j1,…,J1jk},令。算法2考慮r時(shí)刻之前加工的M 1工件與r時(shí)刻之后加工的M2工件交換,使增加的誤工工件數(shù)盡量少,如圖4所示。

圖3 T＞0時(shí)工作示意圖

圖4 π*排序與近似排序的比較

算法2 (P2|D,T≠0|∑U′ij的近似算法):

步驟1 計(jì)算問(wèn)題1去掉啞工件后的最優(yōu)算法排序,將工件集{J1u,…,J1t,J2e,…,J2f}執(zhí)行算法1步驟2,將工件集{J1u,…,J1t,J2,e+1,…,J2f}執(zhí)行算法1步驟3,選擇值小的作為最優(yōu)序π*;

步驟2 若π*在 r時(shí)刻之前不含M 1工件,則π*即為問(wèn)題2的最優(yōu)序,算法終止,否則轉(zhuǎn)下一步;

步驟3 機(jī)器M2上依次選取π*中開(kāi)工時(shí)間大于或等于r的y個(gè)M2工件{J2b1,…,J2by},使得≥P-T1,而P2bv＜P-T1(當(dāng)π*中不存在跨越工件時(shí),令T1=0),令Q=

步驟4 若Q=P-T1,那么在M 2上先安排A1|{J1j1,…,J1 jk},然后安排{J2b1,…,J2by},接著在r時(shí)刻按照M1上的先后序加工π*中轉(zhuǎn)移到機(jī)器M2上的在J2by之前加工的M1工件,再按π*中的先后序加工剩余的其他工件,最后以任意順序在J1n1或J2n2之后加工啞工件;若Q＞P-T1,那么在M2上先安排A1|{J1j1,…,J1jk},然后安排{J2b1,…,J2by-1},接著在r時(shí)刻按照M1上的先后序加工π*中轉(zhuǎn)移到M2上的在J2by之前加工的M1工件。若J2by不誤工,則加工J2by。否則放在所有工件后加工,再按π*中的先后序加工剩余的其他工件,最后以任意順序在J1n1或J2n2之后加工啞工件。

3 算法性能分析

定理1 設(shè)A(I)是算法2關(guān)于問(wèn)題2的任意實(shí)例的目標(biāo)值,OPT(I)是最優(yōu)算法關(guān)于實(shí)例I的目標(biāo)值,則|A(I)-OPT(I)|≤1。

證明 分3種情形證明:

情形1 π*不含跨越工件。若Q=P,誤工工件個(gè)數(shù)不改變。若Q＞P,{J2b1,…,J2by-1}提前完工,交換后{J1j1,…,J1jk}不誤工,產(chǎn)生Q-P個(gè)單位的空閑。若 P2by≤Q-P,則 J2by不誤工,誤工工件個(gè)數(shù)不改變。否則J2by誤工,新增一個(gè)誤工工件;

情形2 π*有一個(gè)跨越工件為M1工件。若Q=P-T1,{J2b1,…,J2by}提前完工,交換后加工{J1j1,…,J1 jk}時(shí)間為T1+Q=P,誤工工件個(gè)數(shù)不改變。若Q＞P-T1,{J2b1,…,J2by-1}提前完工,交換后加工{J1 j1,…,J1jk}時(shí)間為T1+Q＞P,不誤工,此時(shí)產(chǎn)生T1+Q-P個(gè)單位空閑。若P2by≤T1+Q-P,J2by不誤工,誤工工件個(gè)數(shù)不改變。否則J2by誤工,新增一個(gè)誤工工件;

情形3 π*有一個(gè)跨越工件為M2工件。若Q=P-T1,{J2b1,…,J2by},提前完工,機(jī)器在時(shí)刻r前有P-Q=T1個(gè)單位空閑,將跨越工件提前加工,不誤工。交換后加工{J1j1,…,J1jk}時(shí)間為T1+Q=P,誤工工件個(gè)數(shù)沒(méi)有改變。若Q＞P-T1,{J2b1,…,J2by-1}提前完工,機(jī)器在r時(shí)刻前有P-(Q-p2by)=P-P2bv＞T1個(gè)單位空閑,將跨越工件提前加工,沒(méi)有誤工。交換后加工{J1j1,…,J1 jk}時(shí)間為T1+Q＞P,此時(shí)產(chǎn)生T1+Q-P個(gè)單位空閑。若P2by≤T1+Q-P,J2by不誤工,誤工工件個(gè)數(shù)不改變。否則J2by誤工,新增一個(gè)誤工工件。

[1] Lee Chung-Yee,Joseph Y-T Leung,Yu Gang.Two machine scheduling under disruptions with transportation considerations[J].Journal of Scheduling,2006,(9):35-48.

[2] Qix,Band JF,YuG.Disruption management for machine scheduling,the case of SPT schedu les,internet[J].Production Economics,2006,103(1):166-184.

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

[4] Moore JM.Onemachine sequencing algorithm for minimizing the number of late jobs[J].Management Science,1968,(15):102-109.

[5] 孫葉平,唐萬(wàn)梅,唐國(guó)春.Moore-Hodgson算法最優(yōu)性的證明[J].重慶師范大學(xué)學(xué)報(bào),2007,24(3):4-7.