On the complexity of minimizing the number of late jobs in unit time open shop

DOI10.1016/S0166-218X(99)00202-4zbMath0971.90030MaRDI QIDQ1962026

Svetlana A. Kravchenko

Publication date: 30 January 2000

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

zbMATH Keywords

complexityunary NP-hardunit time open shop

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (9)

Minimizing the weighted number of tardy jobs on multiple machines: a review ⋮ Scheduling jobs with equal processing times and time windows on identical parallel machines ⋮ The complexity of mean flow time scheduling problems with release times ⋮ Branch less, cut more and minimize the number of late equal-length jobs on identical machines ⋮ On minimizing the weighted number of late jobs in unit execution time open-shops. ⋮ Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity ⋮ Parallel machine problems with equal processing times: a survey ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ On scheduling cycle shops: Classification, complexity and approximation

Cites Work

• On complexity of minimizing weighted number of late jobs in unit time open shops
• Open shop problems with unit time operations
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

This page was built for publication: On the complexity of minimizing the number of late jobs in unit time open shop