带有到达时间和拒绝费用工件的同类机排序问题  

Uniform machine scheduling with arrival time and rejection

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

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

出　　处：《浙江大学学报（理学版）》2016年第5期545-549,共5页Journal of Zhejiang University（Science Edition）

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

摘　　要：研究了工件带有拒绝费用的m台同类机在线排序问题,m台机器的速度分别为s1=s2=…=sm-1=1,sm=s,当工件到达时,可以接收加工,占用一定的加工时间,也可以拒绝,付出相应的罚值.目标是被接收工件的最长完工时间(makespan)与被拒绝工件的总罚值之和最小.对工件2次到达时间问题(零时刻和r时刻各到达一批工件)设计了在线算法H,并证明该算法的竞争比为4-2ss+m-1.An on‐line scheduling problem on m uniform machines with arrival time and rejection is investigated .The speeds of the machines are respectively s1 = s2 = …= sm-1 =1 ,sm= s .When a job arrives ,it can either be assigned to a certain machine or be rejected by paying penalty .The objective is to minimize the sum of the makespan of all ac‐cepted jobs and the total penalty of the rejection .In addition ,for jobs that arrive at two different times ,namely zero and r ,we propose an on‐line approximation algorithm H with competitive ratio is 4- 2ss＋ m-1 .

关 键 词：在线排序 同类机 拒绝费用 竞争比 

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