USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

n-JOBS 3 MACHINE CASE

 

N-JOBS 3 MACHINE CASE

Johnson’s algorithm’ which we have just applied can be extended and made use of n jobs 3 machine case, if the following conditions hold good:-

a)     Maximum processing, time for a job on machine M1 is greater than or equal to processing time for the same job.

or

b)    Minimum processing time for a job on machine M3 is greater than or equal to maximum processing time for a job on machine M2.

The following assumptions are made :-

a)     Every job is processed on all the three machines M1, M2 and M3 first processed on M1 then on M2 and then on M3.

b)    The passing of jobs is not permitted.

c)     Processing time for each job on the machine M1, M2 and M3 are known.

In this procedure two dummy machines M1’ and M3’ are assumed in such a manner that the processing time of jobs on these machines can be calculated as

Processing time of jobs on M1‘ = Processing time (M1 + M2)

Processing time of a job on M2‘ = Processing time (M2 + M1)

After this Johnson’s algorithm is applied on M1‘ and M2’ to find out the optimal sequencing of jobs.

Example 7.6. In a manufacturing process three operations have to be performed on machines M1, M2 and M3 in order M1, M2 and M3. Find out-the optimum sequencing when the processing time for four jobs on three machines is as follows:-

Sol. Step I. As the minimum processing time for job 2 on M1 > maximum processing time for job 2 on M2, Johnson’s algorithm can be applied to this problem.

Step II. Let us combine the processing time of M1 & M2 and M3 to form two dummy machines M1’ and M2’. This is shown in the matrix below.

Job

M1

M2

1

11 (3+8)

21 (8+13)

2

18 (12+6)

20 (6+4)

3

9 (5+4)

13 (4+9)

4

8 (2+6)

18 (6+12)

 

Step III. Apply Johnson’s algorithm. Minimum time of 8 occurs for job 4 on M’1 hence it is sequenced first.

4

3

1

 

The next minimum time is for job 3 on M’1 so it is sequenced next to job 4. Next is job 1 and so on. So the optimal sequencing is

4

3

1

2

 

Example 7.7. Six jobs have to be processed on machines M1, M2 and M3 in order M1, M2 and M3. Time taken by each job on these machines is given below, Determine the sequence so as to minimize the processing time.

Job

M1

M2

M3

1

12

7

3

2

8

10

4

3

7

9

2

4

11

6

5

5

10

10

3

6

5

5

4

 

Sol. Step 1. As the minimum processing time for jobs 1 and 4 on M1 is greater than on M2, Johnson’s algorithm can be applied.

Step II. Combine the processing time of M1 and M2 and M3 and develop new matrix for machine M1‘ and M2‘ as follows.

Job

M’1

M’2

1

19 (12+7)

10 (7+3)

2

18 (8+10)

14 (10+4)

3

16 (7+9)

11 (9+2)

4

17 (11+6)

11 (6+5)

5

20 (10+10)

13 (10+3)

6

10 (5+5)

9 (5+4)

 

Step III. Use Johnson’s algorithm and sequence the jobs Minimum processing time of 9 occurs for job 6 on M’1 so it will be sequenced the last.

6

 

Next minimum processing time of 10 occurs for job 1 on M2 so job 1 will be sequenced next to job 6.

1

6

 

Next minimum processing time is 11 for jobs 3 and 4 on machine M’2 so these will be sequenced as shown.

3

4

1

6

 

Next minimum is 13 for jobs 5 on machine M2 and after that job 2 has minimum processing time of 14 on M2‘, hence the sequencing is as follows.

2

5

3

4

1

6

 

‘n’ Jobs ‘m’ Machine Case

Let there be ‘n’ jobs 1,2,3, …. n and ‘m’ machine M1 ,M2, M3 …. m. The order of processing is M1, M2, M3 …. m and no passing is permitted. The processing time for the machine is shown below:

Job

M1

M2

M3

m

1

a1

b1

c1

M1

2

a2

b2

c2

M2

3

a3

b3

c3

M3

:

:

:

:

:

:

:

:

:

:

n

an

bn

cn

Mn

 

If the following conditions are used, we can replace ‘m’ machines by an equivalent of two machines problem.

(a)             Min ai ≥  max of M2, M3 …. (m – 1)

(b)             Min m ≥  max M2, M3 …. (m – 1)

when M1‘=a+bi+ci+…. +(m-1) i

M2‘ = bi + ci +…. + (m – 1) i + mi

Example 7.8. Determine the optimal sequence of performing 5 jobs on 4 machines. The machines used in the order M1, M2, M3 and M4 and the processing time is given below

Job

M1

M2

M3

M4

1

8

3

4

7

2

9

2

6

5

3

10

6

6

8

4

12

4

1

9

5

7

5

2

3

 

Sol. Step 1. Let us find out if any of the conditions stipulated is satisfied or not.

