Non‐preemptive speed scaling

Non‐preemptive speed scaling

0.00 Avg rating0 Votes
Article ID: iaor20134176
Volume: 16
Issue: 4
Start Page Number: 385
End Page Number: 394
Publication Date: Aug 2013
Journal: Journal of Scheduling
Authors: ,
Keywords: NP-hard
Abstract:

We consider the following offline variant of the speed scaling problem introduced by Yao et al. We are given a set of jobs and we have a variable‐speed processor to process them. The higher the processor speed, the higher the energy consumption. Each job is associated with its own release time, deadline, and processing volume. The objective is to find a feasible schedule that minimizes the energy consumption. In contrast to Yao et al., no preemption of jobs is allowed. Unlike the preemptive version that is known to be in P, the non‐preemptive version of speed scaling is strongly NP‐hard. In this work, we present a constant factor approximation algorithm for it. The main technical idea is to transform the problem into the unrelated machine scheduling problem with L p equ1 ‐norm objective.

Reviews

Required fields are marked *. Your email address will not be published.