A two-machine preemptive openshop scheduling problem: An elementary proof of NP-completeness

DOI10.1016/S0377-2217(96)00249-4MaRDI QIDQ1280122zbMATH OpenOpenAlexFDO

Authors A. A. Gladky

Publication date 27 April 1999

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0377-2217(96)00249-4

zbMATH Keywords

different ready datesmean flow timeNP-hardnessstrongly NP-completetwo-machine preemptive openshop system

Mathematics Subject Classification ID

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

Recommendations

• Scheduling two-machine preemptive open shops to minimize total completion time
• On the complexity of preemptive openshop scheduling problems
• On the complexity of preemptive open-shop scheduling problems
• scientific article; zbMATH DE number 1279216
• A note on the proof of the complexity of the little-preemptive open-shop problem
• Non-preemptive two-machine open shop scheduling with non-availability constraints
• scientific article; zbMATH DE number 5260089
• scientific article; zbMATH DE number 930117
• Polynomial-time approximation schemes for two-machine open shop scheduling with nonavailability constraints

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the complexity of preemptive openshop scheduling problems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

Cited in

(9)

• On the complexity of preemptive open-shop scheduling problems
• On the complexity of preemptive openshop scheduling problems
• Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
• Scheduling two-machine preemptive open shops to minimize total completion time
• Minimizing Mean Flow Time in Two-Machine Open Shops and Flow Shops
• The NP-completeness of the \(n/m/parallel/C_{\max}\) preemptive due-date scheduling problem
• On the open-shop problem with preemption and minimizing the average completion time
• A note on the proof of the complexity of the little-preemptive open-shop problem
• On the complexity of constructing multiprocessor little-preemptive schedules

This page was built for publication: A two-machine preemptive openshop scheduling problem: An elementary proof of NP-completeness

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