姚青華，邱本花

(鄭州科技學(xué)院基礎(chǔ)部，河南鄭州 450064)

鏈組約束下部分批處理平行機(jī)在線排序

姚青華，邱本花

(鄭州科技學(xué)院基礎(chǔ)部，河南鄭州 450064)

研究了一臺是批處理機(jī)而另一臺是正常機(jī)器、工件具有鏈組約束、最小化時(shí)間表長的兩臺恒同機(jī)在線排序問題.給出該問題競爭比為+1)/2的最好可能的在線算法.

在線排序;平行分批;鏈約束;競爭比;下界

0 引言

設(shè)有兩臺恒同機(jī)器，機(jī)器分別記為M1，M2，其中M1是批處理機(jī)且容量無界，M2是正常機(jī)器且任意時(shí)刻只能加工一個(gè)工件.工件信息在排序之初未知，只有在其到達(dá)之后工件信息才釋放，每個(gè)到達(dá)時(shí)間到來的一組工件之間存在鏈組約束關(guān)系，所有工件的長度都相同(即為p)，目標(biāo)是最小化時(shí)間表長.用Cj表示工件Jj的完工時(shí)間.根據(jù)文獻(xiàn)［1］，該模型用三參數(shù)法表示為

鏈約束可以借助于有向圖來描述:設(shè)每個(gè)工件對應(yīng)有向圖的一個(gè)頂點(diǎn)，若每個(gè)頂點(diǎn)都至多有一個(gè)直接前任和一個(gè)直接后繼，則此工件之間的序約束稱為鏈組約束.對于一組鏈組約束下的工件，若該工件有直接后繼，則它的層次為直接后繼工件的層次加1;若該工件沒有直接后繼，則該工件的層次為1.記工件Jk所在的鏈為chainJk，此鏈的到達(dá)時(shí)間為rk.用|chainJk|來表示鏈chainJk中所含工件的個(gè)數(shù).

對于兩臺恒同機(jī)或者都是批處理機(jī)或者都是正常機(jī)器排序問題，文獻(xiàn)［2］和文獻(xiàn)［3］已經(jīng)給出了相當(dāng)豐富的研究成果，而同時(shí)考慮一臺機(jī)器是批處理機(jī)，另一臺是正常機(jī)器的研究很少看到.本文討論該問題的下界為1+α的情形，并給出了一個(gè)最好可能的在線算法，其中，α =－1/2.

1 問題的下界

定理1該問題不存在競爭比小于1+α的在線算法.

證明 首先，ε是一個(gè)充分小的正數(shù).假設(shè)在r=0時(shí)刻到達(dá)兩個(gè)只含一個(gè)工件的鏈，分別為chainJ1，chainJ2.J1，J2的開工時(shí)刻分別為s1，s2.

情形1 如果s1，s2至少有一個(gè)si≥αp(i=1，2)，那么不再來工件.于是，Cmax(σ)≥si+p，Cmax(π)=p.因此，Cmax(σ)/ Cmax(π)≥(si+p)/p≥1+α.

情形2 如果s1，s2都有si＜αp(i=1，2)，那么考慮下面兩種情況:

情形2.1 若J1，J2分別安排在M1，M2上開工，且si≤sj(i，j∈{1，2})，但i≠j，那么在si+ε時(shí)刻又來n(n≥2)條只含一個(gè)工件的鏈.于是，Cmax(σ)≥si+2p，Cmax(π)≤si+p+ε.因此，Cmax(σ)/Cmax(π)≥(si+2p)/(si+p+ε)→(si+2p)/(si+p)= 1+p/(si+p)＞1+α.

情形2.2 若J1，J2作為一批安排在M1上開工，則s1=s2=s，那么在s+ε時(shí)刻又來n(n≥2)條只含一個(gè)工件的鏈.則Cmax(σ)≥s+2p，Cmax(π)≤s+p+ε.故Cmax(σ)/Cmax(π)≥(s+2p)/(s+p+ε)→(s+2p)/(s+p)＞1+α.

