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^alphacompetitive 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 nonnegative. Besides, we also consider the problem of minimizing the weighted flowtime 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 EnergyEfficient Scheduling}},
booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
pages = {20:120:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770118},
ISSN = {18688969},
year = {2016},
volume = {53},
editor = {Rasmus Pagh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6042},
URN = {urn:nbn:de:0030drops60427},
doi = {10.4230/LIPIcs.SWAT.2016.20},
annote = {Keywords: Online Scheduling, Energy Minimization, Speed Scaling and Powerdown, Lagrangian Duality}
}
Keywords: 

Online Scheduling, Energy Minimization, Speed Scaling and Powerdown, Lagrangian Duality 
Collection: 

15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) 
Issue Date: 

2016 
Date of publication: 

22.06.2016 