帶兩個(gè)服務(wù)等級(jí)的3臺(tái)機(jī)半在線算法*

肖 滿，丁 璐，張 怡

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

1 引言

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

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

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

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

2 問(wèn)題描述

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

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

由引理1可得:

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

(1)

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

已知等級(jí)為1的工件加工時(shí)間之和為T(mén)1，本節(jié)給出了一個(gè)下界為3/2和一個(gè)競(jìng)爭(zhēng)比為5/3的在線算法。

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

□

算法描述如算法1所示。

算法1H1算法

輸入：工件序列S。

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

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

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

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

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

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

若max{(T2-pmax)/2+pmax,T1}=T1，則CH1=T1，此時(shí)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算法可知，在這種情形下，任意時(shí)刻，M2和M3中總有一臺(tái)機(jī)器的負(fù)載不會(huì)超過(guò)T1，因此所有等級(jí)為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被分配了等級(jí)為2的工件，則由H1算法可知，在M1被分配等級(jí)為2的工件后，任意2臺(tái)機(jī)器的負(fù)載之差不會(huì)超過(guò)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

已知等級(jí)為2的工件加工時(shí)間之和為T(mén)2，本節(jié)給出了一個(gè)下界為3/2和一個(gè)競(jìng)爭(zhēng)比為9/5的在線算法.

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

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

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

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

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

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

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

□

算法描述如算法2所示。

算法2H2算法

輸入：工件序列S。

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

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

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

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

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

情形1等級(jí)為2的工件都小于T2/3。假設(shè)L3>3T2/5，則L1(2)+L2<2T2/5，因?yàn)镴t分配給M3，則由H2算法可知，L2+pt>3T2/5,L1(2)+pt>2T2/5。若L1(2)=0，則pt>2T2/5>T2/3，與等級(jí)為2 的工件都小于T2/3矛盾。若L1(2)>0，則必有等級(jí)為2的工件分配給M1，由H2算法可知，分配給M1的任意1個(gè)等級(jí)為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等級(jí)為2的工件只有1個(gè)不小于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，因?yàn)榈燃?jí)為2 的工件只有1個(gè)不小于T2/3，所以pmax=pt。又Jt是分配給M3的最小工件，所以L3=pmax=pt。由H2算法可知，在這種情形，除工件Jt外，其它所有等級(jí)為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}，所以此時(shí)H2算法的分配達(dá)到最優(yōu)。若L1(2)>0，則必有等級(jí)為2 的工件分配給M1，由H2算法可知，L1(2)+L2>3T2/5，與L1(2)+L2<2T2/5矛盾，所以L3≤3T2/5。 由情形1可知，CH2/COPT≤9/5。

情形3等級(jí)為2的工件有2個(gè)不小于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，因?yàn)長(zhǎng)3>3T2/5，則pt=pmax>3T2/5。因此，由H2算法可知，在這種情形，除工件Jt外，其它所有等級(jí)為2的工件全部分配給了M2。由情形2可知此時(shí)H2算法的分配達(dá)到最優(yōu)。若M3至少被分配了2 個(gè)工件，又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等級(jí)為2的工件有3個(gè)不小于T2/3 (即等級(jí)為2的工件只有3個(gè)，且大小都為T(mén)2/3)。由H2算法可知，L1(2)=L2=L3=T2/3，因此，CH2=L1(2)+T1=T2/3+T1。若T1≤T2/3，此時(shí)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

已知等級(jí)為1的工件加工時(shí)間之和為T(mén)1，等級(jí)為2的工件加工時(shí)間之和為T(mén)2，本節(jié)給出了一個(gè)下界為4/3和一個(gè)競(jìng)爭(zhēng)比為3/2的在線算法。

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

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

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

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

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

證畢。

□

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

算法3H3算法

輸入：工件序列S。

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

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

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

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

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

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

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

證畢。

□

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

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

定理7對(duì)于P(1,2,2)|T|Cmax，任意在線算法A的競(jìng)爭(zhēng)比至少為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個(gè)工件J5=(2,2)，在J5被分配后，可得CA≥3,COPT=2。

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

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

證畢。

□

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

算法4H4算法

輸入：工件序列S。

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

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

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

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

證明若T1≥T2，由H4算法可知，等級(jí)為2的工件將全部分配給M2，即L2=T2≤T/2,L3=0，此時(shí)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é)束語(yǔ)

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