2 問題的一個(gè)最好可能的在線算法

2.1 約定及算法描述

約定1對于該問題任意一個(gè)實(shí)例第一個(gè)到達(dá)時(shí)間都滿足r1=0.

約定2在同一時(shí)刻不會(huì)到達(dá)兩個(gè)或多個(gè)完全一樣的鏈.

把已經(jīng)到達(dá)且所有前任都已完工的工件稱為可排工件.

算法H

t←當(dāng)前時(shí)刻，k←移動(dòng)指針，U(t)←當(dāng)前可排工件的集合.

第1步 令k=0.在t=0時(shí)刻，將U(0)中可排工件中層次最高者安排在M2上開工.

第2步 安排工件到機(jī)器M1，執(zhí)行:如果t=(α+k)p，那么將U(t)中可排工件作為一批安排在機(jī)器M1上(這里允許某一批為空).否則，M1等待.轉(zhuǎn)第3步.置k=k+1.

第3步 安排工件到機(jī)器M2，執(zhí)行:

第3.1步 當(dāng)p≤t＜(1+α)p時(shí)，若U(t)中存在層次大于等于2的可排工件，則將層次最高者安排在M2上開工.否則，M2等待.返回第2步.

第3.2步 當(dāng)t≥(1+α)p時(shí)，若只有機(jī)器M2可用，則將U(t)中層次最高者安排在M2上開工(如果該工件不唯一，選擇到達(dá)時(shí)間最大);若兩臺機(jī)器都可用，優(yōu)先安排在M1上開工，開工時(shí)刻為t=(1+α)p，將U(t)中所有可排工件作為一批在t時(shí)刻加工.返回第2步.

第4步 當(dāng)所有工件已完工時(shí)，結(jié)束算法.

假設(shè)Bl為σ中M1上的最后一批完工工件，這里的Jl是Bl中所在鏈最長的工件(如果該工件不唯一，那么選擇rl最大的一個(gè))其中rl是鏈chainJl的到達(dá)時(shí)間.工件Jc是機(jī)器M2在σ下最后一個(gè)加工工件，其到達(dá)時(shí)間為rc，開工時(shí)刻為sc.現(xiàn)在假設(shè)Bl之前的一批為B*(如果有的話)，其開工時(shí)刻為S*.

由算法的第3.2步可知，不會(huì)出現(xiàn)CM1(σ)=CM2(σ)的情況.現(xiàn)在我們討論σ中兩臺機(jī)器的完工時(shí)間(σ)(σ)之間的關(guān)系，就CM1(σ)＞CM2(σ)和CM1(σ)＜CM2(σ)兩種情況分別證明，算法H的競爭比為1+α.

2.2CM1(σ)＞CM2(σ)的情形

定理2 若CM1(σ)＞CM2(σ)，則在線算法H的競爭比不超過1+α.

證明 如果批B*不存在，那么M1上只有一批Bl.根據(jù)算法H可知，Cmax(σ)/Cmax(π)≤1+α.下面我們假設(shè)B*存在.

情形1B*與Bl之間有空閑時(shí)間.由算法H及題設(shè)可設(shè)CB*=(i+α)p(i≥1).

情形1.1rl＜CB*.

斷言1 批B*內(nèi)不含鏈chainJl中任意一個(gè)工件.

斷言2 由算法H及題設(shè)條件可知，鏈|chainJl|≥2.

斷言3 在CB*時(shí)刻，機(jī)器M2正在加工鏈chainJl中的工件Jl|chainJl|－1.

斷言4 鏈chainJl的第一個(gè)工件Jl1一定安排在M2上開工，并且工件Jl1，Jl2，…，Jl|chainJl|－1在M2上連續(xù)加工.

斷言5 鏈chainJl的第一個(gè)工件Jl1的開工時(shí)刻滿足sl1＜rl+p.

由斷言5可知Cmax(σ)≤sl+|chainJl|p+p≤rl+(|chainJl|+2)p，Cmax(π)≥rl+|chainJl|p.

