帶兩個服務(wù)等級的3臺機半在線算法*

肖 滿，丁 璐，張 怡

(云南大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院,云南 昆明 650000)

1 引言

在服務(wù)行業(yè)中，為了獲得更多利益，服務(wù)商通常根據(jù)客戶的消費水平將客戶分為不同的服務(wù)等級，例如普通客戶和VIP客戶。VIP客戶往往比普通客戶享受更多的服務(wù)，即普通客戶能享受的服務(wù)，VIP客戶都能享受，而某些特殊服務(wù)只有VIP客戶才能享受，因此需要制定一些策略使得服務(wù)效率更高。例如在酒店行業(yè)，酒店需要提供免費接機服務(wù)，一般情況下普通客戶只能享受包車服務(wù)，而VIP客戶可以享受專車服務(wù)，也可以與普通客戶一起享受包車服務(wù)。若將服務(wù)的車輛看作機器，客戶的需求看作需要加工的工件，預(yù)先給每臺機器和每個工件安排一個服務(wù)等級標(biāo)號，這就是一類帶服務(wù)等級的排序問題。

帶服務(wù)等級約束的排序問題最早由Bar-Noy等人[1]提出，并針對任意等級和m臺同型機，他們首次給出了一個競爭比為e+1≈3.718的在線算法，當(dāng)所有工件加工時間相等時，由該算法可得到競爭比為e≈2.718。Hwang等人[2]則研究了任意等級和m臺同型機的離線情形，給出了一個近似算法，在m=2和m≥3時，分別得到競爭比為5/4和2-1/(m-1)。周萍等人[3]則研究了在3臺同型機上帶服務(wù)等級(最多有3個等級)的離線情形。

對于機器帶有約束(Eligibility Constraints)的在線情形,在有2臺同型機和3臺同型機時，Lim等人[11]分別證明了由AW算法可得最優(yōu)競爭比2和5/2。在有m臺同型機時，相關(guān)研究成果可見文獻(xiàn)[11]。在有2臺同型機時，Lee等人[12]給出了一個最優(yōu)在線算法HSF。Hou等人[13]研究了m臺同型機的情形。

現(xiàn)有文獻(xiàn)對2臺機上帶2個服務(wù)等級的情形研究已很充分,對3臺機上帶2個服務(wù)等級的半在線情形研究很少，而2臺機上的半在線算法不能直接運用到3臺機上,且3臺機上不同半在線情形的算法并不通用，相反根據(jù)獲知的工件信息不同，設(shè)計的算法差異會很大。因此，本文研究了一些帶有2個服務(wù)等級約束，在3臺同型機上的半在線排序問題，充分利用獲知的部分工件信息，設(shè)計了有較好競爭比的在線算法。

2 問題描述

設(shè)有3臺機器M1,M2,M3，一個工件序列S={J1,J2,…,Jn}，機器和工件都有一個等級標(biāo)號，工件一個接一個到達(dá)，只有安排好工件Jj，才能得知下一個工件Jj+1的信息(加工時間和等級)。工件Jj的加工時間記為pj，等級記為gj，一般將工件Jj記為(pj,gj)。 則對于任意工件Jj=(pj,gj),j=1,2,…,n，都有g(shù)j∈{1,2}。機器Mi的等級記為g(Mi),i=1,2,3，其中g(shù)(M1)=1,g(M2)=g(M3)=2。只有當(dāng)gj≥g(Mi)時，工件Jj才能被分配給機器Mi加工，所有工件都必須被加工，且加工過程不可中斷，工件Jj(j=1,2,…,n)被分配給機器Mi(i∈{1,2,3})后，不能取回再重新分配給其它機器。目標(biāo)為極小化最大機器完工時間(makespan)。為方便敘述，使用三參數(shù)法將這個問題記為P(1,2,2)‖Cmax。

引理1工件Jj被分配后，最優(yōu)解的目標(biāo)值至少為LBj,j=1,2,…,n。

由引理1可得:

COPT≥max{T1,pmax,(T1+T2)/3}

(1)

3 P(1,2,2)|T1|Cmax

已知等級為1的工件加工時間之和為T1，本節(jié)給出了一個下界為3/2和一個競爭比為5/3的在線算法。

