Power-aware scheduling for makespan and flow
From MaRDI portal
Abstract: We consider offline scheduling algorithms that incorporate speed scaling to address the bicriteria problem of minimizing energy consumption and a scheduling metric. For makespan, we give linear-time algorithms to compute all non-dominated solutions for the general uniprocessor problem and for the multiprocessor problem when every job requires the same amount of work. We also show that the multiprocessor problem becomes NP-hard when jobs can require different amounts of work. For total flow, we show that the optimal flow corresponding to a particular energy budget cannot be exactly computed on a machine supporting arithmetic and the extraction of roots. This hardness result holds even when scheduling equal-work jobs on a uniprocessor. We do, however, extend previous work by Pruhs et al. to give an arbitrarily-good approximation for scheduling equal-work jobs on a multiprocessor.
Recommendations
Cites work
- A survey of scheduling with controllable processing times
- Algorithm Theory - SWAT 2004
- Algorithms and Data Structures
- An efficient approximation algorithm for minimizing makespan on uniformly related machines.
- Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds
- Approximation and Online Algorithms
- Approximation schemes for scheduling on parallel machines
- Energy-Efficient Algorithms for Flow Time Minimization
- scientific article; zbMATH DE number 53165 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1306870 (Why is no real title available?)
- scientific article; zbMATH DE number 1022658 (Why is no real title available?)
- On Adaptive Transmission for Energy Efficiency in Wireless Data Networks
- Parallel machine scheduling with a convex resource consumption function
- Planning and Scheduling in Manufacturing and Services
- Pre-emptive scheduling problems with controllable processing times
- Single machine scheduling with controllable release and processing parameters
- Speed scaling for weighted flow time
- Speed scaling on parallel processors
- The algebraic degree of geometric optimization problems
Cited in
(24)- Discrete-continuous scheduling to minimize the makespan for power processing rates of jobs
- Flow shop for dual CPUs in dynamic voltage scaling
- Scheduling to minimize energy and flow time in broadcast scheduling
- Minimizing total completion time in multiprocessor job systems with energy constraint
- Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion
- Models and algorithms for energy-efficient scheduling with immediate start of jobs
- Green scheduling, flows and matchings
- Optimizing resource speed for two-stage real-time tasks
- On a certain class of power- and energy-related scheduling problems
- Improved multi-processor scheduling for flow time and energy
- Scheduling to minimize gaps and power consumption
- Rate-adaptive weighted fair queueing for energy-aware scheduling
- Speed scaling for maximum lateness
- Convergecast and broadcast by power-aware mobile agents
- Application of submodular optimization to single machine scheduling with controllable processing times subject to release dates and deadlines
- Energy-efficient multiprocessor scheduling for flow time and makespan
- Approximation algorithms for energy, reliability, and makespan optimization problems
- Speed scaling on parallel processors
- Green scheduling, flows and matchings
- Algorithm Theory - SWAT 2004
- Energy-Efficient Algorithms for Flow Time Minimization
- Assigning real-time tasks to heterogeneous processors by applying ant colony optimization
- An adaptive genetic algorithm with optimal recombination for scheduling problems with energy resource
- Power-aware scheduling of preemptable jobs on identical parallel processors to minimize makespan
This page was built for publication: Power-aware scheduling for makespan and flow
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1041350)
