Minimizing Total Tardiness on a Single Machine with Precedence Constraints
From MaRDI portal
Publication:4025912
DOI10.1287/ijoc.2.4.346zbMath0757.90035MaRDI QIDQ4025912
Joseph Y.-T. Leung, Gilbert H. Young
Publication date: 18 February 1993
Published in: ORSA Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/ijoc.2.4.346
single machine; polynomial-time algorithm; NP-hard; minimizing total tardiness; tree-structured precedence constraints; unit-processing-time jobs
90C60: Abstract computational complexity for mathematical programming problems
90B35: Deterministic scheduling theory in operations research
Related Items
Scheduling with bully selfish jobs, On the complexity of generalized due date scheduling problems, Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity, On scheduling cycle shops: Classification, complexity and approximation, A survey on how the structure of precedence constraints may change the complexity class of scheduling problems, Polyhedral results for position-based scheduling of chains on a single machine, Integrality Property in Preemptive Parallel Machine Scheduling