License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2016.20
URN: urn:nbn:de:0030-drops-60427
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6042/
Go to the corresponding LIPIcs Volume Portal

Kim Thang, Nguyen

Lagrangian Duality based Algorithms in Online Energy-Efficient Scheduling

pdf-format:
LIPIcs-SWAT-2016-20.pdf (0.4 MB)

Abstract

We study online scheduling problems in the general energy model of speed scaling with power down. The latter is a combination of the two extensively studied energy models, speed scaling and power down, toward a more realistic one. Due to the limits of the current techniques, only few results have been known in the general energy model in contrast to the large literature of the previous ones.

In the paper, we consider a Lagrangian duality based approach to design and analyze algorithms in the general energy model. We show the applicability of the approach to problems which are unlikely to admit a convex relaxation. Specifically, we consider the problem of minimizing energy with a single machine in which jobs arrive online and have to be processed before their deadlines. We present an alpha^alpha-competitive algorithm (whose the analysis is tight up to a constant factor) where the energy power function is of typical form z^alpha + g for constants alpha > 2 and g non-negative. Besides, we also consider the problem of minimizing the weighted flow-time plus energy. We give an O(alpha/ln(alpha))-competitive algorithm; that matches (up to a constant factor) to the currently best known algorithm for this problem in the restricted model of speed scaling.

BibTeX - Entry

@InProceedings{kimthang:LIPIcs:2016:6042,
  author =	{Nguyen Kim Thang},
  title =	{{Lagrangian Duality based Algorithms in Online Energy-Efficient Scheduling}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Rasmus Pagh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6042},
  URN =		{urn:nbn:de:0030-drops-60427},
  doi =		{10.4230/LIPIcs.SWAT.2016.20},
  annote =	{Keywords: Online Scheduling, Energy Minimization, Speed Scaling and Power-down, Lagrangian Duality}
}

Keywords: Online Scheduling, Energy Minimization, Speed Scaling and Power-down, Lagrangian Duality
Collection: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Issue Date: 2016
Date of publication: 22.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI