TY - GEN

T1 - Smart-grid electricity allocation via strip packing with slicing

AU - Alamdari, Soroush

AU - Biedl, Therese

AU - Chan, Timothy M.

AU - Grant, Elyot

AU - Jampani, Krishnam Raju

AU - Keshav, Srinivasan

AU - Lubiw, Anna

AU - Pathak, Vinayak

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84881142425&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84881142425&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-40104-6_3

DO - 10.1007/978-3-642-40104-6_3

M3 - Conference contribution

AN - SCOPUS:84881142425

SN - 9783642401039

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 25

EP - 36

BT - Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings

T2 - 13th International Symposium on Algorithms and Data Structures, WADS 2013

Y2 - 12 August 2013 through 14 August 2013

ER -