Jump to content

Talk:Uniform-machines scheduling

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

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)[reply]

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)[reply]