Skip to content

n Jobs and Three Machines

This case is similar to the previous case except that instead of two machines, there are three machines. Problems falling under this category can be solved by the method developed by Johnson. Following are the two conditions of this approach:

  • The smallest processing time on machine A is greater than or equal to the greatest processing time on machine B, i.e.,

Min. (Ai) ≥ Max. (Bi)

  • The smallest processing time on machine C is greater than or equal to the greatest processing time on machine B, i.e.,

Max. (Bi) ≤ Min. (Ci)

At least one of the above two conditions must be satisfied.

If either or both of the above conditions are satisfied, then we replace the three machines by two fictitious machines G & H with corresponding processing times given by

G= Ai + Bi
H= Bi + Ci

Where Gi & Hi are the processing times for ith job on machine G and H respectively.
After calculating the new processing times, we determine the optimal sequence of jobs for the machines G & H in the usual manner.

Example 1 : Processing n Jobs Through 3 Machines

The MDH Masala company has to process five items on three machines:- A, B & C. Processing times are given in the following table:

Item Ai Bi Ci
1 4 4 6
2 9 5 9
3 8 3 11
4 6 2 8
5 3 6 7

Find the sequence that minimizes the total elapsed time.

Solution.

Here, Min. (Ai) = 3, Max. (Bi) = 6 and Min. (Ci) = 6. Since the condition of Max. (Bi) ≤ Min. (Ci) is satisfied, the problem can be solved by the above procedure. The processing times for the new problem are given below.

Item G= Ai + Bi H= Bi + Ci
1 8 10
2 14 14
3 11 14
4 8 10
5 9 13

The optimal sequence is

1 4 5 3 2

 

Item Machine A Machine B Machine C
  Time in Time out Time in Time out Time in Time out
1 0 4 4 8 8 14
4 4 10 10 12 14 22
5 10 13 13 19 22 29
3 13 21 21 24 29 40
2 21 30 30 35 40 49

Total elapsed time = 49

Idle time for machine A = 49 – 30 = 19 hours
Idle time for machine B = 4 + (10 – 8) + (13 – 12) + (21 – 19)+ (30 – 24) + (49 – 35) = 29 hours
Idle time for machine C = 8 + (14 – 14) + (22 – 22) + (29 – 29)+ (40 – 40) = 8 hours

Example 2

Shahi Export House has to process five items through three stages of production, viz, cutting, sewing & pressing. Processing times are given in the following table:

Item Cutting
(Ai)
Sewing
(Bi)
Pressing
(Ci)
1 3 3 5
2 8 4 8
3 7 2 10
4 5 1 7
5 2 5 6

Determing an order in which these items should be processed so as to minimize the total processing time.

Solution.

The processing times for the new problem are given below.

Item G= Ai + Bi H= Bi + Ci
1 6 8
2 12 12
3 9 12
4 6 8
5 7 11

Thus, the optimal sequence may be formed in any of the two ways.

1 4 5 3 2

 

4 1 5 3 2

 

Item Cutting Sewing Pressing
  Time in Time out Time in Time out Time in Time out
1 0 3 3 6 6 11
4 3 8 8 9 11 18
5 8 10 10 15 18 24
3 10 17 17 19 24 34
2 17 25 25 29 34 42

Total elapsed time = 42

Idle time for cutting process = 42 – 25 = 17 hours
Idle time for sewing process = 3 + (8 – 6) + (10 – 9) + (17 – 15)+ (25 – 19) + (42 – 29) = 27 hours.
Idle time for pressing process = 6 + (11 – 11) + (18 – 18) + (24 – 24)+ (34 – 34) = 6 hours.

2 Comments »

Leave a Reply

error: Content is protected !!
%d bloggers like this: