Overview
Min-Min Scheduling is a scheduling method that selects or admits work using a concrete priority, fairness, deadline, or capacity rule. It helps expose the policy tradeoff behind queue order, fairness, deadlines, or resource use.
ExtendedSource checked
Min-Min Scheduling
Min-Min Scheduling chooses jobs using priority, completion-time, or resource-availability rules.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Scheduling
- Difficulty
- Intermediate
- Family
- Scheduling
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
priority ruleresource allocationqueue disciplinetask order
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 Min-Min Scheduling when queue order, resource assignment, or deadline policy must be explicit.
- Use it when comparing fairness, latency, throughput, or utilization policies matters.
When Not to Use
- Avoid when the policy would hide starvation, unfairness, or deadline misses.
- Avoid when task durations or priorities are too uncertain for the rule to be meaningful.
What It Does
- Ranks ready work with a scheduling rule
- Updates waiting time, deadlines, or capacity
- Returns an order, assignment, or admission decision
Use Cases
- CPU scheduling
- Network queue management
- Workflow and batch processing
Inputs
- Jobs or requests
- Timing constraints
- Resource limits
Outputs
- Execution order
- Resource assignment
- Timing decision
Key Formulas (1)
Earliest completion
completion(task, machine) = readytime(machine) + runtime(task, machine)
completion(task, machine) = ready_time(machine) + runtime(task, machine)Chooses the task with the smallest earliest completion time.
Pseudocode
- 1.Collect ready jobs, queues, or tasks
- 2.Compute the method's priority, fairness, or capacity score
- 3.Select the next job or resource assignment
- 4.Update waiting time, capacity, or completion state
- 5.Repeat until all work is scheduled or admitted
Canonical Example
- Input
- jobs = [{id:A, time:3}, {id:B, time:1}], resource = one worker
- Output
- ordered or assigned jobs according to the scheduling rule
- Explanation
- Min-Min Scheduling computes the priority or capacity rule and chooses the next job from the ready set.
Implementation Notes
- Make tie-breaking deterministic and visible in tests.
- Track waiting time, service time, and resource state separately.
Common Pitfalls
- Forgetting tie-breaking rules makes schedules unstable across runs.
- Ignoring starvation and fairness edge cases can make good averages hide bad tail behavior.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow queued jobs moving onto processors, links, or time slots as the scheduling rule changes priorities.
Step 1 of 5: Collect ready jobs, queues, or tasks
schedulingNotes
Min-Min Scheduling operates in O(n log n) time and O(n) space within the Scheduling family. Key governing relation: completion(task, machine) = ready_time(machine) + runtime(task, machine). Often compared with Round Robin Scheduling and Priority Scheduling.
Sources (1)
What each reference supports for this entry.
Scheduling in Distributed Computing Systems
BookDistributed scheduling reference for min-min task assignment and earliest-completion heuristics.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toMax-Min Scheduling
Min-min and max-min are heterogeneous task-scheduling heuristics with opposite task-selection priorities.
Conceptual neighborHEFT Scheduling
Both schedule tasks on heterogeneous resources using estimated completion times.
Related Algorithms
Tags
Scheduling