Bin-Packing CI Jobs Across Runner Fleets

A CI queue with 40 pending jobs and three idle GPU runners sitting next to 200 idle CPU runners is not a capacity problem. It is a runner fleet scheduling problem. Most pipeline orchestrators — GitLab CI, Buildkite, GitHub Actions self-hosted runners — still dispatch jobs against static label matches in strict FIFO order. That works when every runner is functionally identical. It falls apart the moment your fleet becomes heterogeneous: some nodes carry GPUs for model-training jobs, some carry high-IOPS NVMe for integration test suites, and the rest are commodity spot instances for linting and unit tests. Label matching alone cannot reason about contention, and FIFO ordering guarantees head-of-line blocking

The fix is to treat pipeline dispatch as a bin-packing problem rather than a queue-drain problem. This article walks through the architecture, the packing algorithm, the admission-control logic, and the failure modes you inherit once you move off naive FIFO dispatch.

#The Head-of-Line Blocking Problem in Heterogeneous Fleets

Consider a fleet with three runner classes: cpu-standard (4 vCPU / 8GB), cpu-highmem (8 vCPU / 32GB), and gpu-a10 (1 GPU / 16 vCPU). A naive scheduler pulls jobs off the queue in submission order and assigns the first available runner matching the job’s label. If job #3 requests gpu-a10 and none are free, most orchestrators either block the entire queue lane or, worse, spin up a new instance regardless of whether cheaper capacity is idle elsewhere. Meanwhile jobs #4 through #40, which only need cpu-standard, sit behind #3 because the queue is a single ordered list rather than a set of independent lanes.

The measurable symptom is pipeline makespan inflation — the wall-clock time from job submission to completion grows non-linearly with queue depth, even though aggregate cluster utilisation stays under 60%. You are not out of capacity. You are out of scheduling intelligence.

#Architectural Breakdown: Resource Vectors and Bin-Packing

Effective runner fleet scheduling requires two things a plain label matcher does not have: a numeric resource vector per job, and a numeric capacity vector per runner. Every job is profiled along dimensions such as CPU millicores, memory MB, GPU count, and expected disk IOPS. Every runner advertises the same dimensions as available capacity. The scheduler’s job is then a classic multi-dimensional bin-packing problem: pack as many job vectors as possible into runner vectors without exceeding any dimension, while minimising the number of bins (runners) left partially idle.

This is structurally identical to the packing logic inside Kubernetes’ kube-scheduler, which filters nodes by predicate (fits) and then scores by priority (best fit). The difference in CI runner fleet scheduling is that jobs are transient, queue depth spikes in bursts around merge windows, and cost sensitivity is higher because CI capacity is frequently pure overhead rather than revenue-generating compute. That changes the scoring function: instead of optimising purely for bin-fill density, you optimise for a weighted combination of fill density, spot-instance cost, and job deadline (branch protection SLAs, merge-train timeouts).

#

Runner Fleet Scheduling as a Multi-Dimensional Bin-Packing Problem

The packing algorithm itself does not need to be NP-hard-optimal — First-Fit Decreasing (FFD) gets you within 11/9 of the optimal bin count for most real-world job-size distributions, and it runs in O(n log n). The sequence is: sort pending jobs by descending resource weight, then for each job scan runners in order of decreasing free capacity and assign the first one that fits. Jobs that fit nowhere are held for the next scheduling tick or trigger a scale-out event.

Where this diverges from generic architectural patterns for stateless service scheduling is state retention: a CI job, once assigned, cannot be rebalanced mid-execution without losing all progress. That makes the initial packing decision far more consequential than in a request-routing context where you can simply retry against a different backend.

#Implementation Logic

A production runner fleet scheduling layer sits between the CI control plane and the runner pool, and operates on a fixed tick interval (typically 5–15 seconds):

• Resource profiling — every job definition carries a declared resource request; unlabelled jobs are backfilled from a rolling 30-day p90 of historical execution telemetry for that job name.
• Capacity snapshot — the scheduler polls the runner API for free capacity per node, tagged by class (on-demand vs spot, GPU vs CPU-only).
• Sort and pack — pending jobs are sorted descending by a weighted resource score; FFD packing runs against the current capacity snapshot.
• Admission control — jobs that would push a runner above a configured utilisation ceiling (typically 85%, leaving headroom for burst memory) are deferred, not force-fitted.
• Scale-out trigger — jobs unassigned after two consecutive ticks trigger a scale-out request against the relevant autoscaling group, scoped to the specific resource class rather than a generic “add more runners” call.
• Feedback loop — actual job duration and peak resource consumption are written back into the telemetry store, correcting future profiling estimates.

#Code and Configuration