定理1對于P(1,2,2)|T1|Cmax，任意在線算法A的競爭比至少為3/2。

□

算法描述如算法1所示。

算法1H1算法

輸入：工件序列S。

輸出：工件序列S的一個分配方案。

步驟3若gj=2,Jj按以下情況進(jìn)行分配：

步驟4若還有新的工件到達(dá)，j=j+1,返回步驟2。

定理2對于P(1,2,2)|T1|Cmax,H1算法的競爭比至多為5/3。

證明由式(1)知COPT≥max{T1,pmax,(T1+T2)/3}，下面對max{T1,pmax,T2-pmax}分3種情形進(jìn)行討論：

情形1max{T1,pmax,T2-pmax}=T1，則T1≥T2/2，且COPT=T1。由H1算法可知，所有等級為2 的工件將以貪婪原則全部分配給機器M2和M3，則任意時刻，M2與M3的負(fù)載之差不會超過pmax。因此,CH1≤max{(T2-pmax)/2+pmax,T1}。

若max{(T2-pmax)/2+pmax,T1}=T1，則CH1=T1，此時H1算法的分配達(dá)到最優(yōu)。否則，

CH1≤(T2-pmax)/2+pmax≤T1/2+T1，

因此，(CH1)/COPT≤3/2。

情形2max{T1,pmax,T2-pmax}=pmax，則COPT=pmax。

情形2.1T1≥T2-pmax。由H1算法可知，在這種情形下，任意時刻，M2和M3中總有一臺機器的負(fù)載不會超過T1，因此所有等級為2 的工件將以貪婪原則分配給M2和M3。則CH1=max{L2,L3}≤(T2-pmax)/2+pmax，因此,CH1/COPT≤((T2-pmax)/2+pmax)/pmax≤3/2。

情形2.2T1

CH1≤max{L1,L2,L3}≤max{(T1+

T2-pmax)/3+pmax,(T2-pmax)/2+pmax}

又

(T1+T2-pmax)/3+pmax≤

2pmax/3+pmax=5pmax/3

且

(T2-pmax)/2+pmax≤3pmax/2

所以證得CH1/COPT≤(5pmax/3)/pmax=5/3。

情形3max{T1,pmax,T2-pmax}=T2-pmax。

pt≤(T1+T2-pmax)/3+pmax

若M1被分配了等級為2的工件，則由H1算法可知，在M1被分配等級為2的工件后，任意2臺機器的負(fù)載之差不會超過Pmax。因此，CH1≤(T1+T2-pmax)/3+pmax，證得:

CH1/COPT≤((T1+T2-pmax)/3+pmax)/COPT=

((T1+T2)/3+2pmax/3)/COPT≤((T1+T2)/3)/

((T1+T2)/3)+(2pmax/3)/pmax=5/3

證畢。

□

4 P(1,2,2)|T2|Cmax

已知等級為2的工件加工時間之和為T2，本節(jié)給出了一個下界為3/2和一個競爭比為9/5的在線算法.

定理3對于P(1,2,2)|T2|Cmax，任意在線算法A的競爭比至少為3/2。

證明令T2=6，首先出現(xiàn)J1=(1,2),J2=(1,2),J3=(1,2),J4=(1,2)。

情形1M1沒有被分配工件。若M2或M3至少被分配了3個工件，則出現(xiàn)最后1個工件J5=(2,2)，在J5被分配后，可得CA≥3,COPT=2。 若M2和M3分別被分配了2個工件，則出現(xiàn)工件J5=(2,2)，若J5分配給M2或M3，則不再有新的工件到達(dá)，此時，CA=4,COPT=2。 若J5分配給M1，則出現(xiàn)最后1個工件J6=(3,1)，在J6被分配后，可得CA=5,COPT=3。

情形2M1被分配了1個工件。無論其余3個工件如何分配給M2和M3，出現(xiàn)最后1個工件J5=(2,2)，在J5被分配后，可得CA≥3，此時COPT=2。

情形3M1被分配了2個工件。最后出現(xiàn)J5=(2,2),J6=(3,1)共2個工件，在這2個工件被分配后，則有CA≥5 ，COPT=3。

