Scheduling and sequencing

Scheduling and sequencing: single/parallel machine and flow/job-shop rules (SPT, EDD, CR), Johnson’s rule, Moore–Hodgson, performance measures (Cmax, Lmax, ∑Cj, tardiness), assumptions, and exam-type computations.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Scheduling and sequencing decide the order of jobs on machines so factories meet due dates, cut lead time and WIP, and use resources well. Even simple, correct rules save hours of machine idle time and reduce penalties for late delivery.

Key ideas

  • Basic terms (single-machine setting unless stated):

    • A job is a unit of work requiring processing time on one or more machines; index j.
    • A machine is a resource that can process at most one job at a time (no preemption unless stated); index i.
    • Processing time pᵢⱼ is known, deterministic time for job j on machine i (s).
    • Release date rⱼ is the earliest time job j is available (s). If not given, assume rⱼ = 0.
    • Due date dⱼ is the promised completion time (s).
    • Start time Sⱼ and completion time Cⱼ are the scheduled begin/end times of job j (s).
    • Flow time Fⱼ = Cⱼ − rⱼ (s). Time job spends in the system.
    • Waiting time Wⱼ = Fⱼ − pⱼ (s) for a single-machine job with one operation.
    • Lateness Lⱼ = Cⱼ − dⱼ (s). Can be negative (early) or positive (late).
    • Tardiness Tⱼ = max(0, Lⱼ) (s). Never negative.
    • Earliness Eⱼ = max(0, −Lⱼ) (s).
    • Makespan Cmax = maxⱼ Cⱼ (s). Time to finish all jobs in the schedule.
    • Throughput is jobs completed per unit time (1/s). In steady state, equals arrival rate under stability.
    • Utilization ρ = busy time / total time (dimensionless, 0–1) for a machine over a horizon.
    • Idle time is the time a machine is not processing due to lack of available job or blocking.
  • Environments:

    • Single-machine (1||·): all jobs on one machine.
    • Parallel machines (P, Q, R||·): identical (P), uniform speed (Q), or unrelated (R) in processing characteristics.
    • Flow shop (Fᵐ||·): m machines in same order for all jobs (M1 → M2 → … → Mm).
    • Job shop (Jᵐ||·): each job has its own route (order of machines can differ).
    • Open shop (Oᵐ||·): each job needs each machine once, in any order.
  • Objectives commonly tested:

    • Minimize ∑Cⱼ (total completion time) or average flow time.
    • Minimize Lmax (maximum lateness) or Tmax (maximum tardiness).
    • Minimize ∑Tⱼ (total tardiness) or the number of tardy jobs ∑Uⱼ, where Uⱼ = 1 if Tⱼ > 0 else 0.
    • Minimize Cmax (makespan) in flow/parallel shops.
  • Gantt charts: time-line bars for each machine showing job intervals. Read Cⱼ at bar ends; Cmax at last bar end on the last-finishing machine. For flow shops, a job’s bar on Mi cannot start before it finishes on Mi−1 and before Mi is free.

  • Dispatching/sequencing rules (deterministic, non-preemptive unless stated):

    • FCFS: first-come, first-served (by rⱼ or arrival). Simple, fair but not optimal for standard objectives.
    • SPT (Shortest Processing Time): sort by increasing pⱼ.
      • Theorem (Smith 1956, single machine): On 1||∑Cⱼ, SPT order minimizes ∑Cⱼ and hence minimizes average flow time when rⱼ = 0, no preemption.
    • WSPT (Weighted SPT/Smith’s Rule): for 1||∑wⱼ Cⱼ, sequence by non-decreasing pⱼ / wⱼ.
    • EDD (Earliest Due Date): sort by increasing dⱼ.
      • Theorem (Jackson 1955, single machine): On 1||Lmax with rⱼ = 0, EDD order minimizes Lmax.
    • Moore–Hodgson algorithm: for 1||∑Uⱼ (minimize number of tardy jobs), order by EDD, build schedule; whenever a tardy occurs, remove from the partial schedule the job with the largest pⱼ and place it in a tardy set. This yields the minimum number of tardy jobs.
    • CR (Critical Ratio): CR = (dⱼ − t_now) / remaining processing time; smaller CR has higher priority. Good for dynamic, due-date adherence.
    • Slack S = dⱼ − t_now − remaining processing time; dispatch lower slack first. S/RO distributes slack per remaining operations.
    • LPT (Longest Processing Time first): good heuristic to reduce makespan on parallel identical machines (P||Cmax).
  • Flow shop results:

    • Johnson’s rule (two-machine flow shop F2||Cmax): Given processing times (p₁ⱼ, p₂ⱼ) for each job j with the same order M1→M2, to minimize makespan:
      1. Find the smallest processing time among all remaining jobs across both machines.
      2. If it is on M1 (i = 1), schedule that job as early as possible; if on M2 (i = 2), schedule it as late as possible.
      3. Remove the job and repeat until all are placed.
      • Assumptions: deterministic times, no preemption, infinite buffer, jobs visit M1 then M2 only once, no machine can process two jobs at the same time, no passing on the same machine.
      • Statement: Johnson’s rule yields an optimal sequence minimizing Cmax for F2||Cmax under the above assumptions (proof by pairwise interchange argument showing no-crossing property).
    • Three-machine flow shop F3||Cmax: Not solvable by Johnson directly. A sufficient condition for reduction is: if minⱼ p₁ⱼ ≥ maxⱼ p₂ⱼ or minⱼ p₃ⱼ ≥ maxⱼ p₂ⱼ, define fictitious machines A and B with times p_Aⱼ = p₁ⱼ + p₂ⱼ, p_Bⱼ = p₂ⱼ + p₃ⱼ, then apply Johnson’s rule on (A,B). If neither holds, use heuristics (e.g., NEH).
    • General m-machine flow shop (m ≥ 3) for makespan is NP-hard; heuristics like NEH are used in practice (outside GATE scope generally, but good to know).
  • Job shop: finding optimal schedules is combinatorially hard even for small instances; dispatching rules (SPT, EDD, CR, S/RO) and shifting bottleneck heuristics are used. In exams, you are typically asked to build feasible schedules and compute Cmax, ∑Cⱼ, or lateness measures, not to prove optimality.

  • Preemption vs non-preemption:

    • In this topic, unless stated, assume non-preemptive. With preemption, for single machine with rⱼ, the SRPT (Shortest Remaining Processing Time) rule minimizes average flow time; this is a queuing/scheduling bridge result.
  • Laws and relations:

    • Little’s Law (steady state): L = λ · W, where L is average number in system (jobs), λ is throughput (jobs/s), W is average time in system (s). Link to scheduling: when rⱼ = 0 batch, minimizing average flow time W reduces average WIP L given a fixed throughput.
  • Real-world deviations from ideal models:

    • Sequence-dependent setups: setup time depends on job order, invalidating SPT/Johnson optimality; problem becomes harder (often NP-hard).
    • Finite buffers/blocking: in flow shops, M1 may have to wait if the buffer before M2 is full; Gantt charts must include blocking/no-wait constraints.
    • Machine breakdowns/learning curve: times are uncertain or change over time; requires reactive rescheduling and stochastic models (Queuing Theory topic).
    • Batching/lot splitting: jobs may be split across parallel machines or processed in batches; objectives change.

