Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2014 | OriginalPaper | Buchkapitel

An Exact Algorithm for Non-preemptive Peak Demand Job Scheduling

verfasst von : Sean Yaw, Brendan Mumey

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Peak demand scheduling aims to schedule jobs so as to minimize the peak load in the schedule. An important application of this problem comes from scheduling power jobs in the smart grid. Currently, peaks in power demand are due to the aggregation of many jobs being scheduled in an on-demand fashion. Often these have some flexibility in their starting times which can be leveraged to lower the peak demand of a schedule. While the general version of the problem is known to be NP-hard (we observe it is even NP-hard to approximate), we provide an optimal algorithm based on dynamic programming that is fixed-parameter tractable (FPT). Simulation results using household power usage data show that peak power demand can be significantly reduced by allowing some flexibility in job execution times and applying scheduling.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Nächstes Kapitel An Asymptotic Competitive Scheme for Online Bin Packing
Fußnoten
1
While not explicitly stated in [16], the best approximation ratio achieved for the MP algorithm results from minimizing \(a + 2 + \frac{2a}{a-1}\), which occurs at \(a = \sqrt{2} + 1\) and yields an approximation ratio of \(7.82\).
 
Literatur
1.
Antoniadis, A., Huang, C.-C.: Non-preemptive speed scaling. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol. 7357, pp. 249–260. Springer, Heidelberg (2012)CrossRef
2.
3.
Bampis, E., Lucarelli, G., Nemparis, I.: Improved approximation algorithms for the non-preemptive speed-scaling problem. arXiv preprint arXiv:​1209.​6481 (2012)
4.
Bell, P., Wong, P.: Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines. J. Comb. Optim. 1–11 (2013)
5.
Chuzhoy, J., Guha, S., Khanna, S., Naor, J.: Machine minimization for scheduling jobs with interval constraints. In: Proceedings of 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 81–90. IEEE (2004)
6.
Cieliebak, M., Erlebach, T., Hennecke, F., Weber, B., Widmayer, P.: Scheduling with release times and deadlines on a minimum number of machines. In: Levy, J.J., Mayr, E., Mitchell, J. (eds.) Exploring New Frontiers of Theoretical Informatics. IFIP, vol. 155, pp. 209–222. Springer, Boston (2004)CrossRef
7.
Conejo, A.J., Morales, J.M., Baringo, L.: Real-time demand response model. IEEE Trans. Smart Grid 1(3), 236–242 (2010)CrossRef
8.
Fox, K., Im, S., Moseley, B.: Energy efficient scheduling of parallelizable jobs. In: Symposium on Discrete Algorithms, pp. 948–957 (2013)
9.
Gu, X., Chen, G., Xu, Y.: Average-case performance analysis of a 2d strip packing algorithm - NFDH. J. Comb. Optim. 9(1), 19–34 (2005)CrossRefMATHMathSciNet
10.
Kolter, J.Z., Johnson, M.J.: Redd: a public data set for energy disaggregation research. In: SustKDD Workshop on Data Mining Applications in Sustainability (2011)
11.
Koutsopoulos, I., Tassiulas, L.: Control and optimization meet the smart power grid: scheduling of power demands for optimal energy management. In: International Conference on Energy-Efficient Computing and Networking, pp. 41–50. ACM (2011)
12.
Koutsopoulos, I., Tassiulas, L.: Optimal control policies for power demand scheduling in the smart grid. IEEE J. Sel. Areas Commun. 30(6), 1049–1060 (2012)CrossRef
13.
Mohsenian-Rad, A.H., Leon-Garcia, A.: Optimal residential load control with price prediction in real-time electricity pricing environments. IEEE Trans. Smart Grid 1(2), 120–133 (2010)CrossRef
14.
Mu, Z., Li, M.: Dvs scheduling in a line or a star network of processors. J. Comb. Optim. 1–20 (2013)
15.
Ortmann, F.G., Ntene, N., van Vuuren, J.H.: New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems. Eur. J. Oper. Res. 203(2), 306–315 (2010)CrossRefMATH
16.
Tang, S., Huang, Q., Li, X.Y., Wu, D.: Smoothing the energy consumption: peak demand reduction in smart grid. In: INFOCOM, 2013 Proceedings IEEE, pp. 1133–1141, April 2013
17.
Vytelingum, P., Ramchurn, S.D., Voice, T.D., Rogers, A., Jennings, N.R.: Trading agents for the smart electricity grid. In: International Conference on Autonomous Agents and Multiagent Systems, pp. 897–904 (2010)
18.
Yao, F., Demers, A., Shenker, S.: A scheduling model for reduced CPU energy. In: Symposium on Foundations of Computer Science, pp. 374–382 (1995)
19.
Yaw, S., Mumey, B., McDonald, E., Lemke, J.: Peak demand scheduling in the smart grid. In: IEEE SmartGridComm (2014, to appear)
Metadaten
Titel
An Exact Algorithm for Non-preemptive Peak Demand Job Scheduling
verfasst von
Sean Yaw
Brendan Mumey
Copyright-Jahr
2014
Buch
Combinatorial Optimization and Applications

Print ISBN: 978-3-319-12690-6

Electronic ISBN: 978-3-319-12691-3

Copyright-Jahr: 2014

DOI
https://doi.org/10.1007/978-3-319-12691-3_1

Premium Partner

    Bildnachweise