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

摘要

研究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).