Online scheduling on unbounded parallel-batch machines to minimize maximum flow-time

We consider online scheduling on m   unbounded parallel-batch machines to minimize maximum flow-time of the jobs. We show that no online algorithm can have a competitive ratio less than 1+αm1+αm, where αmαm is the positive root of α2+(m+1)α−1=0α2+(m+1)α−1=0, and this lower bound is still valid even when all jobs have the same processing times. Then we provide an online algorithm of competitive ratio 1+1/m1+1/m. When the jobs have the same processing times, we present a best possible online algorithm of competitive ratio 1+αm1+αm.

► We consider online batch scheduling on m   machines to minimize maximum flow-time.
► The lower bound of competitive ratio is 1+αm1+αm, where αmαm is the positive root of α2+(m+1)α−1=0α2+(m+1)α−1=0.
► We provide an online algorithm of competitive ratio 1+1m.
► When the processing times are the same, we present a best possible online algorithm.