Priority Queue Design for Repair-Order Dispatch

When a shop has more open repair orders than mechanics, the order in which those orders are pulled is a compliance decision, not a scheduling convenience. A repair order carrying an out-of-service (OOS) or critical defect must preempt every routine job, because the vehicle behind it is barred from dispatch under 49 CFR § 396.11©(2) until the defect is corrected and certified. At the same time, a low-severity order that sits untouched for a week while newer critical work jumps ahead of it must eventually rise, or a minor brake-light defect quietly ages into a roadside violation. This page designs a heap-based priority queue that orders repair orders by a composite key — severity band first, then age, then SLA deadline — and guarantees both properties: critical work always preempts routine work, and no order starves. It feeds the assignment logic in Mechanic Assignment & Workload Balancing, and the severity bands it orders on are the 0–100 tiers set by the Severity Scoring Algorithms for DVIR Defects engine.

The queue does not decide severity and it does not clear a hold; it decides sequence. The canonical bands remain 0–34 minor, 35–69 major, 70–100 critical, with any DOT_OOS_CRITERIA defect held to a critical floor of 70. A critical order is dispatched to a mechanic ahead of all major and minor work regardless of how long the routine work has waited, and the OOS hold on the underlying vehicle stays in force independent of the queue — the queue accelerates the repair, it does not authorize the truck to move.

• Python 3.10+ with the stdlib heapq and itertools.count for a monotonic tie-breaker, and dataclasses for an ordered priority record.
• A classified repair order — each order carries severity_band, its severity_score, an enqueued_at timestamp, and an sla_deadline.
• The canonical bands — 0–34 minor, 35–69 major, 70–100 critical; a DOT_OOS_CRITERIA defect is always critical.
• A monotonic clock source — use time.monotonic() or an injected clock for aging so wall-clock adjustments never reorder the queue.

heapq is a min-heap, so the smallest tuple is popped first. Encode severity as a band rank where critical is 0, and negate age so an older order sorts ahead of a newer one within the same band. A monotonic sequence number is the final element: it guarantees a total order so two orders with identical keys never compare their (unorderable) payloads, and it makes ordering stable and deterministic.

from dataclasses import dataclass, field
from itertools import count

# Lower rank = higher priority. Critical is popped before major before minor.
BAND_RANK = {"critical": 0, "major": 1, "minor": 2}
_seq = count()  # process-wide monotonic tie-breaker


@dataclass(order=True)
class PriorityKey:
    band_rank: int
    neg_age: float          # negative age: older -> smaller -> higher priority
    sla_deadline: float     # earlier deadline -> smaller -> higher priority
    seq: int = field(default_factory=lambda: next(_seq))


def make_key(band: str, age_seconds: float, sla_deadline: float) -> PriorityKey:
    return PriorityKey(BAND_RANK[band], -age_seconds, sla_deadline)

Never let the heap compare repair-order payloads. Push a (key, order) pair where only the key is comparable, and keep the order object out of the comparison entirely by making the key sort first and total. A frozen order record keeps the payload immutable while it waits.

import heapq
from dataclasses import dataclass


@dataclass(frozen=True)
class RepairOrder:
    order_id: str
    vehicle_vin: str
    severity_band: str      # "critical" | "major" | "minor"
    severity_score: int
    enqueued_at: float      # monotonic seconds
    sla_deadline: float     # monotonic seconds


class DispatchQueue:
    def __init__(self) -> None:
        # Each entry: (PriorityKey, RepairOrder). Only the key is compared.
        self._heap: list[tuple[PriorityKey, RepairOrder]] = []

    def push(self, order: RepairOrder, now: float) -> None:
        age = now - order.enqueued_at
        key = make_key(order.severity_band, age, order.sla_deadline)
        heapq.heappush(self._heap, (key, order))

    def pop(self) -> RepairOrder | None:
        if not self._heap:
            return None
        return heapq.heappop(self._heap)[1]

    def __len__(self) -> int:
        return len(self._heap)

A pure band-first ordering starves low-priority work: as long as critical orders keep arriving, a minor order never reaches the front. Introduce aging — periodically re-key waiting orders so an order that has waited past a band-specific promotion interval moves up a band in the ordering (without changing its actual severity or its compliance obligation). Rebuild the heap from the re-keyed entries so the promotion takes effect on the next pop.

# How long an order may wait before it is promoted one band in ORDERING only.
PROMOTE_AFTER = {"minor": 5 * 86_400, "major": 86_400}  # seconds


def effective_rank(order: RepairOrder, now: float) -> int:
    """Band rank after aging. Never promotes past critical (rank 0)."""
    base = BAND_RANK[order.severity_band]
    waited = now - order.enqueued_at
    threshold = PROMOTE_AFTER.get(order.severity_band)
    if threshold is not None and waited >= threshold:
        return max(0, base - 1)  # rise one band; critical is the ceiling
    return base


