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. (A_i) ≥ Max. (B_i)

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

Max. (B_i) ≤ Min. (C_i)

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_i= A_i + B_i
H_i= B_i + C_i

Where G_i & H_i 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	A_i	B_i	C_i
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. (A_i) = 3, Max. (B_i) = 6 and Min. (C_i) = 6. Since the condition of Max. (B_i) ≤ Min. (C_i) is satisfied, the problem can be solved by the above procedure. The processing times for the new problem are given below.

Item	G_i= A_i + B_i	H_i= B_i + C_i
1	8	10
2	14	14
3	11	14
4	8	10
5	9	13

The optimal sequence is

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 (A_i)	Sewing (B_i)	Pressing (C_i)
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_i= A_i + B_i	H_i= B_i + C_i
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.

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.