Processing n Jobs Through Three Machines : Sequencing Problem
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)
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
Gi = Ai + Bi
Hi = 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 | Gi = Ai + Bi | Hi = 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 | Gi = Ai + Bi | Hi = 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.
