Sequencing Problems: Basic Concepts

A sequencing problem asks a different question from the assignment problem. Here we have several jobs, each of which must pass through the same set of machines in the same technological order, and we must decide the order (sequence) in which the jobs are fed to the machines so that the total time to finish all jobs (the total elapsed time) — and the machines' idle time — is as small as possible.

The number of jobs is fixed, and so is the route each job takes; the only thing we control is who goes first, second, third. With $n$ jobs there are $n!$ possible orders, so — as with assignment — we need a rule rather than brute enforce. The great simplification is Johnson's rule, which gives the optimal order for the standard two-machine (and, under a condition, three-machine) cases.

Key terms.

• Processing time $t_{ij}$ — the time job $i$ takes on machine $j$.
• Idle time (of a machine) — time for which a machine stands waiting, with no job to process, between the start and finish of the whole schedule.
• Total elapsed time — the time from the moment the first job starts on the first machine to the moment the last job finishes on the last machine. This is what we minimise.
• In-time / out-time — the clock reading when a job enters and leaves a machine; tabulating these is how we read off elapsed and idle times.

Standing assumptions of the sequencing model.

1. Each job is processed through every machine, in the same order (e.g. Machine A then Machine B then Machine C).
2. A machine handles only one job at a time, and once a job is started on a machine it runs to completion (no interruption). …