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

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

Svetlana A. Kravchenko

Publication date: 30 January 2000

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

zbMATH Keywords

job-shoppseudo-polynomial algorithm\(NP\)-hard problem

Mathematics Subject Classification ID

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

Related Items (5)

Minimizing the weighted number of tardy jobs on multiple machines: a review ⋮ 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 ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ 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

This page was built for publication: Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem