What makes JSSP hard?

As said earlier, JSSP is a class of combinational optimization problems known as NP-Hard one.

In computational complexity theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H, such that for every decision problem L in NP there exists a polynomial-time many-one reduction to H, written L ≤p H. Informally, this class can be described as containing the decision problems that are at least as hard as any problem in NP. This intuition is supported by the fact that if we can find an algorithm A that solves one of these problems H in polynomial time, we can construct a polynomial time algorithm for any problem L in NP by first performing the reduction from L to H and then running the algorithm A. So, formally, a language L is NP-hard if for every L' in NP, L' ≤p L. If it is also the case that L is in NP, then L is called NP-complete. The notion of NP-hardness plays an important role in the discussion about the relationship between the complexity classes P and NP. The class NP-hard can be understood as the class of problems that are NP-complete or harder. A common mistake is to think that the "NP" in "NP-hard" stands for "non-polynomial". Although it is widely suspected that there are no polynomial-time algorithms for these problems, this has never been proved.†

References:

†NP-hard - Wikipedia, the free encyclopedia, last modified 01:43, 18 February 2006, http://en.wikipedia.org/wiki/NP hard

Related Posts:

• JOB SHOP SCHEDULING
• Description of Job Shop Scheduling
• Assumptions in static JSSP
• Johnson’s Rule
• Algorithm of Johnson’s Rule
• Illustration for Johnson’s rule
• Modified Johnson’s Rule for n x m JSSP
• Limitations of Johnson’s Rule

Table of Contents

© 2006 Kumaravel & Project Team