Performance guarantees of local search for minsum scheduling problems

DOI10.1007/S10107-020-01571-5zbMATH Open1485.90040OpenAlexW3089626505MaRDI QIDQ2118098FDOQ2118098

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

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

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

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)

Cites Work

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

Cited In (4)

• Local Search Performance Guarantees for Restricted Related Parallel Machine Scheduling
• Title not available (Why is that?)
• Title not available (Why is that?)
• Performance guarantees of local search for multiprocessor scheduling

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)