---
_id: '580'
abstract:
- lang: eng
text: We present and study a new model for energy-aware and profit-oriented scheduling
on a single processor.The processor features dynamic speed scaling as well as
suspension to a sleep mode.Jobs arrive over time, are preemptable, and have different
sizes, values, and deadlines.On the arrival of a new job, the scheduler may either
accept or reject the job.Accepted jobs need a certain energy investment to be
finished in time, while rejected jobs cause costs equal to their values.Here,
power consumption at speed $s$ is given by $P(s)=s^{\alpha}+\beta$ and the energy
investment is power integrated over time.Additionally, the scheduler may decide
to suspend the processor to a sleep mode in which no energy is consumed, though
awaking entails fixed transition costs $\gamma$.The objective is to minimize the
total value of rejected jobs plus the total energy.Our model combines aspects
from advanced energy conservation techniques (namely speed scaling and sleep states)
and profit-oriented scheduling models.We show that \emph{rejection-oblivious}
schedulers (whose rejection decisions are not based on former decisions) have
– in contrast to the model without sleep states – an unbounded competitive ratio.It
turns out that the jobs' value densities (the ratio between a job's value and
its work) are crucial for the performance of such schedulers.We give an algorithm
whose competitiveness nearly matches the lower bound w.r.t\text{.} the maximum
value density.If the maximum value density is not too large, the competitiveness
becomes $\alpha^{\alpha}+2e\alpha$.Also, we show that it suffices to restrict
the value density of low-value jobs only.Using a technique from \cite{Chan:2010}
we transfer our results to processors with a fixed maximum speed.
author:
- first_name: Andreas
full_name: Cord-Landwehr, Andreas
last_name: Cord-Landwehr
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Fredrik
full_name: Mallmann Trenn, Fredrik
last_name: Mallmann Trenn
citation:
ama: 'Cord-Landwehr A, Kling P, Mallmann Trenn F. Slow Down & Sleep for Profit
in Online Deadline Scheduling. In: Even G, Rawitz D, eds. Proceedings of the
1st Mediterranean Conference on Algorithms (MedAlg). LNCS. ; 2012:218-231.
doi:10.1007/978-3-642-34862-4_17'
apa: Cord-Landwehr, A., Kling, P., & Mallmann Trenn, F. (2012). Slow Down &
Sleep for Profit in Online Deadline Scheduling. In G. Even & D. Rawitz (Eds.),
Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg)
(pp. 218–231). https://doi.org/10.1007/978-3-642-34862-4_17
bibtex: '@inproceedings{Cord-Landwehr_Kling_Mallmann Trenn_2012, series={LNCS},
title={Slow Down & Sleep for Profit in Online Deadline Scheduling}, DOI={10.1007/978-3-642-34862-4_17},
booktitle={Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg)},
author={Cord-Landwehr, Andreas and Kling, Peter and Mallmann Trenn, Fredrik},
editor={Even, Guy and Rawitz, DrorEditors}, year={2012}, pages={218–231}, collection={LNCS}
}'
chicago: Cord-Landwehr, Andreas, Peter Kling, and Fredrik Mallmann Trenn. “Slow
Down & Sleep for Profit in Online Deadline Scheduling.” In Proceedings
of the 1st Mediterranean Conference on Algorithms (MedAlg), edited by Guy
Even and Dror Rawitz, 218–31. LNCS, 2012. https://doi.org/10.1007/978-3-642-34862-4_17.
ieee: A. Cord-Landwehr, P. Kling, and F. Mallmann Trenn, “Slow Down & Sleep
for Profit in Online Deadline Scheduling,” in Proceedings of the 1st Mediterranean
Conference on Algorithms (MedAlg), 2012, pp. 218–231.
mla: Cord-Landwehr, Andreas, et al. “Slow Down & Sleep for Profit in Online
Deadline Scheduling.” Proceedings of the 1st Mediterranean Conference on Algorithms
(MedAlg), edited by Guy Even and Dror Rawitz, 2012, pp. 218–31, doi:10.1007/978-3-642-34862-4_17.
short: 'A. Cord-Landwehr, P. Kling, F. Mallmann Trenn, in: G. Even, D. Rawitz (Eds.),
Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg), 2012,
pp. 218–231.'
date_created: 2017-10-17T12:42:45Z
date_updated: 2022-01-06T07:02:42Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-642-34862-4_17
editor:
- first_name: Guy
full_name: Even, Guy
last_name: Even
- first_name: Dror
full_name: Rawitz, Dror
last_name: Rawitz
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T09:03:39Z
date_updated: 2018-03-15T09:03:39Z
file_id: '1265'
file_name: 580-P._Kling__F._Mallmann-Trenn__A._Cord-Landwehr_-_Slow_Down___Sleep_for_Profit_in_Online_Deadline_Scheduling.pdf
file_size: 325939
relation: main_file
success: 1
file_date_updated: 2018-03-15T09:03:39Z
has_accepted_license: '1'
language:
- iso: eng
page: 218-231
project:
- _id: '1'
name: SFB 901
- _id: '14'
name: SFB 901 - Subprojekt C2
- _id: '16'
name: SFB 901 - Subproject C4
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg)
series_title: LNCS
status: public
title: Slow Down & Sleep for Profit in Online Deadline Scheduling
type: conference
user_id: '477'
year: '2012'
...