Question

Find the sequence that minimizes the total elapsed time to complete the following jobs in the order AB. Find the total elapsed time and idle time for machine B : \[ \begin{array}{|c|c|c|c|c|c|c|c|} \hline \mathbf{Jobs} & I & II & III & IV & V & VI & VII \\ \hline \mathbf{Machine\ A} & 7 & 16 & 19 & 10 & 14 & 15 & 5 \\ \hline \mathbf{Machine\ B} & 12 & 14 & 14 & 10 & 16 & 5 & 7 \\ \hline \end{array} \]

Hint:

Johnson's rule is simple: find the smallest time in the table. If it's on the first machine, schedule that job as early as possible. If it's on the second machine, schedule it as late as possible. Cross off the job and repeat.

Answer 1

We use Johnson's algorithm to find the optimal sequence. The minimum processing time is 5, for Job VI on Machine B and Job VII on Machine A. Job VII goes first, Job VI goes last. Sequence: [VII, , , , , , VI]. The next smallest time is 7 for Job I on Machine A. It goes next. Sequence: [VII, I, , , , , VI]. The next smallest is 10 for Job IV on both machines. We schedule it from Machine A's side. Sequence: [VII, I, IV, , , , VI]. The next smallest is 14 for V on A, and II and III on B. We schedule V from A's side, and II and III from B's side. After tie-breaking, final sequence is: \[ \textbf{VII - I - IV - V - III - II - VI} \]