On-line scheduling with equal-length jobs on parallel-batch machines to minimise maximum flow-time with delivery times

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 $1+{\alpha }_m$, where α_m is the positive root of $x^2+\mathit{mx}=1$. When the capacity of each batch is bounded, we provide a best possible on-line algorithm of competitive ratio $\frac{\sqrt{5}+1}{2}$. 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 $\sqrt{2}$ for m = 1 and an on-line algorithm of competitive ratio $\frac{3}{2}$ for $m\ge 2$.

Keywords:

• On-line scheduling
• parallel-batch
• flow-time
• delivery time
• competitive ratio

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research was supported by the National Natural Science Foundation of China [grant Numbers: 11571321 and 11771406].