Dual techniques for scheduling on a machine with varying speed

DOI10.1007/978-3-642-39206-1_63MaRDI QIDQ5326607zbMATH OpenOpenAlexWikidataFDO

Authors 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

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

Abstract: We study scheduling problems on a machine with varying speed. Assuming a known speed function we ask for a cost-efficient scheduling solution. Our main result is a PTAS for minimizing the total weighted completion time in this setting. This also implies a PTAS for the closely related problem of scheduling to minimize generalized global cost functions. The key to our results is a re-interpretation of the problem within the well-known two-dimensional Gantt chart: instead of the standard approach of scheduling in the {em time-dimension}, we construct scheduling solutions in the weight-dimension. We also consider a dynamic problem variant in which deciding upon the speed is part of the scheduling problem and we are interested in the tradeoff between scheduling cost and speed-scaling cost, which is typically the energy consumption. We observe that the optimal order is independent of the energy consumption and that the problem can be reduced to the setting where the speed of the machine is fixed, and thus admits a PTAS. Furthermore, we provide an FPTAS for the NP-hard problem variant in which the machine can run only on a fixed number of discrete speeds. Finally, we show how our results can be used to obtain a~$(2+eps)$-approximation for scheduling preemptive jobs with release dates on multiple identical parallel machines.

Recommendations

• Dual techniques for scheduling on a machine with varying speed
• Optimal algorithms and a PTAS for cost-aware scheduling
• Scheduling on a single processor with variable speed
• Continuous speed scaling with variability: a simple and direct approach
• Scheduling Multiple Variable-Speed Machines

Cited in

(17)

• Splitting versus setup trade-offs for scheduling to minimize weighted completion time
• The TV advertisements scheduling problem
• 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
• The local-global conjecture for scheduling with non-linear cost
• 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
• Dual techniques for scheduling on a machine with varying speed
• Scheduling Multiple Variable-Speed Machines
• Scheduling under dynamic speed-scaling for minimizing weighted completion time and energy consumption
• Continuous speed scaling with variability: a simple and direct approach
• A primal-dual approximation algorithm for Min-sum single-machine scheduling problems
• Robust Appointment Scheduling with Heterogeneous Costs
• Competitive mechanisms for energy-efficient cloud computing

This page was built for publication: Dual techniques for scheduling on a machine with varying speed

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