Energy-efficient scheduling and routing via randomized rounding

DOI10.1007/s10951-016-0500-2zbMath1406.90053OpenAlexW2241183059MaRDI QIDQ1617291

Giorgio Lucarelli, Evripidis Bampis, Dimitrios Letsios, Alexander V. Kononov, M. I. Sviridenko

Publication date: 7 November 2018

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2013/4392/

zbMATH Keywords

schedulingapproximationrandomized roundingconfiguration linear programenergy-aware

Mathematics Subject Classification ID

Linear programming (90C05) Transportation, logistics and supply chain management (90B06) Approximation methods and heuristics in mathematical programming (90C59) Stochastic scheduling theory in operations research (90B36) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Environmental economics (natural resource models, harvesting, pollution, etc.) (91B76)

Related Items

Approximate schedules for non-migratory parallel jobs in speed-scaled multiprocessor systems ⋮ Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion ⋮ Approximation algorithms for energy-efficient scheduling of parallel jobs ⋮ Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints ⋮ Minimizing energy on homogeneous processors with shared memory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey of offline algorithms for energy minimization under deadline constraints
• Speed scaling on parallel processors
• From preemptive to non-preemptive speed-scaling scheduling
• Properties of optimal schedules in preemptive shop scheduling
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Geometric algorithms and combinatorial optimization.
• Green scheduling, flows and matchings
• On multi-processor speed scaling with migration
• The bell is ringing in speed-scaled multiprocessor scheduling
• Online Primal-Dual for Non-linear Optimization with Applications to Speed Scaling
• Non-preemptive Speed Scaling
• Speed-Scaling with No Preemptions
• On the Distribution of the Number of Successes in Independent Trials
• Minimum-Cost Network Design with (Dis)economies of Scale
• Scheduling Parallel DAG Jobs Online to Minimize Average Flow Time
• Speed Scaling on Parallel Processors with Migration
• Santa Claus Schedules Jobs on Unrelated Machines
• Hallucination Helps: Energy Efficient Virtual Circuit Routing