具有服务等级的可拒绝平行机排序问题
2016-12-15荣建华
荣 建 华
(石家庄铁道大学四方学院 基础部, 河北 石家庄 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