Smart-grid electricity allocation via strip packing with slicing

Soroush Alamdari, Therese Biedl, Timothy M. Chan, Elyot Grant, Krishnam Raju Jampani, Srinivasan Keshav, Anna Lubiw, Vinayak Pathak

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

One advantage of smart grids is that they can reduce the peak load by distributing electricity-demands over multiple short intervals. Finding a schedule that minimizes the peak load corresponds to a variant of a strip packing problem. Normally, for strip packing problems, a given set of axis-aligned rectangles must be packed into a fixed-width strip, and the goal is to minimize the height of the strip. The electricity-allocation application can be modelled as strip packing with slicing: each rectangle may be cut vertically into multiple slices and the slices may be packed into the strip as individual pieces. The stacking constraint forbids solutions in which a vertical line intersects two slices of the same rectangle. We give a fully polynomial time approximation scheme for this problem, as well as a practical polynomial time algorithm that slices each rectangle at most once and yields a solution of height at most 5/3 times the optimal height.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings
Pages25-36
Number of pages12
DOIs
StatePublished - 2013
Externally publishedYes
Event13th International Symposium on Algorithms and Data Structures, WADS 2013 - London, ON, Canada
Duration: Aug 12 2013Aug 14 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8037 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other13th International Symposium on Algorithms and Data Structures, WADS 2013
Country/TerritoryCanada
CityLondon, ON
Period8/12/138/14/13

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Smart-grid electricity allocation via strip packing with slicing'. Together they form a unique fingerprint.

Cite this