Online scheduling of parallelizable jobs in the directed acyclic graphs and speed-up curves models

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)24-38
Journal / PublicationTheoretical Computer Science
Online published13 Oct 2022
Publication statusPublished - 26 Nov 2022


This paper considers scheduling jobs online on m identical machines such that the jobs can be parallelized across the machines. Two models of parallelizability are considered, one is the speed-up curves model, and the other is the directed-acyclic-graph (DAG) model. For both models, the objectives considered are the average, maximum, and k-norms of flow time for k≥1. 
We establish an Ω(m) lower bound on the competitive ratio of any algorithm for optimizing average flow time in both models without resource augmentation. With resource augmentation, we give a (1+ϵ)-speed O(1/ε2k+1)-competitive algorithm in the DAG model for the k-norms of flow time. This essentially matches the best-known result in the speed-up curve model for the k-norms of flow time. Finally, we show an O(1)-competitive algorithm for minimizing the maximum flow time in the speed-up curves model.

Research Area(s)

  • Competitive analysis, DAG jobs, Online algorithms, Parallelizable jobs, Scheduling, ℓk-norm of flow time