Approximation algorithms for the multiprocessor scheduling with submodular penalties

DOI10.1007/s11590-021-01724-1zbMath1475.90021OpenAlexW3139513104MaRDI QIDQ2047204

Xiaofei Liu, Weidong Li

Publication date: 19 August 2021

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-021-01724-1

zbMATH Keywords

multiprocessor schedulingapproximation algorithmsubmodular penalties

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (6)

Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties ⋮ Approximation algorithms for the minimum power cover problem with submodular/linear penalties ⋮ Algorithms for single machine scheduling problem with release dates and submodular penalties ⋮ An approximation algorithm for the \(H\)-prize-collecting power cover problem ⋮ Polynomial-time approximation schemes for a class of integrated network design and scheduling problems with parallel identical machines ⋮ On-line single machine scheduling with release dates and submodular rejection penalties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for parallel machine scheduling with release dates and job rejection
• Improved approximation algorithms for the facility location problems with linear/submodular penalties
• Approximation algorithms for scheduling unrelated parallel machines
• Penalty cost constrained identical parallel machine scheduling problem
• Analysis of a linear programming heuristic for scheduling unrelated parallel machines
• Approximation schemes for scheduling on parallel machines
• A push-relabel framework for submodular function minimization and applications to parametric optimization
• Approximation algorithms for precedence-constrained identical machine scheduling with rejection
• Approximation algorithms for the ring loading problem with penalty cost
• A unified framework for designing EPTAS for load balancing on parallel machines
• A primal-dual approximation algorithm for the facility location problem with submodular penalties
• Submodular functions and optimization.
• An improved heuristic for parallel machine scheduling with rejection
• Multiprocessor Scheduling with Rejection
• An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies

This page was built for publication: Approximation algorithms for the multiprocessor scheduling with submodular penalties