We study an online job scheduling problem arising in networks with aggregated links. The goal is to schedule n jobs, divided into k disjoint chains, on m identical machines, without preemption, so that the jobs within each chain complete in the order of release times and the maximum flow time is minimized.#R##N##R##N#We present a deterministic online algorithm $\mathsf{Block}$ with competitive ratio $O(\sqrt{n/m})$, and show a matching lower bound, even for randomized algorithms. The performance bound for $\mathsf{Block}$ we derive in the paper is, in fact, more subtle than a standard competitive ratio bound, and it shows that in overload conditions (when many jobs are released in a short amount of time), $\mathsf{Block}$ ’s performance is close to the optimum.#R##N##R##N#We also show how to compute an offline solution efficiently for k=1, and that minimizing the maximum flow time for k,m≥2 is ${ \mathcal {N}\mathcal {P}}$-hard. As by-products of our method, we obtain two offline polynomial-time algorithms for minimizing makespan: an optimal algorithm for k=1, and a 2-approximation algorithm for any k.
['Wojciech Jawor', 'Marek Chrobak', 'Christoph Dürr']
Competitive Analysis of Scheduling Algorithms for Aggregated Links