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

Parallel Machine Scheduling with Hierarchical and Rejection

作　　者：荣建华[1] 张国强[1] 孟昕娜[1] 贡丽霞[1] 

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

出　　处：《曲阜师范大学学报（自然科学版）》2017年第2期37-40,共4页Journal of Qufu Normal University(Natural Science)

摘　　要：研究了工件具有服务等级且可拒绝的平行机排序问题.设有两台平行机,加工速度相同;n个工件分别按列表在线到达,每个工件含有三个参数:加工长度,拒绝费用以及服务等级g_j=1,2.当且仅当g(Mi)≤gj时,工件J_j可由机器M_i加工,且加工不允许中断.进一步,当工件到达时,可以选择被加工,花费一定的加工时间;也可以被拒绝,此时要付出相应的罚值.目标为使被接收工件的最大完工时间与被拒绝工件的总罚值之和最小.文中设计出在线算法H,并证明算法的竞争比为1+(2^(1/2)/2)≈1.707,下界为5/3≈1.667,上下界大约相差0.04.An on-line scheduling problem on two parallel machines with rejection and hierarchical is investigated.Machines are provided with the same capabilities.Jobs come one by one over list.Euch job is associated with its length,penalty and hierarchical. A job Ji can be assigned to machine Mi if and only if g（Mi）≤gj .Preemption is not allowed.When a job arrives,it can either be assigned to a certain machine or rejected by paying out the penalty.The objective is to minimize the sum of the makespan produced by the accepted jobs and the total penalty of the jobs which have been rejected. An on-line approximation algorithms H is designed with competitive ratio 1＋（√2/2）≈1.707 while the lower bound being 5/3≈1.667.

关 键 词：在线算法 拒绝费用 竞争比 服务等级 排序 

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