Talk:Uniform-machines scheduling
Latest comment: 12 years ago by Skagedal in topic NP-Completeness
 | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||
| ||||||||||||||||||
NP-Completeness edit
Does a paper exists thar demonstrates that particular case ofschedling is indeed NP-Complete ? I'm looking for one ;-) French-jamian 21:02, 9 September 2007 (UTC)
- I bet you're still looking for an answer, some five years later. :) This article gives the following two references to support the fact that the Multiprocessor Scheduling Problem is NP-hard:
- M. R. Garey and D. S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness (Freeman, New York, 1997).
- S. Mertens, Comput. Sci. Eng. 4, 31 (2002).
- If I understand correctly, this article shouldn't say "NP-complete" since that only applies to decision (yes/no) problems. /skagedaltalk 08:10, 26 January 2012 (UTC)