Single-machine sequencing: SPT, EDD and Moore's rule

Single-machine sequencing measures, SPT and weighted SPT for flow time, EDD for maximum lateness, and Moore's algorithm for the number of tardy jobs.

Drafted with Aria, reviewed by the AiCanCode.org team. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Many shops have one bottleneck machine – a heat-treatment furnace, a CNC centre, a paint booth – where jobs queue up. The order in which those jobs are run decides how long customers wait, how much work-in-process piles up and how many orders go out late. Simple priority rules, with known optimal properties, let a supervisor choose the right sequence for the goal that matters.

Key ideas

The single-machine problem. n jobs are waiting at one machine, all available at time zero. Each job i has a processing time pᵢ (including set-up, assumed sequence-independent) and a due date dᵢ. The machine does one job at a time and a job, once started, is not interrupted. Because the machine is never idle, the makespan (time to finish all jobs) equals Σpᵢ whatever the sequence; the sequence only changes how completion times are spread.

Performance measures (job i in a given sequence).

  • Completion time Cᵢ – time at which job i finishes.
  • Flow time Fᵢ – time the job spends in the shop; with all jobs ready at zero, Fᵢ = Cᵢ.
  • Waiting time Wᵢ = Fᵢ − pᵢ.
  • Lateness Lᵢ = Cᵢ − dᵢ (negative means early).
  • Tardiness Tᵢ = max(0, Lᵢ); a job is "tardy" or "late" if Tᵢ > 0.
  • Average number of jobs in the system = ΣFᵢ / makespan (the time-average WIP).

