Processing n Jobs Through Two Machines

Consider $n$ jobs, each of which must be processed first on Machine 1 ($M_1$) and then on Machine 2 ($M_2$), in that order. Let $A_i$ be the time of job $i$ on $M_1$ and $B_i$ its time on $M_2$. We want the job order that minimises the total elapsed time. Johnson's rule gives it directly.

Johnson's rule (two machines).

1. Look at all the processing times ($A_i$'s and $B_i$'s together) and pick the smallest one.
2. If the smallest time is on $M_1$ (an $A_i$), schedule that job as early as possible (fill the left-most free position in the sequence).
3. If the smallest time is on $M_2$ (a $B_i$), schedule that job as late as possible (fill the right-most free position).
4. Cross out that job and repeat with the remaining jobs, working inwards from both ends, until all positions are filled.
5. Ties may be broken arbitrarily (either choice gives an optimal — possibly different — sequence with the same total time).

Reading the elapsed and idle times. Once the order is fixed, draw a table with, for each job in sequence, its in-time and out-time on $M_1$ and on $M_2$:

• On $M_1$ jobs run back-to-back: each job's in-time is the previous job's out-time.
• On $M_2$, a job can start only when it has left $M_1$ and $M_2$ is free, i.e. its $M_2$ in-time $= \max(\text{its } M_1 \text{ out-time},\ \text{previous job's } M_2 \text{ out-time})$.

The total elapsed time is the last job's out-time on $M_2$. Idle time of a machine = total elapsed time $-$ (sum of that machine's processing times).

For the optimal sequence $1,5,4,2,3$ of Worked Example 8, the in-times and out-times (in hours) on each machine work out as follows, reading the schedule job by job along the $0$–$29$ hour timeline: