Overview
Earliest Due Date scheduling sorts available jobs by their due dates and runs the most urgent due date first. It is a simple nonpreemptive rule often used when due-date order is more important than processing-time variation.
CoreSource checked
Earliest Due Date Scheduling
Orders jobs by due date to reduce lateness-oriented scheduling risk.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Scheduling
- Difficulty
- Intermediate
- Family
- Single-Machine Scheduling
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 6
- Code example
- Ready
- Visualization
- Ready
Core Concepts
due-date schedulingsingle-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 due dates dominate the scheduling objective and jobs are all available.
- Use as a simple transparent rule before adding release times, weights, or preemption.
When Not to Use
- Avoid when processing times, weights, or release times dominate the objective.
- Avoid when minimizing total weighted completion time is more important than due-date order.
What It Does
- Sorts jobs by due date
- Builds a nonpreemptive schedule in that order
- Tracks completion times and lateness
Use Cases
- Single-machine job sequencing
- Due-date-driven production queues
- Baselines for comparing more complex scheduling rules
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.Collect jobs with processing times and due dates
- 2.Sort jobs by increasing due date
- 3.Append jobs to the schedule in sorted order
- 4.Accumulate completion time after each job
- 5.Compute lateness or tardiness metrics if needed
Canonical Example
- Input
- jobs A(p=3,d=8), B(p=2,d=4), C(p=1,d=6)
- Output
- order = B, C, A
- Explanation
- The jobs run in increasing due-date order: 4, then 6, then 8.
Implementation Notes
- Define whether jobs are all available at time zero.
- Sort by due date, then use a deterministic tie-breaker.
- Compute completion, lateness, and tardiness metrics after building the order.
Common Pitfalls
- Confusing due dates with hard deadlines can hide infeasible schedules.
- Ignoring release times makes the sorted order impossible in dynamic queues.
- Tie-breaking by input order can create unstable schedules.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow processing jobs in increasing due-date order on a small due-date scheduling example.
Step 1 of 5: Collect jobs with processing times and due dates
scheduling-mechanismNotes
Earliest Due Date is simple and explainable, but it does not account for job weights or release times.
Sources (1)
What each reference supports for this entry.
Scheduling: Theory, Algorithms, and Systems
BookScheduling reference for Earliest Due Date Scheduling precedence, due-date, lateness, or project-schedule optimization.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toShortest Job First
Scheduling · Core
Earliest Due Date prioritizes due dates, while shortest-job-first prioritizes short processing times.
Compare with thisConceptual neighborsInterval Scheduling
Scheduling · Core
Both use ordering by finishing or due-time information to make scheduling choices.
Compare with thisConceptual neighborMoore-Hodgson Algorithm
Scheduling · Core
Moore-Hodgson uses due-date order while dropping jobs to minimize late jobs.
Compare with thisRelationships
View full relationship pageAlternative toShortest Job First
Earliest Due Date prioritizes due dates, while shortest-job-first prioritizes short processing times.
Conceptual neighborMoore-Hodgson Algorithm
Moore-Hodgson uses due-date order while dropping jobs to minimize late jobs.
Related Algorithms
Tags
Scheduling