Abstract
We consider on-line scheduling on m parallel-batch machines with equal-length jobs. The jobs arrive over time and the goal is to minimise the maximum flow-time with delivery times. When the capacity of each batch is unbounded, we provide a best possible on-line algorithm of competitive ratio , where αm is the positive root of . When the capacity of each batch is bounded, we provide a best possible on-line algorithm of competitive ratio . For the non-batch model, i.e., the capacity of each batch is 1, we provide a best possible on-line algorithm of competitive ratio for m = 1 and an on-line algorithm of competitive ratio for .
Disclosure statement
No potential conflict of interest was reported by the authors.