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

On-line Scheduling on Identical Machines with Rejection

作　　者：荣建华[1] 侯丽英[2] 

机构地区：[1]石家庄铁道大学四方学院基础部,河北石家庄051132 [2]南京农业大学理学院,江苏南京210095

出　　处：《石家庄铁道大学学报（自然科学版）》2016年第2期107-110,共4页Journal of Shijiazhuang Tiedao University(Natural Science Edition)

基　　金：国家自然科学基金(11426133);南京农业大学青年科技创新基金(0506J0116)

摘　　要：研究了工件带有拒绝费用的m台平行机在线算法,假定有m台平行机M_1,M_2,…,M_m,n个工件J_1,J_2,…,J_n,每个工件的加工时间与拒绝费用成固定的比例α(α≥0),即p_j=αt_j,当α较大时,即工件的拒绝费用相对于加工时间较大,则将此工件接收加工;当α较小时,即每个工件的拒绝费用相对于其加工时间较小,此时将工件拒绝。文中设计出在线算法PRLS,并证明算法的竞争比为关于参数α的分段函数,且为紧界。This paper investigates the on-line scheduling problem on m identical machines with rejection.An identical processors system denoted by and a sequence of independent jobs are given.We assume that the processing time of each job and its penalty forms the regular proportion denoted by.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.Preemption is not allowed.For this version,we present an on-line algorithm and prove the competitive ratio.

关 键 词：在线排序 竞争比 同型机 拒绝费用 不可中断 运筹学 

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