Overview
Critical Ratio Scheduling is a dispatching rules method for production scheduling. It works by prioritizing jobs by time remaining divided by work remaining.
ExtendedSource checked
Critical Ratio Scheduling
Critical Ratio Scheduling addresses production scheduling by prioritizing jobs by time remaining divided by work remaining.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Scheduling
- Difficulty
- Intermediate
- Family
- Dispatching Rules
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
production schedulingdispatching rulesscheduling
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 Critical Ratio Scheduling when solving production scheduling and you want to benefit from prioritizing jobs by time remaining divided by work remaining.
- Choose it when O(n log n) average/worst-case time and O(n) memory match your workload profile.
- Prefer it over Earliest Due Date Scheduling or Least Slack Time Scheduling when the problem structure favors production scheduling.
When Not to Use
- Avoid when the chosen priority rule optimizes the wrong business or real-time metric.
- Avoid when resource constraints are coupled in ways the method does not model.
What It Does
- Computes production scheduling within Dispatching Rules workloads (O(n log n) time, O(n) space).
- Works by prioritizing jobs by time remaining divided by work remaining.
- Maintains key invariants across production scheduling, dispatching rules, scheduling.
Use Cases
- Production and research workloads requiring production scheduling via prioritizing jobs by time remaining divided by work remaining.
- Dispatching Rules pipelines where O(n log n) time and O(n) space fit system constraints.
- Engineering comparisons against Earliest Due Date Scheduling and Least Slack Time Scheduling when tuning production scheduling.
Inputs
- Pending job queue with remaining work and due dates
- Current shop-floor or processor time
Outputs
- Priority-ranked dispatch order sorted by critical ratio
- Flagged overdue or behind-schedule jobs
Pseudocode
- 1.Initialize the input structures and parameters for Critical Ratio Scheduling (production scheduling).
- 2.Set up the working state for production scheduling (dispatching rules).
- 3.Execute the core step by prioritizing jobs by time remaining divided by work remaining.
- 4.Update invariants and check termination or convergence criteria.
- 5.Return the resulting production scheduling output.
Canonical Example
- Input
- Pending job queue with remaining work and due dates configured for a representative production scheduling test case
- Output
- Priority-ranked dispatch order sorted by critical ratio satisfying Critical Ratio Scheduling invariants
- Explanation
- Critical Ratio Scheduling processes the input by prioritizing jobs by time remaining divided by work remaining, tracking production scheduling and dispatching rules to produce the verified production scheduling result.
Implementation Notes
- Define the scheduling objective before choosing the dispatch rule.
- Represent release time, deadline, priority, and resource needs separately.
- Test preemptive and non-preemptive assumptions explicitly.
Common Pitfalls
- Optimizing one metric while accidentally violating deadlines or resource constraints.
- Ignoring preemption, release times, or machine-count assumptions.
- Testing only jobs with distinct priorities or durations.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow prioritizing jobs by time remaining divided by work remaining on a small production scheduling example.
Step 1 of 5: Initialize the input structures and parameters for Critical Ratio Scheduling (production scheduling).
scheduling-mechanismNotes
Critical Ratio Scheduling operates in O(n log n) time and O(n) space within the Dispatching Rules family. Often compared with Earliest Due Date Scheduling and Least Slack Time Scheduling.
Sources (1)
What each reference supports for this entry.
Scheduling: Theory, Algorithms, and Systems
BookScheduling reference for critical-ratio dispatching rules and due-date driven production scheduling.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Conceptual neighborEarliest Due Date Scheduling
Scheduling · Core
Critical Ratio Scheduling and Earliest Due Date Scheduling share a concrete dispatching rules mechanism for production scheduling.
Compare with thisConceptual neighborHighest Response Ratio Next
Scheduling · Core
Critical Ratio Scheduling and Highest Response Ratio Next share a concrete dispatching rules mechanism for production scheduling.
Compare with thisRelationships
View full relationship pageConceptual neighborEarliest Due Date Scheduling
Critical Ratio Scheduling and Earliest Due Date Scheduling share a concrete dispatching rules mechanism for production scheduling.
Conceptual neighborLeast Slack Time Scheduling
Critical Ratio Scheduling and Least Slack Time Scheduling share a concrete dispatching rules mechanism for production scheduling.
Conceptual neighborHighest Response Ratio Next
Critical Ratio Scheduling and Highest Response Ratio Next share a concrete dispatching rules mechanism for production scheduling.
Related Algorithms
Tags
SchedulingDivide and Conquer