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.
Ai = Processing time for ith job on machine A
Bi = 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.
The best technique for determining an optimal sequence was developed by Johnson & Bellman, which is discussed below.
The next section concentrates on how to calculate the total elapsed time.