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