Dual Techniques for Scheduling on a Machine with Varying Speed

DOI10.1137/16M105589XzbMath1391.90293WikidataQ57399709 ScholiaQ57399709MaRDI QIDQ3174696

Nicole Megow, José Verschae

Publication date: 18 July 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

schedulingpower managementapproximation algorithmsspeed scalinggeneralized MIN-sum cost functionsnonavailability periods

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items

An Optimal Control Framework for Online Job Scheduling with General Cost Functions, On Submodular Search and Machine Scheduling, Optimal algorithms for scheduling under time-of-use tariffs, Speed-robust scheduling. Sand, bricks, and rocks, Submodular Maximization with Uncertain Knapsack Capacity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
• Preemptive scheduling with availability constraints to minimize total weighted completion times
• Scheduling with limited machine availability
• Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints
• Approximation Techniques for Average Completion Time Scheduling
• Universal Sequencing on an Unreliable Machine
• Increasing Speed Scheduling and Flow Scheduling
• Speed Scaling for Weighted Flow Time
• Non-clairvoyant Speed Scaling for Weighted Flow Time
• A Survey on Approximation Algorithms for Scheduling with Machine Unavailability
• Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler
• On the Performance of Smith’s Rule in Single-Machine Scheduling with Nonlinear Cost
• The Geometry of Scheduling
• Algorithm Theory - SWAT 2004
• Dual Techniques for Scheduling on a Machine with Varying Speed
• A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
• Energy-Efficient Algorithms for Flow Time Minimization