CoreSource checked

Shortest Job First

Runs the ready task with the smallest expected processing time.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Scheduling
Difficulty: Beginner
Family: Greedy Scheduling
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 0
Relationships: 6
Code example: Ready
Visualization: Ready

Overview

Shortest Job First reduces average waiting time by choosing short tasks before long ones.

Core Concepts

task orderingprocess schedulinggreedy choicegreedy schedulingready queuetask priorityresource allocation

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

When to Use

Use Shortest Job First when you need to order tasks by estimated duration.
Use it for batch scheduling with inputs like tasks with estimated run times.
Use it when tasks, priorities, deadlines, or resource limits drive execution order.
Use it when the Greedy Scheduling tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when fairness, latency, and throughput requirements conflict but are not prioritized.
Avoid it when the required output is not duration-prioritized schedule.

What It Does

Orders tasks by estimated duration
Runs shorter tasks earlier

Use Cases

Batch scheduling
CPU scheduling examples
Minimizing average wait time

Inputs

Tasks with estimated run times

Outputs

Duration-prioritized schedule

Pseudocode

1.Collect ready tasks
2.Choose the task with the shortest estimated duration
3.Run that task
4.Update the ready set
5.Repeat until all tasks complete

Canonical Example

Input: tasks = A(4ms), B(2ms), C(1ms)
Output: execution order and completion times
Explanation: Shortest Job First: The scheduler chooses which task should run next according to its rule.

Implementation Notes

Keep the input contract explicit: Tasks with estimated run times.
Record arrival time, remaining work, and completion time so schedule metrics can be checked.
State whether the policy is preemptive and what fairness, latency, or deadline objective it optimizes.

Common Pitfalls

Shortest Job First depends on knowing or estimating task duration.
Ignoring starvation, preemption cost, or inaccurate duration estimates.
Handle empty, invalid, and boundary inputs before trusting duration-prioritized schedule.
Ignoring preemption cost, release times, or starvation can make a schedule look correct only in toy cases.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show shorter jobs moving ahead of longer jobs in a schedule.

Step 1 of 5: Collect ready tasks

duration-order

Notes

Shortest Job First operates in O(n log n) time and O(n) space within the Greedy Scheduling family. Often compared with Round Robin Scheduling and Earliest Deadline First.