Condition 1. Min ai ≥  max of M2 and M3.

Min ai >7

Max bi > 6

Max ci=6

Hence the condition is satisfied.

Step II. Let us form the matrix of new processing time by creating two fictitious machine M1’ and M2’.

Job

M1’=ai+bi+ci

M2’=bi+ci+di

1

15 (8+3+4)

14 (3+4+7)

2

17 (9+2+6)

13 (2+6+5)

3

22 (10+6+6)

20 (6+6+8)

4

17 (12+4+1)

14 (4+1+9)

5

14 (7+5+2)

10 (5+2+3)

 

Step III. Now solve 5 jobs 2 machine problem.

Minimum time of processing is for job 5 on machine M2‘ so it will be sequenced last.

5

 

Next minimum time is 13 for jobs 2 on machine M’2 so it will be sequenced as shown.

2

5

 

Next minimum time is for jobs 1 and 4 on machine M’2 so it will be sequenced as shown.

1

4

2

5

 

Next minimum time is 20 for job 3 on machine M2‘.

3

1

4

2

5

 

Example 7.9. Solve the following sequencing problem when passing off is not allowed.

 

A

B

C

D

I

15

5

4

15

II

12

2

10

12

III

16

3

5

16

IV

17

3

4

17

 

Sol. Let us find out if one of the two conditions is satisfied.

Step 1. min ai ≥  max bi and ci

or min di ≥  max bi and ci

Here both the conditions are satisfied.

Step II. The problem can be converted into 4 jobs 2 machines problem by introducing two fictitious machines M1‘ and M2‘ as follows.

Job

M1

M2

I

24 (15+5+4)

24 (5+4+15)

II

24 (12+2+10)

24 (2+10+12)

III

24 (16+3+5)

24(3+5+16)

IV

24 (17+3+4)

24 (3+4+17)

 

Where M1’=ai+bi+ci

M2’=bi+ci+di

Since all the processing times are equal, the jobs can be sequenced in any manner and all sequences are optimal and will give the same minimum time.

Total time can be worked out from the table below.

Job

Machine A

Machine B

Machine C

Machine D

In

Out

In

Out

In

Out

In

Out

I

0

15

15

20

20

24

24

39

II

15

27

27

29

29

39

39

51

III

27

43

43

46

46

51

51

67

IV

43

60

60

63

63

67

67

84

 

Total time = 84 hours

Idle time Machine A = 84 – 60 = 24 hours

Machine B = 15 + 7 + 14 + 14 + (84 _ 63)

=1 5 + 7 + 14 + 14 + 21 = 71 hours

Machine C = 20 + 5 + 7 + 12 + (84 – 67) = 61 hours

Machine D = 24 hours

Example 7.10 Four Jobs 1.2.3 and 4 are to be processed on each of the five machines M1, M2, M3, M4 and M5 in the order M1, M2, M3, M4, M5. Determine total minimum elapsed time if no passing off is allowed. Also find out the idle time of each of the machines. Processing time are given in the matrix below.

Job

Machine

M1

M2

M3

M4

M5

1

8

4

6

3

9

2

7

6

4

5

10

3

6

5

3

2

8

4

9

2

1

4

6

Sol. Step I. Find out if the condition minimum ei ≥  max bi, ci and di is satisfied.

Job

Machine

M1

M2

M3

M4

M5

1

8

4

6

3

9

2

7

6

4

5

10

3

6

5

3

2

8

4

9

2

1

4

6

Min 6

Max 6

Max 6

Max 5

Min 6

 

This condition is satisfied hence we can convert the problem into four jobs and two ficticious machines M1’ and M2’.

Step II.

Job

M1

M2

1

21 (8+4+6+3)

22 (4+6+3+9)

2

22 (7+6+4+5)

25 (6+4+5+10)

3

16 (6+5+3+2)

18 (5+3+2+8)

4

16 (9+2+1+4)

13 (2+1+4+6)

Step III. The optimal sequence can be determined as minimum of processing time of 13 occurs on M2‘ for job 4 it will be processed last. Next minimum time is for job 3, on machine M1‘ so it will be processed earliest. Next shortest time is for machine 1 on M1’ so it will be sequenced next to job 3 and so on.

3

1

2

4

Step IV. Total time can be calculated with the help of the matrix shown below.

Job

M1

M2

M3

M4

M5

In

Out

In

Out

In

Out

In

Out

In

Out

1

0

8

8

12

12

18

18

21

21

30

2

8

15

15

21

21

25

25

30

30

40

3

15

21

21

26

26

29

29

32

40

48

4

21

30

30

32

30

31

32

36

48

54

 

Hence total minimum elapsed time is 51

Idle time for machines M1 = 24 hours

M2 = 3 + 4 + 22 = 29

M3 = 3 + 1 + 1 + 23 = 28

M4 =4 + 18 = 22