The Bell Is Ringing in Speed-Scaled Multiprocessor Scheduling

Abstract

This paper investigates the problem of scheduling jobs on multiple speed-scaled processors, i.e., we have constant α>1 such that running a processor at speed s results in energy consumption s α per time unit. We consider the general case where each job has a monotonously increasing cost function that penalizes delay. This includes the so far considered cases of deadlines, flow time, and weighted flow time. For any type of delay cost functions, we obtain the following results: Any β-approximation algorithm for a single processor yields a randomized βB α-approximation algorithm for multiple processors, where B α is the αth Bell number, that is, the number of partitions of a set of size α. The generated schedule is without migration, but we compare it to an optimal schedule with migration. Hence, this result holds for migratory and non-migratory schedules. Analogously, we show that any β-competitive online algorithm for a single processor yields a βB α-competitive online algorithm for multiple processors. Finally, we show that any β-approximation algorithm for multiple processors with migration yields a deterministic βB α-approximation algorithm for multiple processors without migration. These facts improve several approximation ratios and lead to new results. For instance, we obtain the first constant factor online and offline approximation algorithm for multiple processors without migration for arbitrary release times, deadlines, and job sizes. © 2013 Springer Science+Business Media New York.