Minimizing Total Tardiness on a Single Machine with Precedence Constraints

DOI10.1287/IJOC.2.4.346zbMATH Open0757.90035OpenAlexW2135728788MaRDI QIDQ4025912FDOQ4025912

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

zbMATH Keywords

single machineNP-hardpolynomial-time algorithmminimizing total tardinesstree-structured precedence constraintsunit-processing-time jobs

Mathematics Subject Classification ID

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

Cited In (12)

• Technical Note—There are No Undiscovered Priority Index Sequencing Rules for Minimizing Total Delay Costs
• Scheduling with bully selfish jobs
• A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• Precedence theorems and dynamic programming for the single-machine weighted tardiness problem
• MINIMIZING TOTAL TARDINESS FOR SINGLE MACHINE SEQUENCING
• On the complexity of generalized due date scheduling problems
• New Precedence Theorems for One-Machine Weighted Tardiness
• Integrality Property in Preemptive Parallel Machine Scheduling
• Polyhedral results for position-based scheduling of chains on a single machine
• Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
• On scheduling cycle shops: Classification, complexity and approximation

This page was built for publication: Minimizing Total Tardiness on a Single Machine with Precedence Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4025912)