Sequencing Problem : Processing n Jobs Through 2 Machines

Example 1

Suppose we have five jobs, each of which has to be processed on two machines A & B in the order AB. Processing times are given in the following table:

On small screens, use horizontal scrollbar to view full table

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

Solution.

The minimum time in the above table is 2, which corresponds to job 2 on machine A.

2

Now we eliminate job 2 from further consideration. The reduced set of processing times are as follows:

The minimum time is 3 for job 1 on machine B. Therefore, this job would be done in last. The allocation of jobs till this stage would be

2

1

After deletion of job 1, the reduced set of processing times are as follows:

Similarly, by repeating the above steps, the optimal sequence is as follows:

2

4

3

5

1

Once the optimal sequence is obtained, the minimum elapsed time may be calculated as follows:

Use horizontal scrollbar to view full table

Idle time for machine A = total elapsed time - time when the last job is out of machine A
36 - 33 = 3 hours
Idle time for machine B = Time at which the first job in a sequence finishes on machine A + {( time when the ith job starts on machine B) - (time when the (i -1)th finishes on machine B)}

Idle time for machine B = 2 + (9 - 9) + (18 - 18) + (27 - 26) + (33 - 32) = 4 hours

Example 2 : Sequencing n Jobs 2 Machines

Strong Book Binder has one printing machine, one binding machine, and the manuscripts of a number of different books. Processing times are given in the following table:

We wish to determine the order in which books should be processed on the machines, in order to minimize the total time required.

Solution.

The minimum time in the above table is 1, which corresponds to the book B on printing machine.

B

Now book B is eliminated. The reduced set of processing times are as follows:

The minimum time is 2 for book A on binding machine. Therefore, this job should be done in last. The allocation of jobs till this stage is:

B

A

The reduced set of processing times are as follows:

Similarly, by repeating the above steps, the optimal sequence is as follows:

B

D

C

E

A

Once the optimal sequence is obtained, the minimum elapsed time may be calculated as follows:

Idle time for printing process = total elapsed time - time when the last job is out of machine A
30 - 28 = 2 hours
Idle time for binding process = 1 + (7 - 7) + (15 - 15) + (23 - 22) + (28 - 27) = 3 hours