具有服務等級的可拒絕平行機排序問題

榮 建 華

(石家莊鐵道大學四方學院 基礎部， 河北 石家莊 051132)

?

具有服務等級的可拒絕平行機排序問題

榮 建 華

(石家莊鐵道大學四方學院 基礎部， 河北 石家莊 051132)

在線排序；平行機；拒絕費用；競爭比；服務等級

0 引 言

排序問題是運籌學與組合優化領域一類重要的問題，對排序理論的研究具有重要的理論意義和廣闊的應用前景.近年來，在含多個窗口的服務業，如銀行等領域，經常存在以下2種現象：首先，提供服務的機構通常有多個不同等級的窗口，如一般窗口、貴賓窗口；顧客也有不同的級別，如一般會員、金卡會員、銀卡會員.等級低的窗口為所有顧客服務，等級高的窗口只為高級別的顧客服務.其次，服務存在雙向選擇，提供服務的一方為了考慮總體效益，可以提供服務需求，花費一定的服務成本；顧客也會因為得不償失而拒絕需求，但此時要付出拒絕費用，最終希望整體利益達到最優.工件帶有拒絕費用和服務等級的排序問題是現代工業生產中出現的2個新的組合優化模型，近年來受到許多研究人員的關注.本文將工件可拒絕與具有服務等級2個模型復合起來，即研究具有服務等級的可拒絕平行機在線排序問題.基本問題描述如下：假定有2臺平行機M1,M2，加工速度一致；n個工件J1,J2,…,Jn,分別按列表在線到達，每個工件Jj含有3個參數：加工長度tj，拒絕費用pj以及服務等級gj=1,2.當工件到達時，可以接收加工，占用一定的加工時間；也可以拒絕，付出相應的罰值.進一步，如果工件被接收，則等級gj=1的工件只能分配在機器M1上加工；等級gj=2的工件被分成2兩部分，分別被安排到機器M1，M2上加工.目標為被接收工件的最大完工時間(makespan)與被拒絕工件的總罰值之和最小.為此本文設計了在線算法PH.

1 P2|gj=2,online|W的算法設計

為便于分析算法，下面引入一些常用的記號：

A、R：算法中分別被接收和拒絕的工件集；

A″k：算法中被接收最優解中被拒絕的等級為k的工件集；

R′：算法和最優解中均被拒絕的工件集；

R″k：算法中被拒絕最優解中被接收的等級為k的工件集；

L(S),S?J∶S中工件的總長度；

P(S),S?J∶S中工件的總罰值；

C(E)：算法中將E作為被加工工件集時的最長完工時間；

C*(E)：最優解中生成的最長完工時間；

WPH：算法生成的目標值；

W*：最優解中生成的目標值.

下面給出在證明競爭比過程中非常有用的幾個引理.

其中tmax為A中最大工件的長度.

引理2[8]設Q=(1,1,…,1)T，K=(k1,k2,…,ku)為1×u矩陣，X=(x1,x2,…,xn)T為u×1矩陣，P=(pij)u×u為可逆矩陣，其中第j行行向量記作αj.如果KP-1≥0,則?X≥0，均有KX≤(KP-1Q)max{α1X,α2X,…,αuX}.

由引理2可得

下面給出在線算法PH的具體描述：

當工件Jj到達時,

規則G1：若gj=1，則將工件Jj分配給機器M1加工；

引理4 設A為被加工的工件集，A中等級為1的工件總是分給M1加工，等級為2的工件按G2規則加工，令x為A中最后一個被加工的工件，則下列結論成立：

證明 (i)如果分配到M1上的均為等級為1的工件，則

(1)

否則，至少存在一個等級為2的工件部分分配在M1上加工，令y為最后一個分配在M1上具有等級2的工件.不妨令ty1=(1-λ)ty，ty2=λty，λ∈(0,1)，并分別將其分配給M1，M2加工，Lxy為工件x,y之間機器M1的負載(不含x,y的長度)，則

(2)

C(A)=

證明 情形1 若A=φ，算法將所有工件拒絕，于是

情形2.2 若gx=2，由引理4可知，

于是有

證畢！

2 結 語

研究了復合服務等級和可拒絕2種模型的2臺平行機排序問題，在工件被接收加工的情形下，等級為2的工件允許被拆分.文中設計了在線算法PH，并證明了其競爭比為1.707，下界為1.618，上下界差約0.089.下一步將致力于構造更精確的算法，以進一步縮小上下界差.

[1] BARTAL Y, LEONARDI S, MARCHETTI-SPACCAMELA A, et al. Multiprocessor scheduling with rejection[J]. SIAM J on Discrete Mathematics,2000,13:64-78.

[2] HE Y,MIN X.On-line uniform machine scheduling with rejection[J]. Operations Research Transactions,2009,13(1):29-36.

[3] DOSA G, HE Y. Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines[J]. Computing,2006,76:149-164.

[4] JIANG Y W, HE Y, TANG C M. Optimal online algorithm for scheduling on identical machines under a grader of service[J]. Journal of Zhejiang University: Science A,2006,7(3):309-314.

[5] PARK J, CHANG S Y, LEE K. Online and semi-online scheduling of two machines under a grader of service provision[J]. Operations Research Letters,2006,34:692-696.

[6] JIANG Y. Online scheduling on parallel machines with two GoS levels[J]. Journal of Combinatorial Optimization,2008,16:28-38.

[7] ZHANG A, JIANG Y, TAN Z. Online parallel machines scheduling with two hierarchies[J]. Theoretical Computer Science,2009,410:3597-3605.

[8] TAN Z, ZHANG A. A note on hierarchical scheduling on two uniform machines[J]. Journal of Combinatorial Optimization, 2010,20:85-95.

RONG Jianhua

(DepartmentofBasic,ShijiazhuangTiedaoUniversitySifangCollege,Shijiazhuang051132,China)

Parallel machine scheduling with service hierarchy and rejection. Journal of Zhejiang University(Science Edition), 2016,43(6):685-688

on-line scheduling; parallel machine; penalty of rejection; competitive ratio; hierarchical

2015-12-18.

河北省高等教育教學改革研究與實踐項目(2015GJJG293)；河北省高等教育科學研究課題(GJXH2015-291).

榮建華(1981-)，ORCID:http://orcid.org/0000-0002-7147-4866，女，碩士，講師，主要從事組合優化、排序理論研究,E-mail:rongjianhua2006@126.com.

10.3785/j.issn.1008-9497.2016.06.012

O 223

A

1008-9497(2016)06-685-04