Minimizing the number of tardy jobs with precedence constraints and agreeable due dates

DOI10.1016/S0166-218X(96)00043-1zbMath0872.90051OpenAlexW2147721188MaRDI QIDQ5961612

George Steiner

Publication date: 25 February 1997

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

due datesprecedence constraintsminimum weight hitting set problemnumber of tardy jobspolynomial time solutionstrongly NP-hard

Mathematics Subject Classification ID

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

Related Items

A survey of single machine scheduling to minimize weighted number of tardy jobs, Review of properties of different precedence graphs for scheduling problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimizing the number of tardy jobs in single machine sequencing
• Finding the largest suborder of fixed width
• Survey of scheduling research involving due date determination decisions
• Complexity results for scheduling chains on a single machine
• A decomposition theorem for partially ordered sets
• Linear-Time Algorithms for Scheduling on Parallel Processors
• Scheduling Tasks with Nonuniform Deadlines on Two Processors
• A Solvable Case of the One-Machine Scheduling Problem with Ready and Due Times
• Computational Complexity of Some Maximum Average Weight Problems with Precedence Constraints
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs