带拒绝费用的平行机在线排序

荣建华, 侯丽英

doi:10.13319/j.cnki.sjztddxxbzrb.2016.02.21

石家庄铁道大学学报（自然科学版） ›› 2016, Vol. 29 ›› Issue (02) : 107 -110. DOI: 10.13319/j.cnki.sjztddxxbzrb.2016.02.21

带拒绝费用的平行机在线排序

荣建华, 侯丽英

作者信息 +

Author information +

文章历史 +

PDF

摘要

研究了工件带有拒绝费用的m台平行机在线算法,假定有m台平行机M₁,M₂,…,M_m,n个工件J₁,J₂,…,J_n,每个工件的加工时间与拒绝费用成固定的比例α（α≥0）,即p_j=αt_j,当α较大时,即工件的拒绝费用相对于加工时间较大,则将此工件接收加工;当α较小时,即每个工件的拒绝费用相对于其加工时间较小,此时将工件拒绝。文中设计出在线算法PRLS,并证明算法的竞争比为关于参数α的分段函数,且为紧界。