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

DOI10.1016/S0377-2217(96)00249-4zbMath0920.90072OpenAlexW1970923666MaRDI QIDQ1280122

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

NP-hardnessmean flow timestrongly NP-completedifferent ready datestwo-machine preemptive openshop system

Mathematics Subject Classification ID

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

Related Items (2)

Scheduling two-machine preemptive open shops to minimize total completion time ⋮ Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity

Cites Work

• Unnamed Item
• On the complexity of preemptive openshop scheduling problems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

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