Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem

DOI10.1016/S0166-218X(99)00165-1zbMath0947.90046MaRDI QIDQ1962067

Svetlana A. Kravchenko

Publication date: 30 January 2000

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

zbMATH Keywords

job-shop; pseudo-polynomial algorithm; \(NP\)-hard problem

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90B35: Deterministic scheduling theory in operations research

Related Items

Is a unit-job shop not easier than identical parallel machines?, Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity, On scheduling cycle shops: Classification, complexity and approximation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimizing maximum lateness in a two-machine unit-time job shop
• Total completion time minimization in two-machine job shops with unit-time operations
• A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem
• Is a unit-job shop not easier than identical parallel machines?
• An efficient algorithm for a job shop problem
• An Efficient Optimal Algorithm for the Two-Machines Unit-Time Jobshop Schedule-Length Problem
• Flowshop and Jobshop Schedules: Complexity and Approximation
• Computational Complexity of Discrete Optimization Problems
• Reducibility among Combinatorial Problems