三台可拒绝平行机在线排序问题的近似算法

荣建华, 侯丽英

doi:10.13319/j.cnki.sjztddxxbzrb.2017.02.18

石家庄铁道大学学报（自然科学版） ›› 2017, Vol. 30 ›› Issue (02) : 101 -104+110. DOI: 10.13319/j.cnki.sjztddxxbzrb.2017.02.18

三台可拒绝平行机在线排序问题的近似算法

荣建华, 侯丽英

作者信息 +

Author information +

文章历史 +

PDF

摘要

研究了工件带有拒绝费用的3台平行机在线算法,假定有3台平行机M₁,M₂,M₃,n个工件J₁,J₂,…,J_n,每个工件可以被接收加工,消耗一定的加工时间tj;也可以被拒绝,但要付出相应的拒绝费用pj,目标为被接收工件的最大完工时间（makespan）与被拒绝工件的总罚值之和最小。进一步,假定每个工件有两套拒绝策略,最后输出目标值较好的一种。文中设计出在线算法H,并证明算法的竞争比为15/8。