Competitively scheduling tasks with intermediate parallelizability
Sungjin Im, Benjamin Moseley, Kirk R. Pruhs, Eric K. Torng · 2014
We introduce a scheduling algorithm Intermediate-SRPT, and show that it is O(log P)-competitive with respect to average waiting time when scheduling jobs whose parallelizability is intermediate between being fully parallelizable and sequential. Here the parameter P denotes the ratio between the maximum job size to the minimum. We also show a general matching lower bound on the competitive ratio. Our analysis builds on an interesting combination of potential function and local competitiveness arguments.