Non-approximability of precedence-constrained sequencing to minimize setups.

DOI10.1016/j.dam.2003.08.006zbMath1077.68037OpenAlexW1999659630MaRDI QIDQ1421479

Craig A. Tovey

Publication date: 26 January 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2003.08.006

zbMATH Keywords

SchedulingComputational complexityApproximabilitySetupPrecedence constraint

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

A note on the precedence-constrained class sequencing problem, An exact dynamic programming algorithm for the precedence-constrained class sequencing problem, A survey of scheduling problems with setup times or costs

Cites Work

• Unnamed Item
• NP-complete scheduling problems
• A Simplified Anomaly and Reduction for Precedence Constrained Multiprocessor Scheduling
• Optimal Sequencing of Two Equivalent Processors