具有服务等级的可拒绝平行机排序问题

具有服务等级的可拒绝平行机排序问题

荣 建 华

【摘 要】研究了将服务等级与拒绝费用2种模型复合起来的平行机排序问题.设有2台平行机M1,M2，加工速度相同；n个工件J1,J2,…,Jn分别按列表在线到达，每个工件Jj含有3个参数：加工长度tj、拒绝费用pj以及服务等级gj=1,2.当工件到达时，可以接收加工，占用一定的加工时间；亦可拒绝，付出相应的罚值.目标为被接收工件的最大完工时间与被拒绝工件的总罚值之和最小.进一步，当且仅当g(Mi)≤gj时，工件Jj可以分配给机器Mi加工，即机器M1可以加工所有工件，机器M2只能加工等级为gj=2的工件，允许中断加工.设计了在线算法PH,并证明其竞争比为,下界为1.618，上下界差约为0.089. 【期刊名称】浙江大学学报（理学版） 【年(卷),期】2016(043)006 【总页数】4

【关键词】关 键 词：在线排序；平行机；拒绝费用；竞争比；服务等级

0 引 言

排序问题是运筹学与组合优化领域一类重要的问题，对排序理论的研究具有重要的理论意义和广阔的应用前景.近年来，在含多个窗口的服务业，如银行等领域，经常存在以下2种现象：首先，提供服务的机构通常有多个不同等级的窗口，如一般窗口、贵宾窗口；顾客也有不同的级别，如一般会员、金卡会员、银卡会员.等级低的窗口为所有顾客服务，等级高的窗口只为高级别的顾客服务.其次，服务存在双向选择，提供服务的一方为了考虑总体效益，可以提供服务需求，花费一定的服务成本；顾客也会因为得不偿失而拒绝需求，但此时要付