情形4M1至少被分配了3個工件。則出現(xiàn)最后1個工件J5=(2,2)，在J5被分配后可得CA≥3,COPT=2。

因此，證得CA/COPT≥3/2。

□

算法描述如算法2所示。

算法2H2算法

輸入：工件序列S。

輸出：工件序列S的一個分配方案。

步驟3若gj=2,Jj按以下情況進(jìn)行分配：

步驟4若還有新的工件到達(dá)，j=j+1,返回步驟2。

定理4對于P(1,2,2)|T2|Cmax,H2算法的競爭比至多為9/5。

證明由H2算法可知，L2≤3T2/5,L1≤2T2/5+T1，令Jt=(pt,2)是分配給M3的最小工件。

情形1等級為2的工件都小于T2/3。假設(shè)L3>3T2/5，則L1(2)+L2<2T2/5，因為Jt分配給M3，則由H2算法可知，L2+pt>3T2/5,L1(2)+pt>2T2/5。若L1(2)=0，則pt>2T2/5>T2/3，與等級為2 的工件都小于T2/3矛盾。若L1(2)>0，則必有等級為2的工件分配給M1，由H2算法可知，分配給M1的任意1個等級為2的工件Js=(ps,2)，有L2+ps>3T2/5。因此，L2+L1(2)>3T2/5，與L2+L1(2)<2T2/5矛盾，所以L3≤3T2/5。又由式(1)知，COPT≥max{T1,pmax,(T1+T2)/3}，若CH2=L1，則:

CH2/COPT≤(2(T1+T2)/5+3T1/5)/COPT≤

(2(T1+T2)/5)/((T1+T2)/3)+

(3T1/5)/T1=9/5

若CH2=max{L2,L3}，則:

CH2/COPT≤(3T2/5)/((T1+T2)/3)≤9/5

情形2等級為2的工件只有1個不小于T2/3。假設(shè)L3>3T2/5，則L1(2)+L2<2T2/5，由H2算法有L2+pt>3T2/5,L1(2)+pt>2T2/5。若L1(2)=0，則pt>2T2/5，因為等級為2 的工件只有1個不小于T2/3，所以pmax=pt。又Jt是分配給M3的最小工件，所以L3=pmax=pt。由H2算法可知，在這種情形，除工件Jt外，其它所有等級為2的工件全分配給了M2。因此，L1=T1，又L3>3T2/5>L2，且L3=pmax，所以CH2=max{L1,L3}=max{T1,pmax}。由式(1)知,COPT≥max{T1,pmax,(T1+T2)/3}，所以此時H2算法的分配達(dá)到最優(yōu)。若L1(2)>0，則必有等級為2 的工件分配給M1，由H2算法可知，L1(2)+L2>3T2/5，與L1(2)+L2<2T2/5矛盾，所以L3≤3T2/5。 由情形1可知，CH2/COPT≤9/5。

情形3等級為2的工件有2個不小于T2/3。假設(shè)L3>3T2/5，則L1(2)+L2<2T2/5，由H2算法可知，L2+pt>3T2/5,L1(2)+pt>2T2/5。若M3只被分配了工件Jt，則L3=pt，因為L3>3T2/5，則pt=pmax>3T2/5。因此，由H2算法可知，在這種情形，除工件Jt外，其它所有等級為2的工件全部分配給了M2。由情形2可知此時H2算法的分配達(dá)到最優(yōu)。若M3至少被分配了2 個工件，又Jt是分配給M3的最小的工件，則L3≥2pt，可得:

T2=L1(2)+L2+L3≥(L1(2)+pt)+

(L2+pt)>2T2/5+3T2/5=T2

是真假式，所以L3≤3T2/5。由情形1可得CH2/COPT≤9/5。

情形4等級為2的工件有3個不小于T2/3 (即等級為2的工件只有3個，且大小都為T2/3)。由H2算法可知，L1(2)=L2=L3=T2/3，因此，CH2=L1(2)+T1=T2/3+T1。若T1≤T2/3，此時H2算法的分配達(dá)到最優(yōu)。若T2/32T2/3，則COPT=T1,CH2/COPT≤(T2/3+T1)/T1≤3/2。