(1)rl=0.由題設(shè)可知|chainJl|≥3.由斷言4及題設(shè)可設(shè)B*的完工時(shí)間為(i+α)p.于是Cmax(σ)=(i+α)p+2p＜(|chainJl|+1)p，Cmax(π)≥rl+|chainJl|p=|chainJl|p.故

(2)αp＜rl＜(1+α)p.由斷言4、斷言2及題設(shè)可知，在rl時(shí)刻必須安排工件Jl1在M2上開工.Cmax(σ)/Cmax(π)≤1+α.

(3)rl＞(1+α)p.注意|chainJl|≥2，則有Cmax(σ)/Cmax(π)≤(rl+|chainJl|p+2p)/(rl+|chainJl|p)≤1+α.

情形1.2rl＞CB*.則鏈chainJl只含有一個(gè)工件.于是Cmax(σ)=(i+1+α+1)p，而Cmax(π)≥rl+p＞(i+α+1)p.故，Cmax(σ)/Cmax(π)≤(i+α+2)/(i+α+1)≤1+α.

情形2B*與Bl之間沒有空閑時(shí)間.

情形2.1 假設(shè)|chainJl|=1，則rl＞sB*≥αp.若B*為M1上第一批，則αp＜rl≤(1+α)p.于是，Cmax(σ)=(2+α)p，而Cmax(π)≥rl+p≥(1+α)p.故Cmax(σ)/Cmax(π)≤1+α;若B*為M1上第i批(1＜i＜m)，則rl＞(1+α)p.在rl時(shí)刻，若M1可用(或者M(jìn)1，M2同時(shí)可用)并且工件Jl被安排在M1上，則Cmax(σ)/Cmax(π)≤1+α.在rl時(shí)刻，若M1不可用，則M2也不可用.于是，(i+α)p＜rl≤(i+1+α)p(1≤i≤m－1)，則Cmax(σ)=(i+2+α)p，而Cmax(π)≥rl+p≥(i+1+α)p.故，Cmax(σ)/ Cmax(π)≤1+α.

情形2.2 假設(shè)|chainJl|=2.如果工件Jl1在M1上加工，顯然工件Jl也在M1上加工.由斷言5可知Cmax(σ)=sl+2p＜rl+3p，而Cmax(π)≥rl+2p，于是，Cmax(σ)/Cmax(π)≤1+α;如果工件Jl1在M2上加工，由題設(shè)條件可知工件Jl在M1上加工.若批B*的開工時(shí)刻sB*=αp，則rl=0.于是，Cmax(σ)≤(2+α)p.而Cmax(π)≥rl+2p=2p.故，Cmax(σ)/Cmax(π)≤1+α;若批B*的開工時(shí)刻sB*≥(1+α)p，設(shè)批B*的完工時(shí)間為(i+α)p(i≥2)，由算法H及題設(shè)條件可知rl＞(i－2+α)p，且Cmax(σ)≤(i+α)p+p，而Cmax(π)≥rl+2p≥(i+α－2)p+2p=(i+α)p.于是Cmax(σ)/Cmax(π)≤1+α.

情形2.3 假設(shè)|chainJl|≥3.如果0＜rl≤αp，根據(jù)算法 H可知將工件Jl1在t=αp時(shí)刻安排在M1上開工.于是，Cmax(σ)=(|chainJl|+α)p.而Cmax(π)≥rl+|chainJl|p＞|chainJl|p.所以Cmax(σ)/Cmax(π)≤1+α.如果rl＞αp，由斷言5可知Cmax(σ)≤sl+(|chainJl|+1)p≤rl+(|chainJl|+2)p.而Cmax(π)≥rl+|chainJlp|.故Cmax(σ)/Cmax(π)≤1+α.

2.3CM1(σ)＜CM2(σ)的情形

考察M2上最后一個(gè)關(guān)鍵工件Jc，假設(shè)Jc所在的鏈為chainJc，該鏈的到達(dá)時(shí)間和開工時(shí)間分別為rc，sc.并且設(shè)鏈chainJc的第i個(gè)工件為Jci(1≤i≤c).

