USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

SEQUENCING JOBS THROUGH TWO MACHINES

SEQUENCING JOBS THROUGH TWO MACHINES

The sequencing algorithm for this case was developed by Johnson and is called Johnson’s Algorithm. In this situation n jobs must be processed through machines M1 and M2. The processing time of all the n jobs or M1 and M2 is known and it is required to find the sequence, which minimizes the time to complete all the jobs.

Johnson’s algorithm is based on the following assumptions:

(i)                           There are only two machines and the processing of all the jobs is done on both the machines in the i.e. first on M1 and then on M2.

(ii)                        All jobs arrive at the same time (static arrival pattern) have no priority for job completion.

Johnson’s Algorithm involves following steps :-

  1. 1.   List operation time for each job on machine M1 and M2.
  2. 2.   Select the shortest operation or processing time in the above list.
  3. 3.   If minimum processing time is on M1, place the corresponding job first in the sequence. If it is on M2, place the corresponding job last in the sequence. In case of tie in shortest processing time, it can be broken arbitrarily.
  4. 4.   Eliminate the jobs which have already been sequenced as result of step 3.
  5. 5.   Repeat step 2 and 3 until all the jobs are sequenced.

Example 7.3 Six jobs are to be sequenced which require processing on two machines M1 and M2. The processing time in minutes for each of the six jobs on machines M1 and M2 is given below. All the jobs have to be processed in sequence M1, M2. Determine the optimum sequence for processing the jobs so that total time of all the jobs is minimum. Use Johnson’s Algorithm.

Jobs

1

2

3

4

5

6

Processing Time Machine M1

30

30

60

20

35

45

Machine M2

45

15

40

25

30

70

 

Sol. Step I. Operation time or processing time for each jobs on M \ and M2 is provided in the question.

Step II. The shortest processing time is 15 for job 2 on M2.

Step III. As the minimum processing time is on M2, job 2 has to be kept last as follows.

2

Step IV. We ignore job 2 and find out the shortest processing time of rest of jobs. Now the least processing time is 20 minutes on machine M1 for job 4. Since it on M1, it is to be placed first as follows.

4

2

 

The next minimum processing time is 30 minutes for job 5 on M2 and Job 1 on M1. So job 5 will be placed at the end. Job 1 will be sequenced earlier 8S shown below.

4

1

5

2

 

The next minimum processing time is 40 minutes for Job 3 on M2, hence it is sequenced as follows.

4

1

3

5

2

 

Job 6 has to be sequenced in the gap or vacant space. The complete sequencing of the jobs is as follows.

4

1

6

3

5

2

 

The minimum time for six jobs on machine M1 and M2 can be shown with the help of a Gantt chart as shown below. 

The above figure shows idle time for M1 (30 minutes) after the last job (2) has been processed. Idle time for M2 is 20 minutes before job 4 is started and 5 minutes before processing 6 and finishing job 1. The percentage utilization of M1 = 250 – 30/250 = 88% M2 = 250 – 25/250 = 90%.

 

Example 7.4. A book-binder has one printing press, one binding machine and manuscript of seven different books. The time required for performing printing and binding operations for different books are shown below:

 

 

 

Book

Printing Time (days)

Binding Time (days)

1

20

25

2

90

60

3

80

75

4

20

30

5

120

90

6

15

35

7

65

50

 

 

 

Decide the optimum sequence of processing of books in order to minimize total time.

 

Sol. Step I. Minimum time is 15 days on printing press (M1) for job 6 so it will be sequenced earlier as shown.

 

6

 

 

 

Step II. Now book I and 4 have the least time of 20 days on printing press (M1) so these two books will be sequenced as

 

6

1

4

 

 

 

Step III. After eliminating jobs 6, 1 and 4, the least time is for job 7 on binding machine (M2) so it will be placed last in the sequence.

 

6

1

4

7

 

Step IV. Now book 2 has least time of 60 on M2. Hence it will be placed at the end.

 

6

1

4

7

 

Step V. Book 3 has the least time of 75 days on M2 so it will be placed as below.

 

6

1

4

3

2

7

 

Step VI. Job 5 will be placed in the vacant place.

 

6

1

4

5

3

2

7

 

Step VII. Total processing time can be calculated as follows.

 

Optimum sequence of jobs (books)

Printing

Binding

Idle time for Binding

In

Out

In

Out

6

0

15

15

50

15

1

15

35

50

75

4

35

55

75

105

5

55

175

175

265

70

3

175

255

265

340

2

255

345

345

405

5

7

345

410

410

460

5

 

 

 

Total idle time

 

Printing = (460 – 410) = 50 days as the printing last job (7) is finished on 410 days but binding finishes only after 460 days, so printing machine is idle for 50 days.

 

Binding = 15 + 70 + 5 + 5 = 95 days

 

Example 7.5. A manufacturing company has 5 different jobs on two machines M1 and M2. The processing time for each of the jobs on M1 and M2 is given below. Decide the optimal sequence of processing of the jobs in order to minimize total time.

 

 

 

Job No.

Processing Time

M1

M2

1

8

6

2

12

7

3

5

11

4

3

9

5

6

14

 

 

 

Sol. The shortest processing time is 3 on M1 for job 4 so it will be sequenced as follows.

 

4

 

 

Next is job 3 with time 5 and M1, hence job 3 will be sequenced as

 

4

3

 

 

 

Next minimum time is for jobs Ion M2 this will be sequenced last

 

4

3

1

 

 

 

After eliminating jobs 4, 3 and 1, the next with minimum time is job 5 on M1 so it will be placed as

 

4

3

5

1

 

 

 

Now job 2 will be sequenced in the vacant space,

 

4

3

5

2

1