Formulas

Fⱼ = Cⱼ − rⱼ

  • Flow time of job j; Fⱼ in s, Cⱼ in s, rⱼ in s; single or multi-machine, definition.

Wⱼ = F�� − pⱼ

  • Waiting time (single-machine, one-operation job); Wⱼ in s, Fⱼ in s, pⱼ in s; assumes no preemption.

Lⱼ = Cⱼ − dⱼ

  • Lateness; Lⱼ in s, Cⱼ in s, dⱼ in s; definition (can be negative).

Tⱼ = max(0, Lⱼ)

  • Tardiness; Tⱼ in s; definition.

Eⱼ = max(0, −Lⱼ)

  • Earliness; Eⱼ in s; definition.

Cmax = maxⱼ Cⱼ

  • Makespan; in s; any environment; objective to minimize in many shop problems.

Average flow time = (1/n) · ∑ⱼ Fⱼ

  • Average over n jobs; in s; batch with known rⱼ.

∑Cⱼ = ∑ⱼ Cⱼ

  • Total completion time; in s; minimized by SPT (1||∑Cⱼ with rⱼ = 0, no preemption).

Sequence by increasing pⱼ / wⱼ (Smith’s Rule)

  • Optimal order for 1||∑wⱼ Cⱼ; pⱼ in s, wⱼ dimensionless positive weights.

