Performance guarantees of local search for minsum scheduling problems

DOI10.1007/S10107-020-01571-5MaRDI QIDQ2118098zbMATHOpenAlexFDO

Authors José R. Correa, Felipe T. Muñoz

Publication date 22 March 2022

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10107-020-01571-5

zbMATH Keywords

local searchparallel machinestotal weighted completion timeperformance guarantee

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• Performance guarantee of the jump neighborhood for scheduling jobs on uniformly related machines
• scientific article; zbMATH DE number 1757968
• Performance guarantees of local search for multiprocessor scheduling
• Local Search Performance Guarantees for Restricted Related Parallel Machine Scheduling
• Performance guarantees of jump neighborhoods on restricted related parallel machines

Cites work

• scientific article; zbMATH DE number 3550182 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2146482 (Why is no real title available?)
• A PTAS for minimizing the total weighted completion time on identical parallel machines.
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• A Survey of Approximation Results for Local Search Algorithms
• A linear time approximation algorithm for multiprocessor scheduling
• A multi-exchange neighborhood for minimum makespan parallel machine scheduling problems
• A survey of very large-scale neighborhood search techniques
• Approximation algorithms for scheduling unrelated parallel machines
• Approximation schemes for scheduling on uniformly related and identical parallel machines
• Bounds for List Schedules on Uniform Processors
• Decentralized utilitarian mechanisms for scheduling games
• Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Exponential size neighborhoods for makespan minimization scheduling
• Improving local search heuristics for some scheduling problems. II
• Local Search Performance Guarantees for Restricted Related Parallel Machine Scheduling
• Optimal Coordination Mechanisms for Multi-job Scheduling Games
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Performance guarantees of jump neighborhoods on restricted related parallel machines
• Performance guarantees of local search for multiprocessor scheduling
• Quality of move-optimal schedules for minimizing total weighted completion time
• Scheduling independent tasks to reduce mean finishing time
• Scheduling. Theory, algorithms, and systems
• Technical Note—Minimizing Average Flow Time with Parallel Machines
• Theoretical aspects of local search.
• Tight bounds for selfish and greedy load balancing
• Worst-case equilibria
• `` Strong NP-Completeness Results

Cited in

(7)

• Performance guarantees for scheduling algorithms under perturbed machine speeds
• scientific article; zbMATH DE number 4121743 (Why is no real title available?)
• Local Search Performance Guarantees for Restricted Related Parallel Machine Scheduling
• Performance guarantees of local search for multiprocessor scheduling
• Smoothed performance guarantees for local search
• Performance guarantees for scheduling algorithms under perturbed machine speeds
• scientific article; zbMATH DE number 1757968 (Why is no real title available?)

This page was built for publication: Performance guarantees of local search for minsum scheduling problems

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