Question

The time required for two operations cutting and binding for 5 jobs are as follows:

Job No.	1	2	3	4	5
Cutting (min)	8	6	2	5	7
Binding (min)	8	7	7	6	4

What is the optimal makespan sequence?

1. 2-4-1-3-5
2. 3-4-2-1-5
3. 1-2-3-4-5
4. 3-5-2-4-1

Answer 1

Correct Answer - Option 2 : 3-4-2-1-5

Concept:

n - Jobs and 2 - Machines:

• There are 'n' jobs to be processed on two machines in the technological order of m₁ - m₂.
• The objective is to find out optimum job sequence that can minimize makespan or overall completion time or total elapes time or batch completion time.

Solution methodology:

"Johnson's Algorithm":

• Johnson's Algorithm can give optimum job sequences in the case of two machines only. However, the algorithm can be extended for more than two machines by means of some modifications.

 

Calculation:

Given:

Job No.	1	2	3	4	5
Cutting (min)	8	6	2	5	7
Binding (min)	8	7	7	6	4

Now,

From Johnson's Algorithm,

Use Johnson’s Algorithms solve.

 

Make a box like this & select the lowest number (say ‘2’ in this case). If the number belongs to ‘Cutting’ place it on the extreme left or else place it on the right side at the box.

3

 

Next lowest is ‘4’ on ‘Binding’, so place it in the Right

3

5

 

Next is ‘5’ on ‘Cutting’, so place it on left

3

4

5

 

Next is ‘6’ on ‘Cutting’, so place it on Left.

3

4

2

5

 

‘1’ is the only Remaining job so place it on the vacant position.

3

4

2

1

5

 

Optimum job sequence is given by

Cutting

3

4

2

1

5

Binding