CRⱼ = (dⱼ − t_now) / (remaining processing time)

  • Critical ratio priority index; dimensionless; dynamic dispatching.

L = λ · W

  • Little’s Law; L in jobs, λ in jobs/s, W in s; steady state, stable system.

Worked examples

Example 1 — Direct: Johnson’s rule for a 2-machine flow shop (minimize makespan) Given: Five jobs J1–J5 must be processed on M1 then M2. Processing times (s):

  • J1: p₁ = 12, p₂ = 8
  • J2: p₁ = 7, p₂ = 15
  • J3: p₁ = 9, p₂ = 6
  • J4: p₁ = 16, p₂ = 9
  • J5: p₁ = 5, p₂ = 11 Assumptions: deterministic, no preemption, infinite buffer between machines, all jobs ready at t = 0.

Steps:

  1. Apply Johnson’s rule.
    • Smallest time among all p’s is 5 (J5 on M1) → place earliest.
    • Remaining smallest is 6 (J3 on M2) → place latest.
    • Remaining: J1(12,8), J2(7,15), J4(16,9).
    • Next smallest is 7 (J2 on M1) → place next earliest.
    • Remaining: J1(12,8), J4(16,9); smallest is 8 (J1 on M2) → place next latest.
    • Last remaining J4 goes in the remaining middle slot.
    • Final sequence: [J5, J2, J4, J1, J3].
  2. Build the schedule and compute start/finish times.
    • Machine M1 (in sequence order):
      • J5: S=0 s, C=0+5=5 s
      • J2: S=5 s, C=5+7=12 s
      • J4: S=12 s, C=12+16=28 s
      • J1: S=28 s, C=28+12=40 s
      • J3: S=40 s, C=40+9=49 s
    • Machine M2 (a job can start after it finishes on M1 and M2 is free):
      • J5: S=max(0,5)=5 s, C=5+11=16 s
      • J2: S=max(16,12)=16 s, C=16+15=31 s
      • J4: S=max(31,28)=31 s, C=31+9=40 s
      • J1: S=max(40,40)=40 s, C=40+8=48 s
      • J3: S=max(48,49)=49 s, C=49+6=55 s
  3. Read the makespan and idle times.
    • Cmax = 55 s (end of J3 on M2).
    • Idle time on M1 over [0, Cmax]: 55 − total busy on M1 = 55 − (12+7+9+16+5) = 6 s (this is tail idle from 49–55 s). Internal idle before its last completion: 0 s.
    • Idle time on M2 over [0, Cmax]: initial wait 5 s before J5 + a 1 s gap before J3 = 6 s total.

Answer: Optimal sequence [J5, J2, J4, J1, J3] with makespan Cmax = 55 s; M1 idle time = 6 s; M2 idle time = 6 s.

Example 2 — GATE-level: Single machine, due dates — compare EDD (min Lmax) and Moore–Hodgson (min number tardy) Given: Six jobs (all released at t = 0), single machine, processing times pⱼ (s) and due dates dⱼ (s):

  • J1: p=12, d=20
  • J2: p=7, d=15
  • J3: p=9, d=27
  • J4: p=5, d=14
  • J5: p=11, d=35
  • J6: p=4, d=10 Assumptions: deterministic, non-preemptive, single operation per job.

(a) Sequence to minimize maximum lateness Lmax: use EDD.

  1. Order by increasing dⱼ: [J6(10), J4(14), J2(15), J1(20), J3(27), J5(35)].
  2. Compute completion times and lateness:
    • J6: C=4, L=4−10=−6 s
    • J4: C=9, L=9−14=−5 s
    • J2: C=16, L=16−15=+1 s
    • J1: C=28, L=28−20=+8 s
    • J3: C=37, L=37−27=+10 s
    • J5: C=48, L=48−35=+13 s
  3. Lmax = max Lⱼ = +13 s. Answer (a): EDD sequence minimizes Lmax; Lmax = 13 s.

