Scalably scheduling processes with arbitrary speedup curves

Abstract

We give a scalable ((1+e)-speed O(1)-competitive) non-clairvoyant algorithm for scheduling jobs with sublinear nondecreasing speed-up curves on multiple processors with the objective of average response time.