Document Open Access Logo

Optimal Nonpreemptive Scheduling in a Smart Grid Model

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

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.53.pdf
  • Filesize: 0.53 MB
  • 13 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

Fu-Hong Liu, Hsiang-Hsuan Liu, and Prudence W. H. Wong. Optimal Nonpreemptive Scheduling in a Smart Grid Model. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 53:1-53:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ISAAC.2016.53

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.

Subject Classification

Keywords
  • Scheduling
  • Smart Grid
  • Convex function cost
  • Fixed parameter tractable
  • Online algorithms
  • Non-preemptive

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Soroush Alamdari, Therese Biedl, Timothy Chan, Elyot Grant, Krishnam Jampani, Srinivasan Keshav, Anna Lubiw, and Vinayak Pathak. Smart-grid electricity allocation via strip packing with slicing. In WADS, pages 25-36, 2013. Google Scholar
  2. Susanne Albers. Energy-efficient algorithms. Commun. ACM, 53(5):86-96, 2010. Google Scholar
  3. Yossi Azar. On-line load balancing. In Online Algorithms, pages 178-195, 1998. Google Scholar
  4. Nikhil Bansal, Tracy Kimbrel, and Kirk Pruhs. Speed scaling to manage energy and temperature. J. ACM, 54(1), 2007. Google Scholar
  5. Paul C. Bell and Prudence W. H. Wong. Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines. J. Comb. Optim., 29(4):739-749, 2015. Google Scholar
  6. Mihai Burcea, Wing-Kai Hon, Hsiang-Hsuan Liu, Prudence W. H. Wong, and David K. Y. Yau. Scheduling for electricity cost in smart grid. In COCOA, pages 306-317, 2013. Google Scholar
  7. Chen Chen, K. G. Nagananda, Gang Xiong, Shalinee Kishore, and Lawrence V. Snyder. A communication-based appliance scheduling scheme for consumer-premise energy management systems. IEEE Trans. Smart Grid, 4(1):56-65, 2013. Google Scholar
  8. Lin Chen, Nicole Megow, and Kevin Schewior. An O(log m)-competitive algorithm for online machine minimization. In SODA, pages 155-163, 2016. Google Scholar
  9. Mark Cieliebak, Thomas Erlebach, Fabian Hennecke, Birgitta Weber, and Peter Widmayer. Scheduling with release times and deadlines on a minimum number of machines. In IFIP TCS, pages 209-222, 2004. Google Scholar
  10. Marijana Živić Djurović, Aleksandar Milačić, and Marko Kršulja. A simplified model of quadratic cost function for thermal generators. In DAAAM, pages 25-28, 2012. Google Scholar
  11. Kan Fang, Nelson A. Uhan, Fu Zhao, and John W. Sutherland. Scheduling on a single machine under time-of-use electricity tariffs. Annals OR, 238(1-2):199-227, 2016. Google Scholar
  12. Xin Feng, Yinfeng Xu, and Feifeng Zheng. Online scheduling for electricity cost in smart grid. In COCOA, pages 783-793, 2015. Google Scholar
  13. Delbert Fulkerson and Oliver Gross. Incidence matrices and interval graphs. Pacific Journal of Mathematics, 15(3):835-855, 1965. Google Scholar
  14. Rudolf Halin. Some remarks on interval graphs. Combinatorica, 2(3):297-304, 1982. Google Scholar
  15. Katherine Hamilton and Neel Gulhar. Taking demand response to the next level. IEEE Power and Energy Mag., 8(3):60-65, 2010. Google Scholar
  16. Klaus Jansen, Felix Land, and Kati Land. Bounding the running time of algorithms for scheduling and packing problems. In WADS, pages 439-450, 2013. Google Scholar
  17. Iordanis Koutsopoulos and Leandros Tassiulas. Control and optimization meet the smart power grid: Scheduling of power demands for optimal energy management. In Proc. e-Energy, pages 41-50, 2011. Google Scholar
  18. Fu-Hong Liu, Hsiang-Hsuan Liu, and Prudence W. H. Wong. Optimal nonpreemptive scheduling in a smart grid model. CoRR, abs/1602.06659, 2016. Google Scholar
  19. Thillainathan Logenthiran, Dipti Srinivasan, and Tan Shun. Demand side management in smart grid using heuristic optimization. IEEE Trans. Smart Grid, 3(3):1244-1252, 2012. Google Scholar
  20. T. Lui, W. Stirling, and H. Marcy. Get smart. IEEE Power &Energy Mag., 8(3):66-78, 2010. Google Scholar
  21. Sabita Maharjan, Quanyan Zhu, Yan Zhang, Stein Gjessing, and Tamer Basar. Dependable demand response management in the smart grid: A stackelberg game approach. IEEE Trans. Smart Grid, 4(1):120-132, 2013. Google Scholar
  22. Gilbert Masters. Renewable and efficient electric power systems. John Wiley &Sons, 2013. Google Scholar
  23. Barna Saha. Renting a cloud. In FSTTCS, pages 437-448, 2013. Google Scholar
  24. Sergio Salinas, Ming Li, and Pan Li. Multi-objective optimal energy consumption scheduling in smart grids. IEEE Trans. Smart Grid, 4(1):341-348, 2013. Google Scholar
  25. US Department of Energy. The Smart Grid: An Introduction. http://www.oe.energy.gov/SmartGridIntroduction.htm, 2009.
  26. F. Frances Yao, Alan J. Demers, and Scott Shenker. A scheduling model for reduced CPU energy. In FOCS, pages 374-382, 1995. Google Scholar
  27. Sean Yaw and Brendan Mumey. An exact algorithm for non-preemptive peak demand job scheduling. In COCOA, pages 3-12, 2014. Google Scholar
  28. Zpryme Research &Consulting. Power systems of the future: The case for energy storage, distributed generation, and microgrids, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact