Non-Approximability Results for Scheduling Problems with Minsum Criteria

DOI10.1287/ijoc.13.2.157.10520zbMath1238.90066MaRDI QIDQ2884502

Hoogeveen, J. A., Gerhard J. Woeginger, Petra Schuurman

Publication date: 30 May 2012

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/61046f7135cb561f2deaa65e562a8695088152c9

zbMATH Keywords

scheduling; unrelated parallel machines; APX-hardness; open shop flow shop

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90B35: Deterministic scheduling theory in operations research

Related Items

Static Routing in Stochastic Scheduling: Performance Guarantees and Asymptotic Optimality, Bounding the Running Time of Algorithms for Scheduling and Packing Problems, Approximability of average completion time scheduling on unrelated machines, Maximizing business value by optimal assignment of jobs to resources in grid computing, Polyhedral results for position-based scheduling of chains on a single machine, Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates, Decentralized utilitarian mechanisms for scheduling games, Unrelated Machine Scheduling with Stochastic Processing Times