Dual Techniques for Scheduling on a Machine with Varying Speed

DOI10.1007/978-3-642-39206-1_63zbMath1336.90040arXiv1211.6216OpenAlexW1547437929WikidataQ57399748 ScholiaQ57399748MaRDI QIDQ5326607

Nicole Megow, José Verschae

Publication date: 6 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Related Items (15)

Dual Techniques for Scheduling on a Machine with Varying Speed ⋮ The local-global conjecture for scheduling with non-linear cost ⋮ Mechanism design for aggregating energy consumption and quality of service in speed scaling scheduling ⋮ Efficient computation of optimal energy and fractional weighted flow trade-off schedules ⋮ On the Complexity of Speed Scaling ⋮ Optimal Algorithms and a PTAS for Cost-Aware Scheduling ⋮ Splitting versus setup trade-offs for scheduling to minimize weighted completion time ⋮ The TV advertisements scheduling problem ⋮ Robust Appointment Scheduling with Heterogeneous Costs ⋮ Scheduling under dynamic speed-scaling for minimizing weighted completion time and energy consumption ⋮ How unsplittable-flow-covering helps scheduling with job-dependent cost functions ⋮ On the complexity of the single machine scheduling problem minimizing total weighted delay penalty ⋮ A polynomial-time approximation scheme for the airplane refueling problem ⋮ For the airplane refueling problem local precedence implies global precedence ⋮ A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems

This page was built for publication: Dual Techniques for Scheduling on a Machine with Varying Speed