---
res:
bibo_abstract:
- We present a new online algorithm for profit-oriented scheduling on multiple speed-scalable
processors.Moreover, we provide a tight analysis of the algorithm's competitiveness.Our
results generalize and improve upon work by \citet{Chan:2010}, which considers
a single speed-scalable processor.Using significantly different techniques, we
can not only extend their model to multiprocessors but also prove an enhanced
and tight competitive ratio for our algorithm.In our scheduling problem, jobs
arrive over time and are preemptable.They have different workloads, values, and
deadlines.The scheduler may decide not to finish a job but instead to suffer a
loss equaling the job's value.However, to process a job's workload until its deadline
the scheduler must invest a certain amount of energy.The cost of a schedule is
the sum of lost values and invested energy.In order to finish a job the scheduler
has to determine which processors to use and set their speeds accordingly.A processor's
energy consumption is power $\Power{s}$ integrated over time, where $\Power{s}=s^{\alpha}$
is the power consumption when running at speed $s$.Since we consider the online
variant of the problem, the scheduler has no knowledge about future jobs.This
problem was introduced by~\citet{Chan:2010} for the case of a single processor.They
presented an online algorithm which is $\alpha^{\alpha}+2e\alpha$-competitive.We
provide an online algorithm for the case of multiple processors with an improved
competitive ratio of $\alpha^{\alpha}$.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Peter
foaf_name: Kling, Peter
foaf_surname: Kling
- foaf_Person:
foaf_givenName: Peter
foaf_name: Pietrzyk, Peter
foaf_surname: Pietrzyk
bibo_doi: 10.1145/2486159.2486183
dct_date: 2013^xs_gYear
dct_language: eng
dct_title: Profitable Scheduling on Multiple Speed-Scalable Processors@
...