A BEST POSSIBLE ONLINE ALGORITHM FOR SCHEDULING TO MINIMIZE MAXIMUM FLOW-TIME ON BOUNDED BATCH MACHINES

We consider online scheduling of unit length jobs on m identical parallel-batch machines. Jobs arrive over time. The objective is to minimize maximum flow-time, with the flow-time of a job being the difference of its completion time and its release time. A parallel-batch machine can handle up to b jobs simultaneously as a batch. Here, the batch capacity is bounded, that is b < ∞. In this paper, we provide a best possible online algorithm for the problem with a competitive ratio of $\frac{\sqrt{5}+1}{2}\approx 1.618$.