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

Limitations of Johnson’s rule

· If more than two machines involves then this rule can be applied only if it satisfies any one of the conditions as said above.

· This rule is applicable only when sequence of machines is in same order.

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
• What makes scheduling problems hard?

Table of Contents

© 2006 Kumaravel & Project Team

Modified Johnson’s Rule for n x m JSSP

For the n jobs and m machines JSSP as shown below.

Job	Processing time
	Machine 1	Machine 2	…	Machine k	…	Machine m
J1	T11	T12	…	T1k	…	T1m
J2	T21	T22	…	T2k	…	T2m
.	.	.	…	.	…	.
Ji	Ti1	Ti2	…	Tik	…	Tim
.	.	.	…	.	…	.
Jn	Tn1	Tn2	…	Tnk	…	Tnm

Table:JSSP (n x m) Modified Johnson's Rule

If any one of the conditions below:

· Min (T_i1) ≥ Max (T_ik)

· Min (T_im) ≥ Max (T_ik)

Where i = 1, …, n and k = 2, …,(m-1)

is satisfied, then Johnson’s algorithm can be extended in following way.

Create a hypothetical problem with two machines and n jobs as shown below and objective is to obtain optimal sequence for this. Later, the make-span is to be determined for the optimal sequence by using the data of original problem as above.

Job	Processing time
	Machine A	Machine B
J1	T11 + ∑T1k	∑T1k + T1m
J2	T21 + ∑T2k	∑T2k + T2m
.	.	.
Ji	Ti1 + ∑Tik	∑Tik + Tim
.	.	.
Jn	Tn1 + ∑Tnk	∑Tnk + Tnm

Table: Hypothetical Problem of Modified Johnson's Rule

Where i = 1, …, n and k = 2, …,(m-1)

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
• Limitations of Johnson’s Rule
• What makes scheduling problems hard?

Table of Contents

© 2006 Kumaravel & Project Team

Illustration for Johnson’s rule

Consider the nx2 JSSP as shown below, using the Johnson’s rule obtain the optimal sequence which will minimize the make-span. Also determine the make-span.

Job	Processing time
	Machine 1	Machine 2
J1	4	6
J2	12	10
J3	14	10
J4	8	12
J5	18	6
J6	16	8

Table:Illustration JSSP (6x2) for Johnson’s Rule

The working of the Johnson’s algorithm is as summarized as below.

Stage	Minimum T­ik	Unscheduled Jobs	Partial sequence
1	T11 = 4	1,2,3,4,5,6	1 X X X X X
2	T52 = 6	2,3,4,5,6	1 X X X X 5
3	T41 = T62 = 8	2,3,4,6	1 4 X X X 5
4	T62 = 8	2,3,6	1 4 X X 6 5
5	T22 = T32 = 12	2,3	1 4 2 X 6 5
6	T32 = 12	3	1 4 2 3 6 5

Table:Working of Johnson's Algorithm

Explanation for the specific stage 3 and 5 where the tie exists

· In stage 3, tie occurs between the J₄ and J₆ in different machines and J₄ is on Machine 1 and hence it is first assigned

· In stage 5, tie occurs between the J₂ and J₃ in same machines and giving the priority to J₂, it is first assigned.

Thus the optimal solution is 1-4-2-3-6-5. Then make-span is dogged as below:

Job	Processing Time				Ideal Time
	Machine 1		Machine 2		Machine 1	Machine 2
	In	Out	In	Out
J1	0	4	4	10	0	4
J4	4	12	12	24	0	2
J2	12	24	24	34	0	0
J3	24	38	38	50	0	4
J6	38	54	54	62	0	4
J5	54	72	72	78	6	10

Table:Elapse Time Table for Each Machine of Given Job Sequence

Related Posts:

• JOB SHOP SCHEDULING
• Description of Job Shop Scheduling
• Assumptions in static JSSP
• Johnson’s Rule
• Algorithm of Johnson’s Rule
• Modified Johnson’s Rule for n x m JSSP
• Limitations of Johnson’s Rule
• What makes scheduling problems hard?

Table of Contents

© 2006 Kumaravel & Project Team