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