Top

Journal of Scheduling

Published in:

01-08-2013

Non-preemptive speed scaling

Authors: Antonios Antoniadis, Chien-Chung Huang

Published in: Journal of Scheduling | Issue 4/2013

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We consider the following offline variant of the speed scaling problem introduced by Yao et al. We are given a set of jobs and we have a variable-speed processor to process them. The higher the processor speed, the higher the energy consumption. Each job is associated with its own release time, deadline, and processing volume. The objective is to find a feasible schedule that minimizes the energy consumption. In contrast to Yao et al., no preemption of jobs is allowed. Unlike the preemptive version that is known to be in P, the non-preemptive version of speed scaling is strongly NP-hard. In this work, we present a constant factor approximation algorithm for it. The main technical idea is to transform the problem into the unrelated machine scheduling problem with \(L_p\)-norm objective.

previous article Multi-criteria scheduling: an agent-based approach for expert knowledge integration

next article A study of single-machine scheduling problem to maximize throughput

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

Albers, S. (2010). Energy-efficient algorithms. Communications of the ACM, 53(5), 86–96.CrossRef

Azar, Y., & Epstein, A. (2005). Convex programming for scheduling unrelated parallel machines. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (pp. 331–337).

Bansal, N., Kimbrel, T., & Pruhs, K. (2007). Speed scaling to manage energy and temperature. Journal of the ACM, 54, 1–3.CrossRef

Bartal, Y., Leonardi, S., Shallom, G., & Sitters, R. (2006). On the value of preemption in scheduling. In Approximation, randomization (pp. 39–48). Springer.

Bampis, E., Letsios, D., Milis, I., & Zois, G. (2012). Speed scaling for maximum lateness. COCOON, 25–36.

Bampis, E., Lucarelli, G., & Nemparis, I. (2012). Improved approximation algorithms for the non-preemptive speed-scaling problem. In arXiv, CoRR abs/1209.6481.

Braun, O., & Schmid, G. (2003). Parallel processor scheduling with limited number of preemptions. SIAM Journal on Computing, 32, 671–680.CrossRef

Chen, J. J., Kuo, T. W., & Lu, H. I. (2005). Power-saving scheduling for weakly dynamic voltage scaling devices. In WADS (pp. 338–349). Springer.

Chuzhoy, J., & Codenotti, P. (2009). Resource minimization job scheduling. In APPROX-RANDOM (pp. 70–83). Springer.

Chuzhoy, J., Ostrovsky, R., & Rabani, Y. (2006). Approximation algorithms for the job interval selection problem and related scheduling problems. Mathematics of Operations Research, 31(4), 730–738.

Dimpsey, R. T., & Iyer, R. K. (1990). Performance degradation due to multiprogramming and system overheads in real workloads: Case study on a shared memory multiprocessor. In International Conference on Supercomputing (pp. 227–238).

Etsion, Y., Tsafrir, D., & Feitelson, D. G. (1990). Effects of clock resolution on the scheduling of interactive and soft real-time processes. In SIGMETRICS (pp. 172–183).

Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: a guide to the theory of NP-Completeness. San Francisco: W. H. Freeman.

Natarajan, C., Sharma, S., & Iyer, R. K. (1994). Measurement-based characterization of global memory and network connection, operating system and parallelization overheads: Case study on a shared memory multiprocessor. Annual International Symposium on Computer Architecture, 21, 71–80.CrossRef

Li, M., Liu, B. J., & Yao, F. F. (2006). Min-energy voltage allocation for tree-structured tasks. Journal of Combinatorial Optimization, 11, 305–319.CrossRef

Li, M., & Yao, F. F. (2005). An efficient algorithm for computing optimal discrete voltage schedules. SIAM Journal on Computing, 35, 658–671.CrossRef

Yao, F. F., Demers, A. J., & Shenker, S. (1995). A scheduling model for reduced CPU energy. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (pp. 374–382).

Title: Non-preemptive speed scaling
Authors: Antonios Antoniadis
Chien-Chung Huang
Publication date: 01-08-2013
Publisher: Springer US
Published in: Journal of Scheduling / Issue 4/2013
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-013-0312-6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 4/2013

A study of single-machine scheduling problem to maximize throughput

Guest editorial: “New trends in scheduling”

Erratum to: Minimizing total tardiness on parallel machines with preemptions

A note on reverse scheduling with maximum lateness objective

Batch sequencing and cooperation

Hierarchical scheduling strategies for parallel tasks and advance reservations in grids

Premium Partner