中文摘要：

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

英文摘要：

A batch machine can process a number of jobs simultaneously as a batch, where all the jobs processed in a batch have the same start time and the same completion time, and the processing time of a batch is given by the longest processing time of the jobs assigned to it. This paper deals with the online scheduling problem of min- imizing the maximum completion time on a batch machine, where each job has an unknown arrival time and its processing time becomes known upon its arrival. Zhang et al. （ Naval Research Logistics, 2001, 48 ： 241-258） suggested an algorithm MH^B for the problem, and conjectured that MH^B is a best possible on-line algorithm with the competitive ratio 1. 618. We give a negative answer to the conjecture by proving that the competitive ratio of MH^B tends to 2 as the machine capacity tends to infinity. Also, we present a new 2-competitive algorithm for the problem.