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

Parallel machine scheduling with service hierarchy and rejection

作　　者：荣建华[1] 

机构地区：[1]石家庄铁道大学四方学院基础部,河北石家庄051132

出　　处：《浙江大学学报（理学版）》2016年第6期685-688,共4页Journal of Zhejiang University（Science Edition）

基　　金：河北省高等教育教学改革研究与实践项目(2015GJJG293);河北省高等教育科学研究课题(GJXH2015-291)

摘　　要：研究了将服务等级与拒绝费用2种模型复合起来的平行机排序问题.设有2台平行机M_1,M_2,加工速度相同;n个工件J_1,J_2,…,J_n分别按列表在线到达,每个工件J_j含有3个参数:加工长度t_j、拒绝费用p_j以及服务等级g_j=1,2.当工件到达时,可以接收加工,占用一定的加工时间;亦可拒绝,付出相应的罚值.目标为被接收工件的最大完工时间与被拒绝工件的总罚值之和最小.进一步,当且仅当g(M_i)≤g_j时,工件J_j可以分配给机器Mi加工,即机器M_1可以加工所有工件,机器M_2只能加工等级为g_j=2的工件,允许中断加工.设计了在线算法PH,并证明其竞争比为1+2^(1/2)/2≈1.707,下界为1.618,上下界差约为0.089.The on-line scheduling problem on two parallel machines with rejection and service hierarchy is investigated.Machines M_1,M_2 are provided with the same capabilities.Jobs come one by one over the list.Every job J_jis associated with its length t_j,penalty pjand service hierarchy g_j=1,2.When a job arrives,it can either be assigned to a certain machine or be rejected by paying the penalty.The objective is to minimize the sum of the makespan of all accepted jobs and the total penalty of rejection.A job J_jcan be assigned to machine Miif and only if g（M_i）≤g_j,i.e,M_1 can process all jobs while M_2 can only process the jobs with g_j=2.Assuming that preemption is allowed,we propose an on-line approximation algorithm PH with competitive ratio 1＋2^（1/2）/2≈1.707 while the lower bound is 1.618.

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

分 类 号：O223[理学—运筹学与控制论]