| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428613 | Information Processing Letters | 2011 | 5 Pages |
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.
