Scheduling under dynamic speed-scaling for minimizing weighted completion time and energy consumption

DOI10.1016/J.DAM.2014.08.001MaRDI QIDQ499333zbMATH OpenOpenAlexFDO

Authors Christoph Dürr, Łukasz Jeż, Oscar C. Vásquez

Publication date 30 September 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.11297

zbMATH Keywords

energy managementmechanism designoptimizationquality of servicescheduling

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Abstract: Since a few years there is an increasing interest in minimizing the energy consumption of computing systems. However in a shared computing system, users want to optimize their experienced quality of service, at the price of a high energy consumption. In this work, we address the problem of optimizing and designing mechanisms for a linear combination of weighted completion time and energy consumption on a single machine with dynamic speed-scaling. We show that minimizing linear combination reduces to a unit speed scheduling problem under a polynomial penalty function. In the mechanism design setting, we define a cost share mechanism and studied its properties, showing that it is truthful and the overcharging of total cost share is bounded by a constant.

Recommendations

• A fast algorithm for multiprocessor speed-scaling problem minimizing completion time and energy consumption
• Speed scaling on parallel processors
• Dual techniques for scheduling on a machine with varying speed

Cites work

• Dual techniques for scheduling on a machine with varying speed
• Energy-efficient algorithms for flow time minimization
• Getting the best response for your erg
• scientific article; zbMATH DE number 1306870 (Why is no real title available?)
• Improved bounds for speed scaling in devices obeying the cube-root rule
• Non-clairvoyant Speed Scaling for Weighted Flow Time
• Optimal Allocation of Public Goods: A Solution to the "Free Rider" Problem
• Speed scaling to manage energy and temperature

Cited in

(8)

• Discrete-continuous scheduling to minimize the makespan for power processing rates of jobs
• Minimizing the number of machines with limited workload capacity for scheduling jobs with interval constraints
• A novel approach to subgraph selection with multiple weights on arcs
• Online speed scaling based on active job count to minimize flow plus energy
• The local-global conjecture for scheduling with non-linear cost
• On Submodular Search and Machine Scheduling
• Exploring a resolution method based on an evolutionary game-theoretical model for minimizing the machines with limited workload capacity and interval constraints
• Competitive mechanisms for energy-efficient cloud computing

This page was built for publication: Scheduling under dynamic speed-scaling for minimizing weighted completion time and energy consumption

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q499333)