平行機(jī)鏈約束下單位長度工件的在線排序問題

平行機(jī)鏈約束下單位長度工件的在線排序問題

有序約束的順序問題是經(jīng)典的順序模型，只有在所有現(xiàn)有零件加工好后才能開始加工，鏈?zhǔn)Y(jié)構(gòu)是一種特殊的序列限制。除了頭和尾零件，還有后入件和后入件。在線順序的特點(diǎn)是對零件信息的逐步釋放。由于手中的信息不足，決策者只能根據(jù)當(dāng)前的信息進(jìn)行分類和決策。由于能夠掌握的信息不足，許多在線問題無法設(shè)計(jì)最佳的多項(xiàng)式時(shí)間算法。在線附近算法的優(yōu)勢和劣勢可以用競爭比來評估。假設(shè)i是其前任，表達(dá)式參數(shù)（）是在線算法的目標(biāo)值，并且elax（）是最佳目標(biāo)值，則在線算法的競爭比設(shè)置為最佳目標(biāo)值。兩臺平行機(jī)上鏈約束下單位長度工件完工時(shí)間平方和最小的在線排序問題可以描述為:給定兩臺速度完全一樣的平行機(jī),每個(gè)到達(dá)時(shí)刻到達(dá)的是具有鏈組約束的工件,工件的加工時(shí)間都是1,工件的其它信息是在線的,只有到到達(dá)之后,其約束關(guān)系等信息才全部釋放,只有工件的全部前任工件加工完才稱為可用工件,目標(biāo)函數(shù)是最小化最大完工時(shí)間的平方和.文中常用的記號有:Jj:第j個(gè)工件;chainsi:第i個(gè)條鏈;│chainsi│:第i個(gè)條鏈的工件數(shù);rj,sj,pj,C(Jj):分別表示工件的到達(dá)時(shí)間、開工時(shí)間、加工時(shí)間和工件Jj的完工時(shí)間;Mi(i=1,2):第1,2臺機(jī)器;CMi(i=1,2):第1,2臺機(jī)器的完工時(shí)間;emax:兩臺機(jī)器的最大完工時(shí)間平方和,即emax=C2M1+C2M2;emax(σ):在線算法排序σ下的完工時(shí)間平方和;emax(π):離線最優(yōu)排序π下的完工時(shí)間平方和.文獻(xiàn)只研究了一些工件帶有序約束關(guān)系的最大完工時(shí)間、最大工件延誤時(shí)間等問題,對于目標(biāo)函數(shù)是機(jī)器完工時(shí)間平方和的排序問題的研究目前還比較少.本文考慮了兩臺平行機(jī)上鏈約束下單位長度工件完工時(shí)間平方和最小的在線排序問題.用三參數(shù)法表示為.利用對手法證明任一實(shí)例在任意算法下競爭比不小于5/4,而任意稠密算法的競爭比都漸近地趨于2;其次找到一種稠密算法—層次算法,其競爭比為2,從而說明此層次算法為本問題的一個(gè)最好可能在線稠密算法.1工件安排開工定理1對于問題,不存在在線算法,使得它對于該問題的所有實(shí)例的競爭比都小于5/44證明我們下面利用對手法(AdversaryArgument)給出一組實(shí)例,并證明任何一個(gè)在線算法都無法使它的競爭比小于5/44考慮下面的鏈:chains1在r1=0時(shí)刻到達(dá),它包含一條只含一個(gè)工件的鏈;r2=1時(shí)刻到達(dá)兩條含一個(gè)工件的鏈chains2,chains3.情形1若在線算法在0時(shí)刻沒有將0時(shí)刻到來的工件安排開工,則chains2,chains3不來.此時(shí)工件J1的開工時(shí)刻s1≥1,emax(σ)≥(s1+1)2≥4,emax(π)=1.從而有情形2若在線算法在0時(shí)刻將0時(shí)刻到來的工件安排開工,不妨假設(shè)工件J1在機(jī)器M1加工,s1=0,則chains2,chains3到達(dá).根據(jù)工件J2和J3是否在同一臺機(jī)器上加工又分為下面幾種情況.子情形2-1工件J2和J3在同一臺機(jī)器上加工.此時(shí)又分為以下兩種子情形.子情形2-1-1工件J2,J3與J1不在同一臺機(jī)器上加工.則后面不來工件.此時(shí)(如圖1),我們有emax(σ)≥1+32=10,emax(π)=22+22=8.從而子情形2-1-2工件J2,J3與J1在同一臺機(jī)器上加工.則chains4到達(dá)(如圖2).此時(shí),不管工件J4,J5與J1是否在同一臺機(jī)器M1,都有emax(σ)≥25,emax(π)=20.從而有(如圖3)emax(π)emax(σ)≥2025=45.子情形2-2工件J2和J3不在同一臺機(jī)器上加工.則第四組鏈chains4到達(dá)(如圖4).此時(shí),不管工件J4在機(jī)器M1還是在機(jī)器M2上加工,都有emax(σ)≥20,emax(π)=16.從而有(如圖5)由上述情況可知,任何在線算法都無法使這組實(shí)例的競爭比全部小于5/442yarguc算法仿真兩臺平行機(jī)的稠密算法指:兩臺機(jī)器一旦同時(shí)空閑,且當(dāng)前可加工工件集非空,就指派當(dāng)前可加工工件到其中任一臺空閑機(jī)器上加工.下面我們構(gòu)造一組實(shí)例來說明任意的稠密算法下此問題的競爭比都漸近地趨于2.定理2對于問題,任何在線的稠密算法的競爭比在漸近的意義下都不會比2小.證明我們下面利用對手法(AdversaryArgument)給出一組實(shí)例,并證明任何在線的稠密算法的競爭比在漸近的意義下都不會比2小.考慮下面的實(shí)例:J1,J2在r0=M時(shí)刻到達(dá);J3,J4在r1=M+1時(shí)刻到達(dá);…;J2i+1,J2i+2在ri=M+i時(shí)刻到達(dá);…;J2n+1,J2n+2在rn=M+n時(shí)刻到達(dá).所有工件的加工時(shí)間pj=1,j=1,2,…,2n+2.根據(jù)稠密算法,不妨設(shè)工件J1放在機(jī)器M1上加工.若工件J2在機(jī)器M2上加工,后面不來工件.此時(shí)若工件J2也在機(jī)器M1上加工,則工件J3,J4在r1=M+1到達(dá).若工件J3,J4有一個(gè)或兩個(gè)都放在機(jī)器M2上加工,則或者依次下去,若有某一個(gè)工件J2i+1或J2i+2放在機(jī)器M2上加工,則后面不來工件.此時(shí)可取M充分大,則若一直沒有工件放在機(jī)器M2上加工,后面按照上述方式一直來工件.當(dāng)工件的個(gè)數(shù)2n充分大的時(shí)候,我們有.由上述情況可知,任何在線的兩臺平行機(jī)的稠密算法的競爭比在漸近意義下不小于2.定理得證.推論1對于問題,任何在線的稠密算法的競爭比在漸近意義下不會比2小.3在線層次算法要證明一個(gè)最小化問題的在線算法是最好可能的在線算法,只需證明其競爭比不大于問題的下界.對于問題,我們只需證明在線算法的競爭比不大于2即可.若問題的某個(gè)實(shí)例I的第一個(gè)到達(dá)時(shí)間r1嚴(yán)格大于0,則對這個(gè)實(shí)例有.如果我們把I的所有到達(dá)時(shí)間都減小r1(第一個(gè)到達(dá)時(shí)間變?yōu)?)得到一個(gè)新實(shí)例I′.若一個(gè)在線算法對I′的競爭比不大于2,則對I的競爭比也不大于2.故我們在接下來總是作以下約定.約定問題的每一個(gè)實(shí)例的第一個(gè)到達(dá)時(shí)間都滿足r1=0.接下來我們來研究該問題的最優(yōu)在線算法.在給出我們的在線算法之前,首先給出工件level的定義.定義對于一組鏈組約束下的工件,若一個(gè)工件沒有直接后繼,則它的層次為1;若一個(gè)工件有直接后繼,則它的層次為其直接后繼的層次加1.記工件Jj的層次為level(Jj).由層次的定義我們知道,一個(gè)鏈的第一個(gè)工件的層次等于它所在的鏈所含的工件個(gè)數(shù).在接下來的討論中,稱一個(gè)工件在某一時(shí)刻t可排,是指它滿足以下三個(gè)條件:(1)此工件所在的鏈在t時(shí)刻已經(jīng)到達(dá);(2)此工件的所有前任在t時(shí)刻已經(jīng)完工;(3)此工件在t時(shí)刻之前未被安排開工.而機(jī)器在t時(shí)刻可用是指在這個(gè)時(shí)刻機(jī)器沒有加工工件.下面我們給出我們的在線層次算法(On-LineLevelAlgorithm)H.在線層次算法H:t為當(dāng)前時(shí)刻;U(t)為當(dāng)前時(shí)刻t的可排工件集合.1)0時(shí)刻,若可排工件集U(0)中可排工件至少有兩個(gè),將層次最高的兩個(gè)工件(若層次最高的工件不止兩個(gè),則任選兩個(gè))分別安排在M1,M2上開工;若可排工件集U(0)中只有一個(gè)工件,安排其在M1上加工;2)當(dāng)t≥1時(shí),每當(dāng)有機(jī)器可用時(shí),將層次最高的可排工件中的一個(gè)安排在空閑機(jī)器上加工.若兩臺機(jī)器同時(shí)可用,優(yōu)先安排在M1上開工;3)當(dāng)所有工件都已完工時(shí),結(jié)束算法.在此問題中,我們要求工件在整數(shù)時(shí)刻到達(dá),在整數(shù)時(shí)刻開工,當(dāng)然工件會在整數(shù)時(shí)刻完工.通過分析算法我們知道,在算法產(chǎn)生的排序Son中滿足:無工件可排而產(chǎn)生的機(jī)器空閑:在某個(gè)時(shí)刻t一臺機(jī)器可用,但此時(shí)U(t)中的工件全是另一臺機(jī)器上正加工工件的后繼,這樣只有當(dāng)有新工件到來后才可能有工件可在這臺機(jī)器上安排.這樣的空閑只會出現(xiàn)在某個(gè)到達(dá)時(shí)間ri之前,具有[ri-li,ri)的形式,其中l(wèi)i為空閑的長度一旦有工件可排且機(jī)器可用,則向空閑機(jī)器安排加工當(dāng)前最高層次工件,若兩臺機(jī)器同時(shí)空閑,優(yōu)先在機(jī)器M1上加工.定理3對于問題,層次算法H的競爭比不超過2.證明假設(shè)在層次算法H下機(jī)器的最大完工時(shí)間CHmax的決定工件為Jn,其所在的鏈為chainJn∈,這條鏈的到達(dá)時(shí)間為rn,用│chainJn∈│表示這條鏈的工件個(gè)數(shù),當(dāng)然等于鏈上工件的總的加工時(shí)間和,把機(jī)器的最小完工時(shí)間表示為CHmin,在離線最優(yōu)排序下機(jī)器的最大完工時(shí)間和最小完工時(shí)間分別為Cmaxopt,Cminopt,那么由算法知,當(dāng)機(jī)器M1空閑時(shí),機(jī)器M2在此段上也必然空閑.假設(shè)工件Jn前最后一個(gè)空閑時(shí)間段之后的連續(xù)的塊(Block)的第一個(gè)工件為Jl.將該連續(xù)塊(Block)記作B(l).若沒有這樣的空閑時(shí)間段,則工件Jl為所在的鏈chainJl∈的層次最高的工件,即起點(diǎn)工件,其到達(dá)時(shí)間為rl.那么,由算法可知,工件Jl的開工時(shí)間sl=rl,所以CHmax=rl+│B(l)│,其中│B(l)│表示塊B(l)中工件個(gè)數(shù),當(dāng)然也為其中工件的總加工時(shí)間和.塊B(l)中的相鄰的工件