论文部分内容阅读
一台批处理机一次可以同时加工多个工件（称为一批），每批工件有相同的开工和完工时间，加工时间等于其中最长工件的加工时间。本文研究单台批处理机上的在线排序，其中每个工件有事先未知的到达时间，加工时间在其到达时才知道，目标是极小化工件的最大完工时间。Zhang等（Naval Research Logistics，2001，48：241—258）就该问题提出了一个竞争比不超过2的算法MH^B，并猜测其竞争比可以达到1．618，因此是最好的在线算法。在本文中，我们证明了当机器容量趋于无穷时，算法MH^B的竞争比不可