Note on “Parallel Machine Scheduling with Batch Setup Times”

Scott Webster
Additional contact information
Scott Webster: Syracuse University, Syracuse, New York

Operations Research, 1998, vol. 46, issue 3, 423-423

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 (search for similar items in EconPapers)
Date: 1998
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.3.423 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:46:y:1998:i:3:p:423-423

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().