Performance guarantees for scheduling algorithms under perturbed machine speeds

DOI10.1016/J.DAM.2014.05.041MaRDI QIDQ496438zbMATH OpenOpenAlexFDO

Authors Michael Etscheid

Publication date 21 September 2015

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

Full work available at URL https://doi.org/10.1016/j.dam.2014.05.041

zbMATH Keywords

local searchschedulingperformance guaranteessmoothed analysis

Mathematics Subject Classification ID

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

Recommendations

• Performance guarantees for scheduling algorithms under perturbed machine speeds
• Smoothed performance guarantees for local search
• Smoothed Performance Guarantees for Local Search
• Performance guarantees of local search for minsum scheduling problems
• Speed-robust scheduling. Sand, bricks, and rocks

Cites work

• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Approximation algorithms for scheduling unrelated parallel machines
• Bounds for List Schedules on Uniform Processors
• Local Search Performance Guarantees for Restricted Related Parallel Machine Scheduling
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Performance guarantees of local search for multiprocessor scheduling
• Probability Inequalities for Sums of Bounded Random Variables
• Random knapsack in expected polynomial time
• Smoothed analysis of algorithms
• Smoothed analysis. Motivation and discrete models
• Tight bounds for worst-case equilibria
• Worst-case Nash equilibria in restricted routing

Cited in

(7)

• Speed-robust scheduling. Sand, bricks, and rocks
• Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
• Smoothed performance guarantees for local search
• Performance guarantee of the jump neighborhood for scheduling jobs on uniformly related machines
• Performance guarantees for scheduling algorithms under perturbed machine speeds
• Smoothed analysis of local search algorithms
• On the Robustness of Graham’s Algorithm for Online Scheduling

This page was built for publication: Performance guarantees for scheduling algorithms under perturbed machine speeds

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