最大化接收工件总权值的批处理机在线排序

Online Batch-machine Scheduling to Maximize Total Weight of the Accepted Jobs

研究m台无界批处理机上的在线排序问题.每个工件J_j具有一个相同的加工时间p>0,一个到达时间r_j≥0,一个权值w_j>0,一个必须交货期d_j>0.无界批处理机是指一台机器可以同时加工任意多个工件,目标是确定一个工件允许被中断重启的在线排序使得接收工件的总权值最大化.主要设计了一个在线算法并证明其竞争比为3-1/m-(4m-2)(2m^2-m)^(1/2)/(2m^2-m).

This paper studies the online scheduling on m unbounded batch machines. Each job Jjhas a common processing time p 0,an arriving time rj≥0,a weight wj 0,a deadline dj 0. ＂Unbounded batch machines＂means that one machine can process up to countless jobs simultaneously as a batch. The goal is to determine a preemption-restart schedule which maximizes total weight of the accepted jobs. In this paper,we first design an online algorithm,and then prove that it has a competitive ratio of 3-1/m-（ 4m-2）（ 2m^2-m）^1/2/（ 2m^2-m）.