Scheduling Jobs with Work-Inefficient Parallel Solutions

This paper introduces the 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) work-inefficient. As tasks arrive, the scheduler must decide for each task which implementation to use. We begin by studying total awake time. We give a simple decide-on-arrival scheduler that achieves a competitive ratio of 3 for total awake time -- this scheduler makes serial/parallel decisions immediately when jobs arrive. Our second result is an parallel-work-oblivious scheduler that achieves a competitive ratio of 6 for total awake time -- this scheduler makes all of its decisions based only on the size of each serial job and without needing to know anything about the parallel implementations. Finally, we prove a lower bound showing that, if a scheduler wishes to achieve a competitive ratio of O (1), it can have at most one of the two aforementioned properties (decide-on-arrival or parallel-work-oblivious). We also prove lower bounds of the form 1 + (1) on the optimal competitive ratio for any scheduler. Next, we turn our attention to optimizing mean response time. Here, we show that it is possible to achieve an O (1) competitive ratio with O (1) speed augmentation. This is the most technically involved of our results. We also prove that, in this setting, it is not possible for a parallel-work-oblivious scheduler to do well. In addition to these results, we present tight bounds on the optimal competitive ratio if we allow for arrival dependencies between tasks (e. g. , tasks are components of a single parallel program), and we give an in-depth discussion of the remaining open questions.