因此，證得CH2/COPT≤9/5。

□

5 P(1,2,2)|T1&T2|Cmax

已知等級為1的工件加工時間之和為T1，等級為2的工件加工時間之和為T2，本節(jié)給出了一個下界為4/3和一個競爭比為3/2的在線算法。

定理5P(1,2,2)|T1&T2|Cmax，任意在線算法A的競爭比至少為4/3。

證明令T1=1,T2=8，首先出現(xiàn)J1=(1,1),J2=(1,2),J3=(1,2)共3個工件。

情形1M1只被分配了J1,則最后出現(xiàn)J4=(3,2)和J5=(3,2)，此時可得CA≥4,COPT=3。

情形2M1被分配了J1，J2和J3中的1個，則最后出現(xiàn)J4=(3,2)和J5=(3,2)，此時可得CA≥4,COPT=3。

情形3M1被分配了J1,J2和J3，則最后出現(xiàn)J4=(2,2)和J5=(2,2),J6=(2,2)，此時可得CA≥4,COPT=3。

證畢。

□

本節(jié)算法由文獻(xiàn)[14]中CMF(Common Machine First)算法修改得到，具體步驟如算法3所示。

算法3H3算法

輸入：工件序列S。

輸出：工件序列S的一個分配方案。

步驟3等級為2的工件Jj按以下情況進(jìn)行分配：

步驟3.2若T2>T1，則按以下情形分配:

步驟4若還有新的工件到達(dá)，j=j+1，返回步驟2。

定理6對于P(1,2,2)|T1&T2|Cmax,H3算法的競爭比至多為3/2。

CH3/COPT≤max{(T1+T2)/2,pmax}/

max{T1,(T1+T2)/3,pmax}≤3/2

證畢。

□

6 P(1,2,2)|T|Cmax

已知等級為1的工件與等級為2的工件加工時間之和為T，本節(jié)給出了一個競爭比為3/2的最優(yōu)在線算法。

定理7對于P(1,2,2)|T|Cmax，任意在線算法A的競爭比至少為3/2。

證明令T=6，首先出現(xiàn)J1=(1,1),J2=(1,2),J3=(1,2)和J4=(1,2)。

情形1若M1未被分配J2,J3和J4，則出現(xiàn)最后1個工件J5=(2,2)，在J5被分配后，可得CA≥3,COPT=2。

情形2若M1被分配了J2,J3和J4中的1個，則最后出現(xiàn)J5=(1,1)和J6=(1,2)，在這2個工件被分配后，可得CA≥3,COPT=2。

情形3若M1至少被分配了J2,J3和J4中的2個，則出現(xiàn)最后一個工件J5=(2,2)，在J5被分配后，可得CA≥3,COPT=2。

證畢。

□

本節(jié)算法由文獻(xiàn)[14]中CMF算法修改得到，具體步驟如算法4所示。

算法4H4算法

輸入：工件序列S。

輸出：工件序列S的一個分配方案。

步驟3等級為2的工件Jj按以下情況進(jìn)行分配:

步驟4若還有新的工件到達(dá)，j=j+1，返回步驟2。

定理8對于P(1,2,2)|T|Cmax,H4算法的競爭比至多為3/2。

證明若T1≥T2，由H4算法可知，等級為2的工件將全部分配給M2，即L2=T2≤T/2,L3=0，此時CH4=T1達(dá)到最優(yōu)分配。若T1T/2。所以，L1≤T/2,CH4=max{L1,L2,L3}≤max{pmax,T/2}，又由式(1)知，COPT≥max{T1,pmax,(T1+T2)/3}，因此證得:

CH4/COPT≤max{pmax,T/2}/

max{T1,pmax,T/3}≤3/2

□

7 結(jié)束語

本文研究了在3臺同型機上，帶2個服務(wù)等級的排序問題，考慮了4種半在線情形：(1)已知低等級工件加工時間之和；(2)已知高等級工件加工時間之和；(3)分別已知2個等級的工件加工時間之和；(4)已知總的工件加工時間之和。其中只有第4種情形得到了最優(yōu)在線算法，在后續(xù)的研究中，可考慮前3種情形的最優(yōu)算法，以及3臺機上的其它半在線情形。