Processing n Jobs Through Three Machines

When each of $n$ jobs must pass through three machines in the fixed order $M_1 \to M_2 \to M_3$, there is no simple rule in general. But if the middle machine is 'weak enough', the three-machine problem can be converted into an equivalent two-machine problem and then solved by Johnson's rule.

The conversion condition. Let $A_i, B_i, C_i$ be the times of job $i$ on $M_1, M_2, M_3$. The conversion is valid if at least one of the following holds:

In words: the smallest time on the first machine is at least the largest time on the middle machine, or the smallest time on the last machine is at least the largest on the middle machine. (If neither holds, this shortcut does not apply.)

The conversion. Define two fictitious machines $G$ and $H$ with processing times

Now treat $G$ and $H$ as a two-machine problem and apply Johnson's rule to the $(G_i, H_i)$ times to get the optimal sequence.

Reading the answer. The optimal order found from $(G, H)$ is the order to use on the real machines $M_1, M_2, M_3$. To get the total elapsed and idle times, tabulate in-/out-times across all three real machines: a job's in-time on a machine is $\max(\text{its out-time on the previous machine},\ \text{previous job's out-time on this machine})$.