We cut a 45-minute CI pipeline to 12 minutes by measuring every task and solving a knapsack problem to distribute builds across GitHub Actions workers. It worked. It was also the wrong problem: a static assignment is a bet placed before the run, and it cannot stay optimal once the run has better information.
The first version of the build distribution was an LPT scheduler. Sort the tasks by estimated duration, drop each one into the least-loaded worker, ship it. It was thirty lines and it took a 45-minute pipeline down to roughly 12 minutes.
Then we made it worse.
We replaced the heuristic with an exact partition solver: binary-search the smallest capacity that can hold the work, then use a branch-and-bound search to decide which task goes into which worker. We added a hand-maintained file of build durations, a score for every task, a model of worker startup overhead, and a plan that assigned every task before the first runner booted. On paper, the plan was optimal. In production, the headline number barely moved, and the plan was still wrong in the same way the thirty-line version had been wrong.
This is the story of why we solved a knapsack problem when we should have built a queue, and why we chose the knapsack anyway.
This is a companion to the broader monorepo migration case study; the Nx adoption that eventually replaced the static plan with a queue is covered in Part 2.
A fixed assignment is a prediction. A queue is a decision made at the moment you have the information.
The Pipeline We Had
The client was a white-label credit card platform: one product, 26 brands, a React monorepo, a dozen or so apps and packages, and a CI pipeline shared by every team that touched them. Most pull requests changed a small slice of the graph. A few changed a shared package and lit up half the repository.
Change detection gave us the affected subgraph. The problem was not which tasks to run — it was where to run them.
GitHub Actions gave us a matrix. We could declare N workers and assign each of them a list of tasks:
jobs:
plan:
runs-on: ubuntu-latest
outputs:
matrix: ${{ steps.pack.outputs.matrix }}
steps:
- uses: actions/checkout@v4
- id: pack
run: node scripts/pack-builds.js >> "$GITHUB_OUTPUT"
build:
needs: plan
strategy:
matrix: ${{ fromJSON(needs.plan.outputs.matrix) }}
runs-on: ubuntu-latest
steps:
- uses: actions/checkout@v4
- run: node scripts/run-worker.js
env:
TASKS: ${{ toJSON(matrix.tasks) }}That fromJSON is the part people point at when they say the matrix is not really static. It is dynamic in the sense that a previous job can compute the values. It is static in the sense that matters: once the matrix is expanded, every worker knows its assignment, and no worker can take work from another. If worker 2 finishes eight minutes early, it waits. If worker 3 gets a cold npm cache and runs twelve minutes long, everyone waits for worker 3.
We had no shared task queue. We had jobs.
The Plan, in Equations
Let each task have an estimated duration — the number of minutes we expected it to take. With workers, we wanted an assignment that minimises the makespan:
where is the startup cost of a worker. Every task is assigned exactly once. The second term is the weight of the heaviest worker's bin; the plan is only as fast as its slowest bin.
For a fixed capacity , the decision version is: can the tasks be partitioned into subsets, each with total weight at most ? Each worker is a 0/1 knapsack with capacity , so this is repeated knapsack — or, more precisely, bin packing into identical bins. It is NP-hard. For a monorepo's worth of tasks it is also small enough to solve exactly with a bit of branch-and-bound, which is exactly the kind of fact that gets an engineer into trouble.
The feasibility check looked like this:
function tryPack(items, workers, capacity) {
const bins = Array.from({ length: workers }, () => [])
const loads = new Array(workers).fill(0)
const place = (i) => {
if (i === items.length) return true
const seen = new Set()
for (let b = 0; b < workers; b++) {
if (loads[b] + items[i].weight > capacity) continue
if (seen.has(loads[b])) continue // symmetry: equal loads are interchangeable
seen.add(loads[b])
loads[b] += items[i].weight
bins[b].push(items[i].id)
if (place(i + 1)) return true
bins[b].pop()
loads[b] -= items[i].weight
if (loads[b] === 0) break // an empty bin is an empty bin
}
return false
}
return place(0) ? bins : null
}
function pack(tasks, workers) {
const items = [...tasks].sort((a, b) => b.weight - a.weight)
const total = items.reduce((sum, item) => sum + item.weight, 0)
let lo = Math.max(items[0].weight, Math.ceil(total / workers))
let hi = total
let best = null
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2)
const bins = tryPack(items, workers, mid)
if (bins) {
best = bins
hi = mid - 1
} else {
lo = mid + 1
}
}
return best
}For large graphs we fell back to Longest Processing Time first, the greedy heuristic with the comfortable approximation bound. For the sizes we had, the exact search usually finished before the workflow finished parsing.
Choosing the number of workers
The knapsack answers a conditional question: given workers, what is the best partition? The pipeline also needed .
We looped from 1 to 8, solved the partition for each, and scored the result as
where is the per-worker startup estimate and is how much a minute of worker time costs relative to a minute of wall-clock time. The smallest score won. On most affected sets the answer was four workers, which is also the number everyone guesses when they look at the graph. That should have been a warning.
Then we added the rest of the model: a duration for every task, sampled from recent runs and committed to build-times.json; the startup estimate; the worker-count rule. The script emitted one matrix entry per worker, each with a newline-separated list of tasks. It was, by the standards of CI scripts, quite nice.
Why the Plan Was Wrong
The solver was correct. The problem it solved was not the problem the pipeline had.
We knew a static partition would never be truly optimal. Durations are not known in advance and the assignment is made once. What we underestimated was the size of the gap. We expected a few percent. On the workloads that mattered it was thirty to fifty percent.
The rest of this section is the anatomy of that gap.
The objective was a proxy
The knapsack minimises the heaviest bin. The pipeline's makespan is not the heaviest bin. It is the time at which the last task in the longest dependency chain finishes. Dependencies turn a balanced partition into a schedule with holes:
- A worker cannot start a task until every dependency has finished, even if that dependency is on another worker.
- A worker that finishes its bin early cannot help a worker that is still running.
- Two tasks with the same weight can have wildly different downstream effects. A ten-minute
uibuild that unlocks four brands is not the same item as a ten-minute visual-regression suite at the end of the graph.
The partition is a statement about weights. The schedule is a statement about time.
The inputs were stale
The weights came from history. History is a useful prior and a terrible promise.
A new test file changes the duration. A cold cache changes the duration. A flaky suite that retries changes the duration. A dependency bump that invalidates a layer changes the duration for every downstream task at once. We used a median, which smoothed out the outliers and quietly hid the p90 that actually determined the slow runs. And the file itself was maintained by hand, which meant it was accurate for the packages someone had recently touched and approximate for everything else.
The plan was only as good as a JSON file that nobody wanted to own.
The assignment was frozen
This is the structural problem. The plan was computed before the run, from estimates. The run then produced facts. The plan could not use them.
If worker 1 hit a warm cache and finished in four minutes, it could not take the e2e task that worker 4 had not started yet. If worker 4 hit a cold cache and doubled its estimate, worker 1 could not absorb half of worker 4's bin. The only feedback loop was the next pull request.
A queue inverts this. Work is not assigned to workers; workers ask for work. The assignment is computed continuously, from the actual state of the system, by the only component that knows which worker is free: the worker itself.
Over-provisioning was built in
The number of workers had to be chosen before the run. Choose too few and the graph's parallelism is left on the table. Choose too many and you pay for startup and idle time, especially when the affected set is small.
We chose by minimising a modelled cost: startup per worker plus the predicted makespan. The model was reasonable. The variance was not. On a large PR, four workers were not enough; on a small one, four workers were three too many. A queue with a fixed pool can at least keep every worker busy until the queue is empty; a matrix with a fixed assignment pays for the over-provisioning and still leaves workers idle.
The knapsack can be optimal and still slow
This is the part that took the longest to accept. Even a perfect weight partition can produce a terrible schedule. Here is the playground's “three brands” workload, three workers:
- The knapsack finds a 20-minute bin max. That is the optimal weight partition.
- The actual static run takes 42 minutes, because each product branch is split across workers and every step waits for the previous step on someone else's bin.
- A work-conserving queue takes 28 minutes — the critical path, which is also the optimal time for this run.
The plan was not badly solved. It was the wrong plan.
The bound is a bound on the bin-packing objective, not on your pipeline. It says the heaviest bin is within 33% of optimal. It says nothing about the dependency stalls between bins, the retries, the cache misses, or the startup you paid for a worker that ran one three-minute task.
The Playground
The interactive below builds the same picture. Pick a workload, pick a number of workers, and compare three schedules on the same dependency graph:
- Knapsack computes a static partition (exact branch-and-bound for small graphs), assigns every task to a bin, and then simulates the run with dependencies and the realized durations. The solver never uses either.
- Random allocation topologically sorts the graph, ignores every duration, and drops each task into a random bin. It is the baseline the knapsack was meant to beat. The sort is still necessary: dependencies have to be respected, and it gives us a valid order to walk. It just says nothing about how long the walk takes.
- Task queue computes no assignment. Every free worker pulls the ready task with the longest remaining path to the end of the graph. That is a critical-path-first list scheduler — a heuristic, not an oracle, but one that always knows which worker is free.
The nodes show their estimated weight in minutes. When randomness is on, a small badge shows the realized delta. Click a node or use the task picker to change an estimate. The Gantt lanes show what actually happened. Press replay to watch the schedule at time .
Knapsack vs. task queue
same DAG · same 4 workers · knapsack
A change under the shared shell: most brands rebuild, then e2e and visual tests join.
workers
realized = estimate ± random minutes · seed 1
schedule
dependency graph · click a node to edit · badge = realized − estimate
static assignment · each worker owns its bin
knapsack
38.0 min
plan estimated 17.0 min
random allocation
48.0 min
durations ignored
task queue
31.0 min
dynamic, work-conserving
optimal (hindsight)
31.0 min
proven lower bound
optimal in hindsight 31.0 min (proven) · knapsack is +7.0 min / +23% above it
plan built from estimates: 17.0 min bin max · realized run: 38.0 min
critical path 31.0 · total work 68.0 · workers used 4/4 · randomness ±0.0 min
idle above the bound: knapsack 7.0 min · queue 0.0 min
billed worker-minutes: knapsack 120 · queue 90 · knapsack solved exactly
“Optimal (hindsight)” is the best schedule found across the three strategies and an exact partition rebuilt from the realized durations; it is marked proven when it matches the lower bound. The knapsack never sees the realized durations, and random allocation does not even see the estimates. Here the plan gives away 7.0 minutes (23%) to a schedule that knew the run.
The playground leaves worker startup at zero. It was a real cost in the pipeline, but it is a constant tax on every strategy; removing it keeps the comparison about allocation.
Some things to try:
- Start with typical PR at four workers. The knapsack's 17-minute bin max becomes a 38-minute run. The queue finishes in 31 — the critical path and the optimal time for this run. The knapsack is 7 minutes above it. The gap is not a solver bug — it is the cost of assigning tasks before you know when their dependencies finish.
- Switch to three brands at three workers. The static plan is 42 minutes; the queue is 28. The plan balanced the weights almost perfectly and split every product branch in the process. This is the clearest case: the bins are fine; the edges are the problem.
- Switch to random allocation. It is the baseline the knapsack was supposed to beat: topological order, random bins, no durations. On the typical PR at four workers it takes 48 minutes against the knapsack's 38 — the knapsack is meaningfully better here, which is what it bought you. On three brands, random allocation takes 40 minutes and the knapsack takes 42: the weight-optimal partition is worse than scattering the tasks, because it split every product branch. That is the whole failure mode in one number.
- Click a node and drag its estimate. The knapsack re-plans around the new weight; the queue does not care until the task actually runs. Make one task enormous and watch the knapsack sacrifice the rest of the bin to it.
- Turn randomness up to ±4 minutes. The plan is still built from the original estimates; the run uses the jittered durations. The knapsack starts missing, the queue reorders. Hit reroll a few times and watch the gap move even though the plan did not.
- With knapsack selected, read the optimal (hindsight) line. It is the best schedule found with the realized durations, and the rose number is what the plan gave away by deciding too early.
- Switch to one huge app. The queue finishes at the critical path and stops there. Extra workers cannot beat a 16-minute task that everything else waits on. This is the honest limit of the whole exercise: a queue removes artificial waiting, not physics.
- Move the worker count from 2 to 6 and watch the knapsack's makespan jump around while the queue's flattens. Adding a worker changes the partition, and a new partition can split a chain that the old one happened to keep together.
What a Queue Does Differently
A task queue replaces the assignment with a claim:
while (!stopped) {
const task = await queue.claim({ leaseMs: 60_000 })
if (!task) break
try {
const result = await runTask(task)
await queue.ack(task.id, result)
} catch (err) {
await queue.retry(task.id, err)
}
}The important line is the first one. A worker does not ask “what was I assigned?” It asks “what is ready and unclaimed?” When it finishes, it asks again. If it dies, the lease expires and the task returns to the queue. If a task runs long, only that task is late; the other workers keep draining the queue.
This changes the shape of the optimisation. There is no global partition to compute. The scheduler is a policy — which ready task should the next free worker take? — and the policy can be as simple as critical-path-first, or as sophisticated as you like. The system is making a decision with more information than the planner ever had: the current time, the current queue depth, the current worker availability, and the actual completion times of the tasks that have already run.
The queue is not an oracle
It is tempting to say a queue is always optimal. It is not. List scheduling is a heuristic; on some graphs a clairvoyant static schedule can beat a greedy queue. The playground's three workloads happen to favour the queue, but that is not a theorem. The claim is not that a queue solves scheduling perfectly.
The claim is that a queue is never committed to a plan that the run has already invalidated. Every decision is made with the information available at that moment. A static assignment makes all of its decisions with the least information it will ever have.
What it costs to build one
This is the part that kept us on the knapsack for four months.
A queue is not a script. It is a small distributed system:
- A broker or a table with atomic claims, leases, and visibility timeouts.
- Idempotent task execution and retry semantics, because a worker can die mid-task.
- Artifact and cache handling, because the task that produces
dist/and the task that consumes it may run on different machines. - Authentication and network access from CI, plus a story for secrets.
- Cancellation, so a superseded commit does not keep burning workers.
- Metrics, logs, and someone to be on call when the queue backs up at 2 a.m.
GitHub Actions gives you isolated jobs and a matrix. It does not give you a broker, a long-lived worker pool, or a way for job 3 to hand a task to job 1. You can approximate it with a shared Redis, a database table, or an artifacts branch, but then you own the races, the leases, and the cleanup. That is a platform project, not a CI tweak.
Where More Workers Stop Helping
The second chart sweeps the worker count from 1 to 8 and plots the makespan of the knapsack plan and the queue, plus the lower bound: the critical path, or total work divided by workers, whichever is larger. The slider adds randomness to the realized durations; the plan is rebuilt from the original estimates every time.
Where more workers stop helping
makespan vs. worker count · randomness ± 0.0 min
queue at 8 workers
31.0 min
knapsack 35.0 min · 4.0 min gap
queue plateaus at
3 workers
critical path 31.0 min
static plan range
31.0–68.0 min
best at 5, worst at 1 workers
The plan is rebuilt from the estimates for each worker count; randomness changes the realized durations, not the estimates. The queue curve falls until the critical path and then stops. The static curve is not even monotone — a new partition can split a dependency chain, and rerolling the jitter can move either curve. At 8 workers the queue is 4.0 min ahead.
The queue curve falls until it hits the critical path and then goes flat. The static curve is not even monotone: adding a worker changes the partition, and a new partition can be worse for the dependencies than the old one. At eight workers the static plan can be slower than it was at five.
Turn the randomness up and reroll a few times. The queue reorders; the plan cannot. This is the chart I wish we had put on a dashboard in 2022. It would have made the argument better than any amount of solver tuning: the static plan's quality is a function of the number of workers in a way that has nothing to do with how much work there is.
Why We Did It Anyway
I want to be precise about the decision, because “we should have built a queue” is easy to say after the fact.
We had a small platform team, a broken pipeline, and a deadline measured in days. The knapsack script was a one-day change. It required no new service, no security review, no on-call rotation, and no new failure mode in the critical path. It was obviously going to beat the status quo, and it did: 45 minutes to roughly 12.
A queue would have been the right architectural answer and the wrong project for that week. The mistake was not choosing the script. The mistake was staying on it after it had done its job.
We kept improving the static plan instead of replacing it. We added a better solver, a more accurate duration file, a startup model, and a worker-count heuristic. Each change made the plan better on paper. Each change also made the system more complex without changing the fundamental failure mode: the plan was still a prediction, and the run still had better information than the plan.
The exit criterion should have been explicit from day one:
- If the p90 of the predicted-versus-actual gap exceeds 20%, stop tuning the solver.
- If the idle time above the lower bound is larger than the time saved by adding a worker, stop adding workers.
- If the duration file needs manual maintenance more than once a quarter, the model is already stale.
We had those signals. We read them as reasons to improve the model.
What I Would Do Next Time
Timebox the static solution. A knapsack or LPT plan is a good stopgap. Give it an expiration date and a metric that triggers the replacement. “We will revisit this next quarter” is not a trigger.
Measure the gap, not just the makespan. Store the predicted makespan next to the actual one for every run. The difference is the value of the information the planner did not have. If it is small, the static plan is fine. If it is large, no amount of solver tuning will close it.
Keep dependent tasks together. If you must stay static, add affinity: never split a chain across workers unless you have to. This is a constraint the pure weight partition does not know about, and it is often worth more than a better bin balance.
Choose workers by cost, not by makespan alone. With a fixed m, a static plan has no way to use the extra worker that finishes early. With a queue, the marginal worker is useful exactly when the queue is non-empty.
Buy or borrow before you build. The correct fix for us was Nx's distributed task execution and remote cache, which replaced the plan with a queue and made cache hits take tasks out of the schedule entirely. If your stack has a tool that already implements the queue — Nx, Bazel remote execution, Buildkite dynamic pipelines, a hosted runner pool with a work-stealing agent — the build-versus-buy calculation is not close.
If you build it, build the boring parts first. Leases, retries, idempotency, cancellation, and observability. The scheduler policy is the easy part.
| Situation | Static plan is enough | A queue is worth it |
|---|---|---|
| Graph size | A handful of tasks | Dozens to hundreds |
| Duration stability | Stable, cache-warm | Cold caches, flaky tests, variable runners |
| Worker count | 1–3 | 4+ |
| Dependency shape | Wide, shallow | Deep, fan-out/fan-in |
| Time to build | Days | Weeks |
| Failure cost | Retry the workflow | Needs leases and idempotency |
The Actual Lesson
The knapsack was a symptom. The real constraint was that our CI system could describe workers but could not describe work. We had jobs, not a queue, so we turned the jobs into bins and hoped the bins would behave like a queue.
They never will. A bin is a decision made before the run. A queue is a decision made during it. The whole value of the queue is that it gets to use the facts the planner did not have: which worker is free, which task actually finished early, which cache actually hit, which test actually retried.
The 45-minute pipeline was the problem. The knapsack was a very good answer to a slightly different question. The queue was the answer to the actual one.
If your scheduler needs a plan, you do not have a scheduler. You have a rota.
We shipped the rota, learned from it, and replaced it. The replacement was not a better rota. It was a queue.
Related Articles
From Legacy to Monorepo: Migrating a White-Label Credit Card Platform (2021–2024)
A four-year case study of migrating a white-labeled credit card platform from a legacy Angular/C# stack to a React monorepo with single-spa — covering GraphQL BFFs, micro-frontends, build parallelization, and the people problems that matter more than the tech ones.
From DIY Monorepo to Nx: Lessons from a White-Label Credit Card Platform (2024)
Part 2 of a multi-year migration case study. After building a homegrown monorepo toolchain, we adopted Nx — and discovered that its opinionated approach solves some problems elegantly while creating new ones when your apps can't truly be isolated.
Optimizing CI Builds with Docker Layer Caching on TeamCity
How we cut build times from 45 minutes down to 3–10 minutes on an on-premise TeamCity cluster using multistage Docker builds, content-addressed cache keys, and shared filesystem volumes — plus what modern BuildKit unlocks today.