Optimal rules.

  • SPT (shortest processing time first) minimises mean flow time, mean waiting time, mean completion time, mean lateness and average number of jobs in the system. Reason: a short job placed first delays every following job by only a small amount. (Pairwise interchange proof: swapping adjacent jobs with pᵢ > pⱼ into order j, i reduces total flow time by pᵢ − pⱼ.)
  • WSPT (Smith's rule) – sequence in increasing pᵢ/wᵢ, where wᵢ is a weight (priority, value or holding cost); minimises weighted mean flow time.
  • EDD (earliest due date first) minimises the maximum lateness and the maximum tardiness. If EDD gives no tardy job, no sequence can do better on any due-date measure.
  • Moore's (Moore–Hodgson) algorithm minimises the number of tardy jobs:
    1. Arrange all jobs in EDD order.
    2. Find the first tardy job in the current sequence. If none, stop.
    3. Among the jobs up to and including that first tardy job, remove the one with the longest processing time and set it aside.
    4. Recompute completion times and repeat from step 2.
    5. The final sequence = on-time jobs in EDD order, followed by the removed jobs in any order (they are late anyway).
  • Mean tardiness has no simple optimal rule; SPT tends to do well when the shop is heavily loaded, EDD when due dates are loose. Exact answers need branch-and-bound or dynamic programming.

Other dispatching rules used in practice: FCFS (fair, poor on most measures), LPT (longest first – usually worst on flow time), critical ratio CR = (due date − now)/remaining processing time (CR < 1 means behind schedule), and minimum slack (dᵢ − now − pᵢ).

Limits. Results assume all jobs are ready at time zero, no preemption, deterministic times and sequence-independent set-ups. With sequence-dependent set-ups, the problem becomes a travelling-salesman type.

Formulas

Cᵢ = Σ p (all jobs up to and including i in the sequence) Mean flow time F̄ = Σ Fᵢ / n Lᵢ = Cᵢ − dᵢ, Tᵢ = max(0, Lᵢ) Mean tardiness T̄ = Σ Tᵢ / n Average jobs in system N̄ = Σ Fᵢ / Σ pᵢ WSPT order: increasing pᵢ / wᵢ Critical ratio CR = (dᵢ − t_now) / remaining processing time

  • p = processing time (h or days), d = due date (same unit, from time zero), C, F, L, T in the same time unit, n = number of jobs, w = weight (dimensionless or ₹ per unit time), N̄ in jobs.

Worked examples

Example 1 (standard) – SPT vs EDD. Five jobs, all ready at day 0 (times in days): A: p = 6, d = 8; B: p = 2, d = 6; C: p = 8, d = 14; D: p = 3, d = 15; E: p = 9, d = 30. Makespan = 28 days. SPT order: B–D–A–C–E

  1. Completion times: 2, 5, 11, 19, 28. Mean flow time = 65/5 = 13.0 days.
  2. Lateness: B −4, D −10, A +3, C +5, E −2. Maximum lateness = 5 days; total tardiness = 8; tardy jobs = 2 (A, C).
  3. Average jobs in system = 65/28 = 2.32. EDD order: B–A–C–D–E
  4. Completion times: 2, 8, 16, 19, 28. Mean flow time = 73/5 = 14.6 days.
  5. Lateness: B −4, A 0, C +2, D +4, E −2. Maximum lateness = 4 days; total tardiness = 6; tardy jobs = 2 (C, D).
  6. Average jobs in system = 73/28 = 2.61.
  7. As theory predicts, SPT gives the lower mean flow time (13.0 < 14.6) and EDD the lower maximum lateness (4 < 5).

Example 2 (GATE level) – Moore's algorithm. Six jobs (hours): 1: p = 4, d = 6; 2: p = 7, d = 10; 3: p = 3, d = 12; 4: p = 6, d = 15; 5: p = 5, d = 16; 6: p = 2, d = 18.

  1. EDD order: 1–2–3–4–5–6. Completion: 4, 11 … Job 2 finishes at 11 > 10: first tardy job is 2.
  2. Among jobs {1, 2}, the longest is job 2 (7 h): remove it.
  3. New sequence 1–3–4–5–6: completion 4, 7, 13, 18 … Job 5 finishes at 18 > 16: first tardy job is 5.
  4. Among {1, 3, 4, 5}, the longest is job 4 (6 h): remove it.
  5. Sequence 1–3–5–6: completion 4, 7, 12, 14 against due dates 6, 12, 16, 18 – all on time.
  6. Optimal sequence 1–3–5–6–4–2 (or 1–3–5–6–2–4); minimum number of tardy jobs = 2 (jobs 2 and 4). A full enumeration of all 720 sequences confirms that no sequence has fewer than 2 tardy jobs.

Common mistakes

  • Removing the tardy job itself in Moore's algorithm instead of the longest job among those up to the first tardy one.
  • Counting a job that finishes exactly on its due date as late (L = 0 is on time).
  • Averaging lateness only over late jobs; mean tardiness divides by all n jobs unless the question says otherwise.
  • Thinking a rule can change the makespan on a single machine with all jobs ready at zero – it cannot.
  • Quoting SPT as optimal for maximum lateness or EDD for mean flow time.
  • Mixing lateness (can be negative) with tardiness (never negative).

For GATE PI

Typical questions give four to six jobs with processing times and due dates and ask for the mean flow time, total or mean tardiness, maximum lateness or number of tardy jobs under SPT, EDD or Moore's rule, or which rule optimises a stated measure. Weighted SPT and the average number of jobs in the system also appear. Practise building a completion-time table quickly and running Moore's algorithm without skipping steps.

Quick check

  1. Which rule minimises mean waiting time on a single machine?
  2. Jobs with p = 5, 3, 8 h are run in SPT order. What is the mean flow time?
  3. A job finishes at 22 h with due date 18 h. What are its lateness and tardiness?
  4. Which algorithm minimises the number of tardy jobs?

Answers: 1. SPT. 2. Order 3, 5, 8: completions 3, 8, 16; mean flow time = 27/3 = 9 h. 3. Lateness = tardiness = 4 h. 4. Moore's (Moore–Hodgson) algorithm.

Interview questions

All Production Planning and Operations Management interview questions

Try answering each one aloud before you open it.

  1. 1.What is the Shortest Processing Time (SPT) rule in single-machine sequencing?Concept

    The Shortest Processing Time (SPT) rule is a scheduling method where jobs are sequenced in order of their processing times, starting with the shortest. This rule aims to minimize the average completion time and is particularly effective in reducing the total time jobs spend in the system.

  2. 2.Explain the Earliest Due Date (EDD) rule in the context of single-machine sequencing.Concept

    The Earliest Due Date (EDD) rule is a scheduling strategy where jobs are sequenced based on their due dates, with the job having the earliest due date scheduled first. This rule is primarily used to minimize the maximum lateness of jobs, ensuring that deadlines are met as closely as possible.

  3. 3.What is Moore's rule in single-machine sequencing, and what problem does it address?Concept

    Moore's (Moore–Hodgson) algorithm minimises the number of tardy jobs on a single machine. Arrange the jobs in EDD order, find the first tardy job, and among the jobs up to and including it remove the one with the longest processing time. Recompute and repeat until no job in the sequence is tardy. The on-time jobs run in EDD order and the removed jobs are placed at the end; their number is the minimum possible number of late jobs.

  4. 4.Why is the SPT rule often preferred in manufacturing environments?Application

    The SPT rule is preferred in manufacturing because it minimizes the average completion time and work-in-process inventory. By processing shorter jobs first, it helps in quickly freeing up resources and reducing the time jobs spend waiting in the system, which can improve overall efficiency.

  5. 5.What are the potential drawbacks of using the EDD rule in scheduling?Application

    While the EDD rule helps in minimizing maximum lateness, it may not always optimize other performance measures like average completion time or total tardiness. Additionally, if due dates are not well-distributed or realistic, the EDD rule might lead to inefficient scheduling and increased idle times.

  6. 6.How does Moore's rule help in reducing the number of late jobs, and what is a potential limitation?Application

    It starts from EDD, which minimises maximum lateness, and repeatedly drops the longest job in the late prefix, which gains the most time per job sacrificed, so the count of late jobs is provably minimised. Its limitation is that it ignores how late the dropped jobs are and how important they are: a dropped job may end up very late, so total tardiness or a key customer's order can suffer. A weighted version or a different rule is used when lateness size or job priority matters.

  7. 7.In Moore's rule, what happens to a job after it is removed from the sequence?Application

    The removed job is set aside and will be scheduled after all the on-time jobs, so it is accepted as late. Taking out the longest job among those up to the first tardy job frees the most time for the jobs that follow, so the remaining sequence (still in EDD order) is recomputed and checked for the next tardy job. The process stops when the remaining jobs are all on time; the removed jobs, placed at the end in any order, are the minimum set of late jobs.

  8. 8.Consider three jobs with processing times of 4, 6, and 8 hours, and due dates of 10, 12, and 15 hours respectively. Sequence these jobs using the SPT rule.Numerical

    Using the SPT rule, the jobs are sequenced in order of their processing times: Job 1 (4 hours), Job 2 (6 hours), and Job 3 (8 hours). This sequence minimizes the average completion time.

  9. 9.Given jobs with due dates of 5, 10, and 15 hours and processing times of 3, 7, and 2 hours respectively, sequence them using the EDD rule.Numerical

    Using the EDD rule, the jobs are sequenced based on their due dates: Job 1 (due in 5 hours), Job 2 (due in 10 hours), and Job 3 (due in 15 hours). This sequence aims to minimize the maximum lateness.

  10. 10.What happens if all jobs have the same due date when using Moore's rule?Application

    If all jobs have the same due date, Moore's rule will sequence them based on their processing times, similar to the SPT rule, to minimize the number of late jobs. However, if the total processing time exceeds the common due date, some jobs will inevitably be late.

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

Stuck on something here?

PreviousCapacity planningNext Flow shop scheduling: Johnson's rule