Overview
Earliest Start Time scheduling propagates finish times through dependency edges in topological order.
CoreSource checked
Earliest Start Time
Computes the earliest time each task can begin after its prerequisites finish.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Scheduling
- Difficulty
- Intermediate
- Family
- Project Scheduling
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
dependency graphtopological orderfinish timeforward pass
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)
When to Use
- Use when ordering jobs needs dependency graph.
- Use when the input matches the assumptions behind project Scheduling.
When Not to Use
- Avoid when the real constraints are not represented in the scheduling model.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Computes the earliest time each task can begin after its prerequisites finish
- Uses dependency graph and topological order to guide the work.
- Produces schedule.
Use Cases
- Ordering jobs
- Allocating compute time
- Planning constrained work
Inputs
- Jobs or tasks
- Durations, deadlines, or priorities
Outputs
- Schedule
- Start and finish times
- Queue decisions
Key Formulas (1)
Earliest start
ES(task) = max EF(predecessor)
ES(task) = max EF(predecessor)A task can start only after all predecessors have finished.
Pseudocode
- 1.Collect ready tasks and their release times, durations, priorities, or deadlines
- 2.Choose the next task according to the scheduling rule
- 3.Advance time, update remaining work, and add newly ready tasks
- 4.Repeat until every task is completed or no feasible schedule remains
Canonical Example
- Input
- tasks = A(duration=2, deadline=5), B(duration=1, deadline=3), C(duration=3, deadline=8)
- Output
- Schedule
- Explanation
- Earliest Start Time applies dependency graph to produce schedule.
Implementation Notes
- Keep the scheduling objective explicit so tie-breaking rules are consistent.
- Keep the dependency graph step separate enough to test independently.
- State whether the policy is preemptive and what fairness, latency, or deadline objective it optimizes.
Common Pitfalls
- Optimizing one metric can harm fairness, latency, or deadline behavior.
- Test edge cases, not only clean examples.
- Ignoring preemption cost, release times, or starvation can make a schedule look correct only in toy cases.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow jobs on a timeline with queue order, start times, and constraints.
Step 1 of 4: Collect ready tasks and their release times, durations, priorities, or deadlines
scheduling-mechanismNotes
Earliest Start Time should be used with the assumptions and tradeoffs of project Scheduling in mind.
Sources (1)
What each reference supports for this entry.
Scheduling: Theory, Algorithms, and Systems
BookScheduling reference for Earliest Start Time precedence, due-date, lateness, or project-schedule optimization.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageOften paired withLatest Finish Time
Earliest-start and latest-finish times are paired schedule bounds in precedence-constrained planning.
Related Algorithms
Tags
SchedulingTask SchedulingDirected Acyclic GraphPlanning