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.ISAAC.2016.53
URN: urn:nbn:de:0030-drops-68252
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6825/
Go to the corresponding LIPIcs Volume Portal

Liu, Fu-Hong ; Liu, Hsiang-Hsuan ; Wong, Prudence W. H.

Optimal Nonpreemptive Scheduling in a Smart Grid Model

pdf-format:
LIPIcs-ISAAC-2016-53.pdf (0.5 MB)

Abstract

We study a scheduling problem arising in demand response management in smart grid. Consumers send in power requests with a flexible feasible time interval during which their requests can be served. The grid controller, upon receiving power requests, schedules each request within the specified interval. The electricity cost is measured by a convex function of the load in each timeslot. The objective is to schedule all requests with the minimum total electricity cost. Previous work has studied cases where jobs have unit power requirement and unit duration. We extend the study to arbitrary power requirement and duration, which has been shown to be NP-hard. We give the first online algorithm for the general problem, and prove that the worst case competitive ratio is asymptotically optimal. We also prove that the problem is fixed parameter tractable. Due to space limit, the missing proofs are presented in the full paper.

BibTeX - Entry

@InProceedings{liu_et_al:LIPIcs:2016:6825,
  author =	{Fu-Hong Liu and Hsiang-Hsuan Liu and Prudence W. H. Wong},
  title =	{{Optimal Nonpreemptive Scheduling in a Smart Grid Model}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{53:1--53:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6825},
  URN =		{urn:nbn:de:0030-drops-68252},
  doi =		{10.4230/LIPIcs.ISAAC.2016.53},
  annote =	{Keywords: Scheduling, Smart Grid, Convex function cost, Fixed parameter tractable, Online algorithms, Non-preemptive}
}

Keywords: Scheduling, Smart Grid, Convex function cost, Fixed parameter tractable, Online algorithms, Non-preemptive
Collection: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue Date: 2016
Date of publication: 07.12.2016

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