觀察1 (1)鏈chainJc的第一個(gè)工件Jc1必定在M2上開工;(2)當(dāng)rc＞αp，且工件Jc1一旦在機(jī)器M2上開工時(shí)，則工件從sc開始一直連續(xù)加工到Cmax(σ).

觀察2 根據(jù)算法H可知，鏈chainJc的到達(dá)時(shí)間rc滿足rc=0或者rc＞αp且rc≠(α+k)p(k為非負(fù)整數(shù)).觀察3 當(dāng)rc=0時(shí)，鏈chainJc所含的工件個(gè)數(shù)|chainJc|≠2.

定理3 若CM1(σ)＜CM2(σ)，則在線算法H的競爭比不會(huì)超過1+α.

證明 情形1rc=0.由觀察3可知，僅需考慮|chainJc|≥3或|chainJc|=1.由算法H可得Cmax(σ)=Cmax(π).

情形2 αp＜rc＜(1+α)p.如果|chainJc|=2，根據(jù)算法H及觀察1可知，在rc時(shí)刻機(jī)器M1正在加工工件，于是，Cmax(σ)=sc1+2p＜(1+α)p+2p=(3+α)p.而Cmax(π)≥rc+2p＞(2+α)p.所以Cmax(σ)/Cmax(π)≤1+α.如果|chainJc|≥3.根據(jù)算法H及觀察1可知，在rc時(shí)刻機(jī)器M1正在加工工件.

于是Cmax(σ)=sc1+|chainJc|p＜(1+α)p+|chainJc|p=(|chainJc|+1+α)p.而Cmax(π)≥rc+|chainJl|p＞(|chainJc|+ α)p.所以Cmax(σ)/Cmax(π)≤1+α.

情形3rc＞(1+α)p.根據(jù)算法H及觀察1和觀察2可知，在rc時(shí)刻機(jī)器M1必定在加工某一批B.假設(shè)(i+α)p＜rc≤(i+ 1+α)p(1≤i≤n).由算法H及題設(shè)條件可知必定有CM1(rc)＞(rc)，于是Cmax(σ)=+|p≤(i+1+||+ α)p，而Cmax(π)≥rc+||p.所以Cmax(σ)/Cmax(π)≤1+α.

綜上，有以下結(jié)論.

定理4 對排序問題P2|on－line，p－batch，chains，pj=p，B1=∞，B2=1|Cmax所有實(shí)例，在線算法H的競爭比不會(huì)超過1+α.

［1］ GRAHAM R L，LAWLER E L，LENSTRA J K，et al.Optimization and approximation in deterministic sequencing and scheduling:a survey［J］.Annals of Discrete Mathematics，1979(5):287－326.

［2］ DU J，LEUNG J Y T，YOUNG G H.Scheduling chain-structured tasks to minimize makespan and mean flow time［J］.Inform and Comput，1991，92(2):219－236.

［3］ NONG Q Q，CHENG T C E，C T NG.An improved on-line algorithm for scheduling on two unrestrictive parallel batch processing machines［J］.Operat Res Lett，2008，36(5):584－588.

On-Line Scheduling on Partial Batch Parallel Machine with Chains Precedence Constraints

YAO Qing-hua，QIU Ben-hua

(Department of Basic Courses，Zhengzhou College of Science＆Technology，Zhengzhou450064，China)

Studied on-line scheduling of two identical parallel machines，one of which is processing machine and the other is normal.The jobs are chains-precedence constraints;the goal is to minimize the makespan.Provided a best possible on-line algorithm for the problem with competitive ration(+1)/2.

on-line scheduling;parallel batch;chains-precedence constraint;competitive ration;lower bound

O224

A

1007－0834(2011)02－0037－03

10.3969/j.issn.1007－0834.2011.02.013

2011－02－23

河南省基礎(chǔ)與前沿技術(shù)研究計(jì)劃資助項(xiàng)目(082300410070)

姚青華(1982—)，男，河南駐馬店人，鄭州科技學(xué)院基礎(chǔ)部教師.