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

On-line Scheduling on Three Identical Machines with Rejection

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

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

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

基　　金：南京农业大学青年科技创新基金(0506J0116);河北省高等教育教学改革研究与实践项目(2015GJJG293);河北省高等教育科学研究课题(GJXH2015-291)

摘　　要：研究了工件带有拒绝费用的3台平行机在线算法,假定有3台平行机M_1,M_2,M_3,n个工件J_1,J_2,…,J_n,每个工件可以被接收加工,消耗一定的加工时间tj;也可以被拒绝,但要付出相应的拒绝费用pj,目标为被接收工件的最大完工时间(makespan)与被拒绝工件的总罚值之和最小。进一步,假定每个工件有两套拒绝策略,最后输出目标值较好的一种。文中设计出在线算法H,并证明算法的竞争比为15/8。This paper investigates the on-line scheduling problem on three identical machines with re-jection . An identical processors system denoted by M1 ,M2 ,M3 and a sequence of independent jobs J1 , J2 ,Jn are given. When a job arrives,we can either reject it,in which case we pay its penalty,or accept it in which case it contributes its processing time to the makespan of the constructed schedule. The objec- tive is to minimize the sum of the makespan of the schedule of all accepted jobs and the penalties of all rejected jobs. In addition,two schemes could be choosen and we can select the better solution finally. We 15 present an approximation algorithm with competitive ratio 15/8.

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

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