葉春花,沈 灝

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

0 引 言

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

1 問題介紹

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

2 算法及定理

2.1 問題1 P2|D=∞,T=0|的算法

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

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

圖1 C1t≤C2f的示意圖

圖 2 C1t＞C2f的示意圖

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

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

2.2 問題2 P2|D,T≠0|的算法

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

定義2 稱π*中r時刻正在機器M 2上加工且尚未完工的工件為跨越工件,記跨越工件在r時刻之后加工的時間長度為T1,記在時刻之前開工的工件集為A1,在r時刻或之后開工的工件集為A2。

設r=t1+T,由于考慮運輸時間,原來M1上r時刻前開工的工件沒轉移就已誤工,稱為啞工件,如圖3所示。對于圖2,M2工件轉移到M1加工至少有一個工件誤工,而考慮M2工件轉移到M1加工,至多可以減少J1t這個工件的誤工可能性,所以,圖2不需要考慮M2工件轉移到M1加工的情況。

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

圖3 T＞0時工作示意圖

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

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

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

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

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

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

3 算法性能分析

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

證明 分3種情形證明:

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

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

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

[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] 葉賽英,沈灝,魏小蘭.機器帶故障的兩臺機排序問題的一個近似算法[J].杭州電子科技大學學報,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] 孫葉平,唐萬梅,唐國春.Moore-Hodgson算法最優(yōu)性的證明[J].重慶師范大學學報,2007,24(3):4-7.