Universal sequencing on an unreliable machine

DOI10.1137/110844210MaRDI QIDQ2910853zbMATH OpenOpenAlexWikidataFDO

Authors Leah Epstein, Asaf Levin, Nicole Megow, Julián Mestre, Alberto Marchetti-Spaccamela, L. Stougie, Martin Skutella

Publication date 12 September 2012

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://research.vu.nl/ws/files/3067170/287206.pdf

zbMATH Keywords

machine speedmin-sum objectiveschedulingsingle machineuniversal solutionunreliable machineworst case guarantee

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)

Recommendations

• Universal sequencing on a single machine
• The list scheduling algorithm for scheduling unreliable jobs on two parallel machines
• Stochastic Scheduling on Unrelated Machines
• Optimal algorithms and a PTAS for cost-aware scheduling
• Sequencing unreliable jobs on parallel machines

Cited in

(16)

• Minimizing worst-case and average-case makespan over scenarios
• Distributionally robust appointment scheduling with moment-based ambiguity set
• The TV advertisements scheduling problem
• Speed-robust scheduling. Sand, bricks, and rocks
• Optimal algorithms for scheduling under time-of-use tariffs
• Speed-robust scheduling: sand, bricks, and rocks
• Optimal algorithms and a PTAS for cost-aware scheduling
• Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints (extended abstract)
• Dual techniques for scheduling on a machine with varying speed
• Universal sequencing on a single machine
• Submodular maximization with uncertain knapsack capacity
• Packing a knapsack of unknown capacity
• A primal-dual approximation algorithm for Min-sum single-machine scheduling problems
• Scheduling with speed predictions
• Speed-robust scheduling revisited
• Scheduling with speed predictions

This page was built for publication: Universal sequencing on an unreliable machine

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