Overview
Moore-Hodgson sorts jobs by due date and scans the prefix schedule. Whenever the current prefix cannot meet its due date, it removes the longest processing-time job from that prefix.
CoreSource checked
Moore-Hodgson Algorithm
Minimizes the number of late jobs on a single machine by dropping the longest job from overloaded prefixes.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Scheduling
- Difficulty
- Intermediate
- Family
- Single-Machine Scheduling
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
late-job minimizationsingle-machine schedulingscheduling
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n log n)
Worst
O(n^2)
Space
O(n)
When to Use
- Use when all jobs are available and the goal is minimizing the number of late jobs.
- Use when dropped or deferred jobs can be handled separately after the on-time set is chosen.
When Not to Use
- Avoid when jobs have weights, release times, or precedence constraints not modeled by the algorithm.
- Avoid when every job must be scheduled even if late-job count is not the objective.
What It Does
- Sorts jobs by due date
- Maintains the scheduled prefix duration
- Removes the longest job when a prefix becomes late
Use Cases
- Single-machine scheduling with late-job count as the objective
- Production planning where some jobs may be deferred
- Teaching exchange arguments in scheduling
Inputs
- Job list with processing durations p_j and due dates d_j
- Single-machine availability window
Outputs
- Ordered job execution sequence
- Completion times C_j and lateness/tardiness metrics
Pseudocode
- 1.Sort jobs by increasing due date
- 2.Initialize total processing time to 0 and an empty max-heap
- 3.For each job, add it to the heap and add its processing time
- 4.If total time exceeds this job's due date, remove the longest job from the heap
- 5.Return jobs left in the heap as the maximum on-time set
Canonical Example
- Input
- jobs A(p=4,d=4), B(p=3,d=5), C(p=2,d=6)
- Output
- on-time jobs = B, C; late/deferred job = A
- Explanation
- The prefix A,B exceeds due date 5, so the longest job A is removed.
Implementation Notes
- Sort by due date and scan in that order.
- Use a max-heap keyed by processing time for jobs currently in the on-time prefix.
- Record removed jobs so the final late set is explicit.
Common Pitfalls
- Treating removed jobs as deleted rather than late or deferred work.
- Using the shortest job instead of the longest job for removal breaks the greedy rule.
- Forgetting to maintain total prefix processing time after removals.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow sorting by due date and removing the longest job when deadlines are missed on a small late-job minimization example.
Step 1 of 5: Sort jobs by increasing due date
scheduling-mechanismNotes
The algorithm chooses an on-time subset; it does not optimize the order of the late jobs.
Sources (2)
What each reference supports for this entry.
Scheduling: Theory, Algorithms, and Systems
BookScheduling reference for Moore-Hodgson single-machine late-job minimization and due-date ordered job selection.
Moore Late-Jobs Sequencing Algorithm
PaperOriginal reference for minimizing the number of late jobs on one machine, including the Moore-Hodgson scheduling procedure.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageMoore-Hodgson scans jobs in earliest-due-date order.
UsesPriority Queue
A max-priority queue removes the longest job from an overloaded prefix.
Related Algorithms
Tags
Scheduling