Processing n Jobs Through Two Machines : Sequencing Models

This problem refers to the following situation:

Suppose n jobs are to be processed on two machines, say A & B. Each job has to pass through the same sequence of operations in the same order, i.e., passing is not allowed.

After a job is completely processed on machine A, it is assigned to machine B. If machine B is not free at that moment, then the job enters the waiting queue. Each job from the waiting queue is assigned to machine B according to FIFO discipline. Let
A_i = Processing time for ith job on machine A
B_i = Processing time for ith job on machine B
T = Total elapsed time

The problem here is to determine the sequence in which these n jobs should be processed through A & B, so that the total elapsed time (T) is minimum.

Optimal Sequence Algorithm

The best technique for determining an optimal sequence was developed by Johnson & Bellman, which is discussed below.

Steps

1. Select the minimum processing time out of all the A_i's and B_i's. If it is A_r then do the rth job first. If it is B_s then do the sth job in last.
2. If there is a tie in selecting minimum of all the processing times, then there are following three ways to deal with such a situation:
   • If the minimum of all the processing times is A_r, which is also equal to B_s.
     That is, Min (A_i, B_i) = A_r = B_s
     Then do the rth job first and sth job in last.
   • If Min (A_i, B_i) = A_r, but A_r = A_k, i.e., there is a tie for minimum among A_i's, then select any one.
   • If Min (A_i, B_i) = B_s, but B_s = B_t, i.e., there is a tie for minimum among B_i's, then select any one.
3. Now eliminate the job which has already been assigned from further consideration, and repeat steps 1 and 2 until an optimal sequence is found.

The next section concentrates on how to calculate the total elapsed time.