Job resource declarations need to be explicit rather than inferred from label matching alone. A typical extension to a GitLab CI job definition looks like this:

1integration-tests:
2 stage: test
3 script:
4 - ./run-integration-suite.sh
5 tags:
6 - runner-fleet-scheduled
7 variables:
8 RESOURCE_CPU_MILLICORES: "4000"
9 RESOURCE_MEMORY_MB: "8192"
10 RESOURCE_GPU_COUNT: "0"
11 RESOURCE_DEADLINE_SECONDS: "900"

The scheduler daemon consumes these variables at dispatch time. A simplified FFD implementation, stripped of the telemetry integration for clarity, illustrates the core packing loop:

1def pack_jobs(pending_jobs, runners, ceiling=0.85):
2 jobs = sorted(pending_jobs, key=lambda j: j.weighted_score(), reverse=True)
3 unassigned = []
4 for job in jobs:
5 candidates = sorted(
6 [r for r in runners if r.fits(job, ceiling)],
7 key=lambda r: r.free_capacity(),
8 reverse=True
9 )
10 if candidates:
11 candidates[0].assign(job)
12 else:
13 unassigned.append(job)
14 return unassigned

Queue depth and makespan should be exported as first-class metrics rather than inferred from CI dashboards. A representative Prometheus query for detecting scheduling degradation:

1histogram_quantile(0.95, sum(rate(ci_job_queue_wait_seconds_bucket[5m])) by (le, runner_class))

A sustained p95 wait time climbing above the job’s own deadline for a given runner_class is the earliest reliable signal that fleet capacity or packing weights need rebalancing.

#Failure Modes and Edge Cases

Bin-packing schedulers trade FIFO simplicity for a different class of failure. The most common is fragmentation: repeated packing of small jobs into partially-filled runners leaves just enough free capacity scattered across the fleet that no single runner can accommodate a large job, even though aggregate free capacity exceeds its requirement. Mitigation is a periodic defragmentation pass — draining and repacking a small percentage of runners during low-traffic windows — or reserving a dedicated runner class purely for large jobs above a size threshold.

Spot instance reclamation is the second major failure mode. A job mid-execution on a spot runner that receives a two-minute reclaim notice has no graceful pause mechanism; it either completes in time or is lost entirely, forcing a full re-run. The scheduler must therefore treat spot capacity as a lower-priority bin reserved for jobs under a configurable duration ceiling, never for long-running builds with expensive setup phases.

Misreported resource requests cause a subtler failure: a job declaring 2GB of memory that actually peaks at 6GB triggers OOM kills on co-located jobs sharing the same runner, not just itself. This is why the feedback loop correcting profiling estimates against actual peak consumption is not optional telemetry — without it, the scheduler’s packing decisions degrade within weeks as declared and actual resource use drift apart.

Finally, watch for oscillation between the scheduler and the autoscaler: if scale-out triggers fire too aggressively on transient queue spikes, and scale-in reclaims capacity just as aggressively once the spike clears, you get a thrashing pattern where runners churn faster than jobs can warm caches, inflating cold-start overhead across the entire fleet.

#Scaling and Security Trade-offs

Moving to weighted runner fleet scheduling introduces trade-offs that need explicit sign-off from platform and security stakeholders, not just performance engineering:

• Solver latency vs optimality — constraint solvers such as CP-SAT produce near-optimal packing but scale poorly past a few thousand pending jobs per tick; FFD remains the pragmatic default for high-churn fleets.
• Multi-tenant isolation — packing unrelated jobs onto the same runner to improve fill density increases the blast radius of a compromised build step; namespace-level cgroup isolation and network policy segmentation become mandatory, not optional hardening.
• Spot cost savings vs re-run cost — spot capacity can cut compute spend by 60–70%, but every reclaimed job re-run consumes queue slots and developer patience; cap spot allocation to job classes under a strict duration ceiling.
• Telemetry retention vs profiling accuracy — a longer historical window improves resource estimate stability but slows the scheduler’s adaptation to genuine workload changes after a dependency upgrade or test suite rewrite.
• Defragmentation cadence vs disruption — frequent repacking improves long-term fill density but forces job migrations that interrupt warm caches; schedule defragmentation only during confirmed low-traffic windows.

None of these trade-offs are free, and none can be resolved purely at the scheduling layer — they require coordinated decisions across the runner provisioning strategy, the security boundary around shared compute, and the cost model your finance stakeholders have signed off on. Treat runner fleet scheduling as a continuously tuned subsystem rather than a one-off migration, and revisit the packing weights every time the underlying job-size distribution shifts materially, because a scheduler tuned for last quarter’s workload mix will quietly degrade under this quarter’s.