def reheapify_with_aging(queue: DispatchQueue, now: float) -> None:
    """Re-key every waiting order so starved orders rise. Deterministic in `now`."""
    rekeyed: list[tuple[PriorityKey, RepairOrder]] = []
    for _, order in queue._heap:
        age = now - order.enqueued_at
        key = PriorityKey(effective_rank(order, now), -age, order.sla_deadline)
        rekeyed.append((key, order))
    heapq.heapify(rekeyed)
    queue._heap = rekeyed

When the tuning layer promotes a new threshold registry, an order’s band can change under it. Do not mutate heap entries in place — that corrupts the heap invariant. Instead, re-key the affected orders and re-heapify, so a re-tuned severity is reflected atomically on the next pop rather than leaving a stale key buried in the heap.

def retune_bands(queue: DispatchQueue, reband: dict[str, str], now: float) -> None:
    """Apply new bands from a re-tuned registry, then rebuild the heap."""
    rebuilt: list[tuple[PriorityKey, RepairOrder]] = []
    for _, order in queue._heap:
        band = reband.get(order.order_id, order.severity_band)
        updated = RepairOrder(
            order.order_id, order.vehicle_vin, band, order.severity_score,
            order.enqueued_at, order.sla_deadline,
        )
        age = now - updated.enqueued_at
        rebuilt.append((make_key(band, age, updated.sla_deadline), updated))
    heapq.heapify(rebuilt)
    queue._heap = rebuilt

Prove the three guarantees: critical preempts minor no matter the arrival order, aging promotes a starved order, and equal keys pop in a stable, deterministic sequence. Run these under pytest in CI.

import pytest


def _order(oid: str, band: str, enqueued: float, sla: float = 1e9) -> RepairOrder:
    score = {"critical": 90, "major": 50, "minor": 20}[band]
    return RepairOrder(oid, "1FUJGLDR1CLBP8834", band, score, enqueued, sla)


def test_critical_preempts_minor_regardless_of_arrival():
    q = DispatchQueue()
    q.push(_order("minor-1", "minor", enqueued=0.0), now=100.0)
    q.push(_order("crit-1", "critical", enqueued=99.0), now=100.0)
    assert q.pop().order_id == "crit-1"  # newer critical still wins


def test_aging_promotes_a_starved_minor_order():
    q = DispatchQueue()
    q.push(_order("minor-old", "minor", enqueued=0.0), now=0.0)
    q.push(_order("major-new", "major", enqueued=6 * 86_400), now=6 * 86_400)
    # After 6 days the minor order has aged past its 5-day promotion interval.
    reheapify_with_aging(q, now=6 * 86_400)
    assert q.pop().order_id == "minor-old"


def test_equal_keys_pop_in_insertion_order():
    q = DispatchQueue()
    for i in range(5):
        q.push(_order(f"m{i}", "major", enqueued=0.0), now=0.0)
    popped = [q.pop().order_id for _ in range(5)]
    assert popped == ["m0", "m1", "m2", "m3", "m4"]  # seq keeps it stable


def test_aging_never_promotes_past_critical():
    o = _order("minor-ancient", "minor", enqueued=0.0)
    assert effective_rank(o, now=999 * 86_400) == 1  # rises to major, not critical

• Floating-point priority ties. Deriving a single float priority (for example band * 1e6 + age) invites two distinct orders to compare equal, at which point heapq tries to compare the RepairOrder payloads and raises TypeError. Use a structured, integer-anchored tuple with an explicit monotonic seq element so no two entries ever tie on the full key, and the payload is never compared.
• Unbounded growth. A queue that only pushes grows without limit if orders are re-keyed by re-inserting rather than replacing, leaving stale duplicates behind. Rebuild the heap in place with heapify when re-keying (as the aging and re-tune steps do) rather than pushing a second copy, and drop tombstoned entries on pop if you use lazy deletion.
• Re-prioritization corrupting the heap. Mutating a PriorityKey already inside the heap breaks the heap invariant silently — subsequent pops return the wrong order. Never edit an entry in place; re-key into a fresh list and heapify, so the structure is always rebuilt from valid keys.
• Aging a compliance band, not just the ordering. Aging must promote an order’s position in the queue, never its actual severity_band or its compliance obligation. A minor defect that ages to the front is still a minor defect for the audit record; only its dispatch sequence changed. Keep the promoted rank in the key and leave the stored band untouched, and never let aging manufacture a critical or an OOS status that the scoring engine did not assign.

• Mechanic Assignment & Workload Balancing — the assignment layer this queue feeds ordered work into.
• Severity Scoring Algorithms for DVIR Defects — sets the 0–100 bands the queue orders on.
• Dynamic Threshold Tuning for Fleet Types — the source of the re-tuned bands that trigger re-prioritization.
• Out-of-Service Criteria and OOS Hold Triggers — the hold that stays in force on the vehicle while its order moves through the queue.

Part of the Mechanic Assignment & Workload Balancing guide. Back to Defect Classification & Repair Order Routing.