nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.08.2013

Online algorithms for maximizing weighted throughput of unit jobs with temperature constraints

verfasst von: Martin Birks, Daniel Cole, Stanley P. Y. Fung, Huichao Xue

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2013

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We consider a temperature-aware online deadline scheduling model. The objective is to schedule a number of unit jobs, with release dates, deadlines, weights and heat contributions, to maximize the weighted throughput subject to a temperature threshold. We first give an optimally competitive randomized algorithm. Then we give a constant competitive randomized algorithm that allows a tradeoff between the maximum heat contribution of jobs and the competitiveness. Finally we consider the multiple processor case and give several tight upper and lower bounds.

Vorheriger Artikel Online algorithms for 1-space bounded multi dimensional bin packing and hypercube packing

Nächster Artikel The k-Canadian Travelers Problem with communication

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 "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

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

Albers S (2010) Energy efficient algorithms. Commun ACM 53(5):86–96 MathSciNetCrossRef

Andelman N, Mansour Y, Zhu A (2003) Competitive queueing policies for QoS switches. In: Proceedings of 14th ACM-SIAM symposium on discrete algorithms, pp 761–770

Awerbuch B, Bartal Y, Fiat A, Rosen A (1994) Competitive non-preemptive call control. In: Proceedings of 5th ACM-SIAM symposium on discrete algorithms, pp 312–320

Bansal N, Kimbrel T, Pruhs K (2007) Dynamic speed scaling to manage energy and temperature. J ACM 54:1 MathSciNetMATHCrossRef

Birks M, Fung SPY (2010) Temperature aware online scheduling with a low cooling factor. In: Proceedings of 7th annual conference on theory and applications of models of computation. Lecture notes in computer science, vol 6106, pp 105–116 CrossRef

Borodin A, Ran E-Y (1998) Online computation and competitive analysis. Cambridge University Press, New York MATH

Chin FYL, Chrobak M, Fung SPY, Jawor W, Sgall J, Tichý T (2006) Online competitive algorithms for maximizing weighted throughput of unit jobs. J Discrete Algorithms 4(2):255–276 MathSciNetMATHCrossRef

Chin FYL, Fung SPY (2003) Online scheduling with partial job values: Does timesharing or randomization help? Algorithmica 37(3):149–164 MathSciNetMATHCrossRef

Chrobak M, Dürr C, Hurand M, Robert J (2008) Algorithms for temperature-aware task scheduling in microprocessor systems. In: Proceedings of 4th international conference on algorithmic aspects in information and management, pp 120–130 CrossRef

Coskun A, Rosing T, Whisnant K (2007) Temperature aware task scheduling in MPSoCs. In: Proc conference on design, automation and test in Europe, pp 1659–1664

Devadas V, Li F, Aydin H (2010) Competitive analysis of online real-time scheduling algorithms under hard energy constraint. Real-Time Syst 46:88–120 MATHCrossRef

Englert M, Westermann M (2007) Considering suppressed packets improves buffer management in QoS switches. In: Proceedings of 18th ACM-SIAM symposium on discrete algorithms, pp 209–218

Goldwasser MH (2010) A survey of buffer management policies for packet switches. SIGACT News 45(1):100–128 CrossRef

Pruhs K, Uthaisombut P, Woeginger G (2008) Getting the best response for your erg. ACM Trans Algorithms 4:3 MathSciNetCrossRef

Yang J, Zhou X, Chrobak M, Zhango Y, Jin L (2008) Dynamic thermal management through task scheduling. In: IEEE international symposium on performance analysis of systems and software, pp 191–201

Yao AC-C (1977) Probabilistic computations: Toward a unified measure of complexity. In: Proceedings of 18th IEEE symposium on foundations of computer science, pp 222–227

Titel: Online algorithms for maximizing weighted throughput of unit jobs with temperature constraints
verfasst von: Martin Birks
Daniel Cole
Stanley P. Y. Fung
Huichao Xue
Publikationsdatum: 01.08.2013
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 2/2013
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-012-9543-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2013

Optimal job insertion in the no-wait job shop

Tight approximation bounds for combinatorial frugal coverage algorithms

L(2,1)-labelings of the edge-path-replacement of a graph

The k-Canadian Travelers Problem with communication

The nearest neighbor Spearman footrule distance for bucket, interval, and partial orders

A tight analysis of Brown-Baker-Katseff sequences for online strip packing