Non-Approximability Results for Scheduling Problems with Minsum Criteria

DOI10.1287/ijoc.13.2.157.10520zbMath1238.90066OpenAlexW1969964129MaRDI 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

schedulingunrelated parallel machinesAPX-hardnessopen shop flow shop

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)

Related Items (10)

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

This page was built for publication: Non-Approximability Results for Scheduling Problems with Minsum Criteria