Overview
Latest Finish Time scheduling works backward through a dependency graph to identify slack and critical tasks.
CoreSource checked
Latest Finish Time
Computes how late each task can finish without delaying the project.
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
- 2
- Code example
- Ready
- Visualization
- Ready
Core Concepts
dependency graphbackward passslackproject deadline
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 how late each task can finish without delaying the project
- Uses dependency graph and backward pass 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)
Latest finish
LF(task) = min LS(successor)
LF(task) = min LS(successor)A task must finish before the earliest latest-start time of its successors.
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
- Latest Finish 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
Latest Finish 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 Latest Finish 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 withEarliest Start Time
Latest-finish and earliest-start times are paired quantities in critical-path scheduling analysis.
Related Algorithms
Tags
SchedulingTask SchedulingDirected Acyclic GraphPlanning