Randomized On-Line Scheduling of Parallel Jobs

We study randomized on-line scheduling on mesh machines. We show that for scheduling independent jobs randomized algorithms can achieve a significantly better performance than deterministic ones; on the other hand with dependencies randomization does not help. this research was done at Carnegie-Mellon University, Pittsburgh, PA, U.S.A. 1 Introduction In this paper we study the power of randomization for on-line scheduling of parallel jobs in a model which was introduced and studied in [4, 3] for deterministic scheduling. We give a randomized on-line algorithm for scheduling independent jobs on mesh machines which is significantly better than the optimal deterministic algorithm from [4]. On the other hand, for scheduling of jobs with dependencies on one-dimensional meshes, we show that randomization does not help---no randomized algorithm has asymptotically better performance on the worst-case input than the optimal deterministic algorithm from [3]. These results are particularly i..