(b) Sequence to minimize the number of tardy jobs: use Moore–Hodgson.

  1. Start with EDD order and build a feasible on-time set, tracking cumulative time and removing the job with largest p when a tardy would occur.
    • Add J6 (C=4 ≤ 10) → on-time set {J6}.
    • Add J4 (C=9 ≤ 14) → on-time set {J6, J4}.
    • Add J2 (C=16 > 15) → remove longest p among {4,5,7}: remove J2. On-time set {J6, J4}.
    • Add J1 (C=21 > 20) → remove longest p among {4,5,12}: remove J1. On-time set {J6, J4}.
    • Add J3 (C=18 ≤ 27) → on-time set {J6, J4, J3}.
    • Add J5 (C=29 ≤ 35) → on-time set {J6, J4, J3, J5}.
  2. Result: minimum number of tardy jobs is 2 (the removed jobs J2 and J1). A valid final schedule places the on-time set in EDD order then the tardy set in any order (doesn’t change the count). Choose tardy in SPT to reduce total tardiness: [J6, J4, J3, J5, J2, J1].
  3. Compute performance for this schedule (optional but good practice):
    • Completion times: 4, 9, 18, 29, 36, 48 s.
    • Number of tardy jobs = 2 (J2, J1 have positive lateness).
    • Total tardiness: T₂ = 36−15 = 21 s; T₁ = 48−20 = 28 s; others 0 → ∑Tⱼ = 49 s.
    • Average flow time: (4+9+18+29+36+48)/6 = 144/6 = 24 s (since rⱼ=0, average flow time equals average completion time). Answer (b): Minimum number of tardy jobs = 2 (J2, J1). For schedule [J6, J4, J3, J5, J2, J1], makespan = 48 s, total tardiness = 49 s, average flow time = 24 s.

Notes:

  • EDD minimized Lmax = 13 s in part (a) but had 4 tardy jobs; Moore–Hodgson minimized the number tardy (2) in part (b) but did not minimize Lmax. Choice of rule depends on the objective.

Common mistakes

  • Using EDD to minimize average flow time or total completion time; SPT is the correct optimal rule for 1||∑Cⱼ (rⱼ = 0, non-preemptive).
  • Forgetting assumptions: applying EDD for Lmax when some rⱼ > 0 (then 1|rⱼ|Lmax is different), or using Johnson’s rule when routes differ from M1→M2.
  • Misapplying Johnson’s rule to three or more machines without checking the reduction condition; or forgetting to place M2-min jobs at the end.
  • In flow-shop Gantt charts, starting a job on M2 before it finishes on M1 (violates precedence), or allowing overlap on the same machine.
  • Ignoring sequence-dependent setup times; if setups depend on order, SPT/Johnson optimality does not generally hold.
  • Dropping units; always keep seconds for time and, when there is no idle time (e.g., rⱼ = 0 and no intentional idling), the last completion time on a single machine equals ∑ pⱼ. With release dates or deliberate idling, this need not hold.
  • For CR/Slack rules, forgetting to update t_now and remaining times dynamically.

For GATE ME

  • Single-machine metrics: compute Cⱼ, Fⱼ, Wⱼ, Lⱼ, Tⱼ, Eⱼ, Cmax, Lmax from a given sequence. Practise quick, accurate Gantt chart reading.
  • Rule identification and application:
    • Recognize when SPT, EDD, WSPT, CR, LPT apply and the objective each optimizes.
    • Implement Moore–Hodgson to find the minimum number of tardy jobs.
  • Two-machine flow shop: apply Johnson’s rule to produce the sequence and compute Cmax and machine idle times. Be comfortable doing it without a table if needed.
  • Conceptual checks: state assumptions for each rule, explain why they are needed, and know counter-examples when assumptions break (e.g., sequence-dependent setups).
  • Short theory: exact statements of SPT optimality (1||∑Cⱼ), EDD optimality (1||Lmax), Johnson’s optimality (F2||Cmax), Little’s Law, and when three-machine Johnson reduction is permissible.
  • Heuristic awareness: LPT for parallel identical machines to reduce Cmax; know it is heuristic, not guaranteed optimal.
  • Avoid cross-topic deep dives: for variability, reference Queuing Theory; for project networks, PERT/CPM; for optimization across capacities, see Operations Research/Linear Programming.

Quick check

  1. Define lateness and tardiness for a job with Cⱼ = 62 s and dⱼ = 55 s.
  2. Which rule minimizes total completion time on a single machine with all jobs available at time zero: EDD or SPT?
  3. State Johnson’s rule in one line for a 2-machine flow shop.

Answers: (1) Lⱼ = 62−55 = +7 s; Tⱼ = max(0,7) = 7 s. (2) SPT. (3) Repeatedly pick the smallest remaining processing time: if it is on M1 place the job at the earliest available position, if on M2 place it at the latest available position; continue until all jobs are sequenced.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?