Scheduling Jobs with Work-Inefficient Parallel Solutions
Scheduling Jobs with Work-Inefficient Parallel Solutions
This paper introduces the \emph{serial-parallel decision problem}. Consider an online scheduler that receives a series of tasks, where each task has both a parallel and a serial implementation. The parallel implementation has the advantage that it can make progress concurrently on multiple processors, but the disadvantage that it is (potentially) …