An Efficient PTAS for Parallel Machine Scheduling with Capacity Constraints
From MaRDI portal
Publication:2958349
DOI10.1007/978-3-319-48749-6_44zbMath1487.90279OpenAlexW2541841001MaRDI QIDQ2958349
Lin Chen, Wen-Chang Luo, Guo-Chuan Zhang, Klaus Jansen
Publication date: 1 February 2017
Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-48749-6_44
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)
Related Items (5)
EPTAS for the dual of splittable bin packing with cardinality constraint ⋮ EPTAS for parallel identical machine scheduling with time restrictions ⋮ Unnamed Item ⋮ Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments ⋮ Dividing splittable goods evenly and with limited fragmentation
Cites Work
- A 3/2-approximation algorithm for \(k_i\)-partitioning
- Lower bounds and heuristic algorithms for the \(k_i\)-partitioning problem
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Approximation schemes for scheduling on parallel machines
- The \(k\)-partitioning problem
- A tight bound for 3-partitioning
- Carathéodory bounds for integer cones
- An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
- A comment on scheduling two parallel machines with capacity constraints
- Scheduling Jobs on Identical and Uniform Processors Revisited
- Minkowski's Convex Body Theorem and Integer Programming
- Approximating Scheduling Machines with Capacity Constraints
- An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
- Unnamed Item
This page was built for publication: An Efficient PTAS for Parallel Machine Scheduling with Capacity Constraints
