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

作者：Moselely, Benjamin; Zhang, Ruilong^*; Zhao, Shanjiawen

来源：Theoretical Computer Science, 2022, 938: 24-38.

DOI：10.1016/j.tcs.2022.10.005

• Scheduling
• DAG jobs
• Parallelizable jobs
• Online algorithms
• l(k)-norm of flow time
• Competitive analysis

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 pound of flow time fork > 1.We establish an omega(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 + is an element of) -speed O( 1/ is an element of(2k)+1 )-competitive algorithm in the DAG model for the l(k)-norms of flow time. This essentially matches the best-known result in the speed-up curve model for the l(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.