Q.Define a sequencing problem. State Johnson's rule for sequencing $n$ jobs on two machines, and explain how the total elapsed time and a machine's idle time are calculated.

A sequencing problem fixes the jobs and their route and asks for the best order; Johnson's rule gives that order for two machines.

Sequencing problem. Given $n$ jobs, each of which must be processed through the same machines in the same order, a sequencing problem is the task of deciding the order in which the jobs are taken up so that the total elapsed time (and the machines' idle time) is minimised. The jobs and their machine route are fixed; only the order is a decision.

Johnson's rule (two machines $M_1$ then $M_2$). Let $A_i, B_i$ be job $i$'s times on $M_1, M_2$.

1. Find the smallest value among all $A_i$ and $B_i$.
2. If it is an $A_i$ (on $M_1$), place that job in the earliest free position of the sequence.
3. If it is a $B_i$ (on $M_2$), place that job in the latest free position.
4. Remove the scheduled job and repeat, filling positions from both ends towards the middle, until all jobs are placed.
5. Ties may be resolved either way.

Total elapsed time. Fix the order, then tabulate each job's in-time and out-time on $M_1$ and $M_2$. On $M_1$ jobs run consecutively. On $M_2$, a job starts at

The total elapsed time is the out-time of the last job on $M_2$.

Idle time. For each machine, …

Thinking a sequencing problem changes which machines a job uses — it changes only the order. Also, computing idle time as gaps 'by eye' and missing the waiting period …