Performance Guarantees of Local Search for Multiprocessor Scheduling
From MaRDI portal
Publication:2892310
DOI10.1287/ijoc.1050.0152zbMath1241.90057OpenAlexW2143668930MaRDI QIDQ2892310
Tjark Vredeveld, Petra Schuurman
Publication date: 18 June 2012
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/d63fe8e6fed4953b37a9ee0a89acf00aebbc91ea
Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items (36)
The shortest first coordination mechanism for a scheduling game with parallel-batching machines ⋮ Exponential size neighborhoods for makespan minimization scheduling ⋮ Coordination Mechanisms for Selfish Parallel Jobs Scheduling ⋮ Efficient coordination mechanisms for unrelated machine scheduling ⋮ Scheduling selfish jobs on multidimensional parallel machines ⋮ Coordination mechanisms for parallel machine scheduling ⋮ Equilibria for two parallel links: the strong price of anarchy versus the price of anarchy ⋮ Inefficiency of Nash equilibrium for scheduling games with constrained jobs: a parametric analysis ⋮ Maximizing the minimum load: the cost of selfishness ⋮ Reducing price of anarchy of selfish task allocation with more selfishness ⋮ Smoothed performance guarantees for local search ⋮ Worst-case analysis of LPT scheduling on a small number of non-identical processors ⋮ Strategic Scheduling Games: Equilibria and Efficiency ⋮ Bounds for the Convergence Time of Local Search in Scheduling Problems ⋮ The price of anarchy on uniformly related machines revisited ⋮ The strong price of anarchy of linear bottleneck congestion games ⋮ Performance guarantees of jump neighborhoods on restricted related parallel machines ⋮ Non-clairvoyant scheduling games ⋮ Inefficiency of Nash equilibria with parallel processing policy ⋮ Approximate strong equilibria in job scheduling games with two uniformly related machines ⋮ Performance analysis of the \((1+1)\) evolutionary algorithm for the multiprocessor scheduling problem ⋮ Performance guarantees for scheduling algorithms under perturbed machine speeds ⋮ Symmetry exploitation for online machine covering with bounded migration ⋮ A coordination mechanism for a scheduling game with parallel-batching machines ⋮ The cost of selfishness for maximizing the minimum load on uniformly related machines ⋮ Inefficiency of equilibria for the machine covering game on uniform machines ⋮ Very Large-Scale Neighborhoods with Performance Guarantees for Minimizing Makespan on Parallel Machines ⋮ A Coordination Mechanism for a Scheduling Game with Uniform-Batching Machines ⋮ Decentralized utilitarian mechanisms for scheduling games ⋮ The Price of Anarchy on Uniformly Related Machines Revisited ⋮ Selfish load balancing for jobs with favorite machines ⋮ Coordination mechanisms for selfish scheduling ⋮ Coordination mechanisms for scheduling selfish jobs with favorite machines ⋮ A note on the lower bound for the price of anarchy of scheduling games on unrelated machines ⋮ Inefficiency of the Nash equilibrium for selfish machine covering on two hierarchical uniform machines ⋮ Performance guarantees of local search for minsum scheduling problems
This page was built for publication: Performance Guarantees of Local Search for Multiprocessor Scheduling
