Note on “Parallel Machine Scheduling with Batch Setup Times”
Operations Research · 1998 · Volume 46 · Issue 3
Abstract
Cheng and Chen (1994) use a high-multiplicity encoding scheme to prove binary NP -hardness of a scheduling problem. From this they infer a similar result for a well-known, more general problem. We explain that, although their initial proof is correct, their inference about the more general problem is not.
Keywords
Analysis of algorithms, computational complexity, NP-hardness, production/scheduling, parallel machine scheduling
Enable JavaScript for citation tools and additional paper interactions.