A sequencing problem deals with finding the optimum order in which a number
of jobs (tasks) should be processed on a number of machines (resources), so as to minimise a
chosen criterion — usually the total elapsed time required to complete all jobs.
Real-Life Applications
Machine shop: 5 components, each going through lathe → milling → drilling.
Hospital OT: 6 patients to be scheduled through pre-op, surgery, post-op rooms.
Compiler stages: source files going through lex, parse, codegen.
Vehicle servicing centre: wash → check → polish.
2. Assumptions of Sequencing Problems
The processing times of each job on each machine are known and constant.
Each machine can process only one job at a time.
No machine can process more than one job simultaneously; no job is processed on more than one machine simultaneously.
The order in which jobs visit the machines is identical for all jobs (the same routing).
Once started, a job is processed without preemption (no interruptions).
The time taken to move a job from one machine to another is negligible.
All jobs are independent and available at time 0.
Notation
Let \(t_{ij}\) = processing time of job \(j\) on machine \(i\) (or, equivalently, machine \(M_i\)).
The objective is to find the sequence (permutation of jobs) that minimises the makespan — time from start of the first job on the first machine until the last job finishes on the last machine.
3. n Jobs on 2 Machines — Johnson's Algorithm
Each job must be processed first on machine M₁ then on M₂. Let \(t_{1j}\) and \(t_{2j}\) be the processing times of job \(j\) on M₁ and M₂.
Johnson's Algorithm
List all jobs with their times on M₁ and M₂.
Find the smallest processing time across all \(t_{1j}\) and \(t_{2j}\) (the entire table).
If the minimum is on M₁ (a \(t_{1j}\) value), schedule that job as early as possible (next available position at the start).
If the minimum is on M₂ (a \(t_{2j}\) value), schedule that job as late as possible (next available position at the end).
Remove the scheduled job from the list and repeat with the reduced list.
If a tie occurs (the minimum appears multiple times), break it arbitrarily; both choices yield optimum.
After all jobs are placed in the sequence, compute the schedule:
Computing Total Elapsed Time
For each job in sequence position \(k\):
M₁ finish time = (sum of M₁ times up to and including job \(k\)).
M₂ start time = max(M₁ finish of same job, M₂ finish of previous job).
M₂ finish time = M₂ start time + \(t_{2j}\).
Total elapsed time = M₂ finish time of the last job.
Idle time on M₂ = M₂ start time of first job + sum of gaps between M₂ activities.
Idle time on M₁ = Total elapsed time − (sum of M₁ processing times).
EXAMPLE 1 — Five Jobs on 2 Machines
Times:
Job
M₁
M₂
A
5
2
B
1
6
C
9
7
D
3
8
E
10
4
Smallest = 1 (job B, on M₁) → schedule B first. Sequence so far: B __ __ __ __.
From remaining {A, C, D, E}, smallest is 2 (job A, on M₂) → schedule A last. Sequence: B __ __ __ A.
From {C, D, E}, smallest is 3 (job D, on M₁) → schedule D next from start. Sequence: B D __ __ A.
From {C, E}, smallest is 4 (job E, on M₂) → schedule E next from end. Sequence: B D __ E A.
Only C left → fills middle. Final sequence: B D C E A.
Schedule:
Job
M₁ in
M₁ out
M₂ in
M₂ out
B
0
1
1
7
D
1
4
7
15
C
4
13
15
22
E
13
23
23
27
A
23
28
28
30
Total elapsed time = 30 hours.
Idle time on M₂ = 1 (initial) + 0 + 0 + 1 + 1 = 3 hours.
Idle time on M₁ = 30 − (5+1+9+3+10) = 30 − 28 = 2 hours.
Fig 3.1 — Gantt chart of the optimal sequence. Each colour is one job; a job's M₂ bar can
only start after both its own M₁ bar and the previous job's M₂ bar finish. The whole schedule ends at
30 hours, with the grey gaps showing M₂ idle time (3 h in total, 2 h on M₁).
EXAMPLE 2 — 4 Jobs
Times:
Job
M₁
M₂
1
4
5
2
9
6
3
8
2
4
6
3
Smallest = 2 (job 3, on M₂) → schedule 3 last. Sequence: __ __ __ 3.
Next smallest = 3 (job 4, on M₂) → schedule 4 second-last. Sequence: __ __ 4 3.
Next = 4 (job 1, on M₁) → schedule 1 first. Sequence: 1 __ 4 3.
Only job 2 left → middle. Final: 1 2 4 3.
Compute total elapsed time (left as exercise) ≈ 29.
4. n Jobs on 3 Machines
Each job goes through M₁ → M₂ → M₃. Let \(t_{1j}, t_{2j}, t_{3j}\) be the times.
Special Case — Reducible to 2 Machines
Johnson's procedure can be applied directly to a 3-machine problem provided at least one of the following holds:
min(\(t_{1j}\)) ≥ max(\(t_{2j}\)) — minimum on M₁ is at least the maximum on M₂.
min(\(t_{3j}\)) ≥ max(\(t_{2j}\)) — minimum on M₃ is at least the maximum on M₂.
If either condition holds, define two "pseudo-machines":
Apply Johnson's algorithm to \(G_j\) vs \(H_j\) (as if it were a 2-machine problem). The resulting sequence is optimal for the original 3-machine problem.
If Neither Condition Holds
The algorithm gives a near-optimum but not guaranteed optimum. Heuristic methods or exact branch-and-bound is needed for guarantee.
Computing Total Time
Same as 2-machine case but with one extra column. For each job in sequence:
M₃ in = max(M₂ out of same job, M₃ out of previous job).
EXAMPLE 1 — Three machines, four jobs
Times:
Job
M₁
M₂
M₃
A
8
5
4
B
10
6
9
C
6
2
8
D
7
3
6
Check: min(\(t_{1j}\)) = 6, max(\(t_{2j}\)) = 6 — condition (min M₁ ≥ max M₂) holds with equality ⇒ Johnson applies.
Pseudo-machines:
Job
G = M₁+M₂
H = M₂+M₃
A
13
9
B
16
15
C
8
10
D
10
9
Apply Johnson on G, H. Smallest = 8 (job C, G) → C first. Next 9 (job A and D, H) → A or D last (tie). Pick D last; then A second-last; B remains middle.
Sequence: C B A D.
Compute total elapsed time by following the three-machine schedule.
EXAMPLE 2
If max(M₂) is moderate but min(M₃) is large, the second condition often holds. For example, M₁ = 5, 4, 3; M₂ = 2, 1, 3; M₃ = 7, 8, 6. max(M₂) = 3; min(M₃) = 6 ≥ 3 ✓. Apply Johnson on (M₁+M₂, M₂+M₃).
5. n Jobs on m Machines (General Case)
For \(m \ge 3\) machines, the general problem of minimising the total elapsed time is NP-hard: no algorithm is known that is guaranteed to find the optimum in polynomial time. Johnson's reduction in Section 4 covers only the special three-machine case in which the middle machine is dominated.
Heuristic Extension of Johnson's Algorithm
If for all \(j = 2, 3, \ldots, m - 1\): min(\(t_{1j}\)) ≥ max(\(t_{kj}\)) for \(k = 2, \ldots, m - 1\), OR similarly for the last machine, then we can reduce by:
This includes both the time before the machine starts (waiting for upstream machines) and any gaps between consecutive jobs.
Detailed Idle Time
Initial idle time: time from t = 0 until the machine starts processing its first job.
Intermediate idle times: gaps between consecutive jobs on the same machine.
Final idle time: usually 0 for the last machine; otherwise time from finishing the last job on that machine until the makespan ends.
EXAMPLE
From the 5-job, 2-machine example earlier:
M₁ processes B (0–1), D (1–4), C (4–13), E (13–23), A (23–28). Idle on M₁ from 28 to 30 = 2 hours.
M₂ idle 0–1 (waiting for B), then continuous until job E starts at 23 (gap 22–23 = 1), then continuous until A at 28 (gap 27–28 = 1). Total M₂ idle = 1 + 1 + 1 = 3 hours.
7. Two Jobs on m Machines (Graphical Method)
This sub-problem considers only 2 jobs, each having its own order of machines (not necessarily the same). Solved graphically on a (job 1 time × job 2 time) plot — but is outside the scope of most undergraduate syllabi.
Key Take-aways
Sequencing minimises total elapsed time (makespan) for n jobs on m machines.
Johnson's algorithm exactly solves the 2-machine case in \(O(n \log n)\).
For 3 machines, Johnson applies if \(\min t_{1j} \ge \max t_{2j}\) or \(\min t_{3j} \ge \max t_{2j}\).
For 3 or more machines (outside Johnson's special case), the problem is NP-hard; heuristics like Palmer, CDS, NEH are used.
Idle time on a machine = total elapsed time − sum of its processing times.
Assumptions: deterministic times, no preemption, no machine breakdown, common job routing.