Part 2: Money movement as a job shop
Part 2 of 5 in a deep dive on money movement as an optimization problem, and how AI agents can use scheduling and matching algorithms. Start with Part 1 if you are new to the series.
The job shop problem
The job shop problem has jobs and machines. Each job is a fixed sequence of operations, each operation needs one specific machine for a known time, and each machine handles one operation at a time. The goal is to finish everything as early as possible, or to keep jobs from running late against their due dates.
It is NP-hard once there are three or more machines, a result from Garey, Johnson and Sethi in 1976 (cited in Abgaryan et al.). One small instance shows what that means in practice.
Muth and Thompson publish a 10 by 10 instance
Ten jobs, ten machines. It becomes the field's standard test, known as ft10, and nobody can prove an optimal schedule for it.
Carlier and Pinson close it
Their branch-and-bound method solves ft10 for the first time, 26 years after it was published.
Applegate and Cook solve it in minutes
Their method solves the same instance in under 7 minutes on a Sun Sparcstation 1, and the edge-finding technique behind it ends up in commercial scheduling software.
Most payment scheduling sits in the same place, hard in theory and solvable at the sizes a treasury actually faces.
From factory floor to treasury
The translation to money movement is close to one-to-one.
| Job shop term | In money movement |
|---|---|
| Job | One obligation: a supplier run, a payroll, a marketplace payout, a treasury sweep |
| Operation | One step of that obligation: sanctions screening, FX trade, funding transfer, rail submission, stablecoin on- or off-ramp, confirmation |
| Machine | Anything with finite capacity: a rail window, a compliance review queue, an FX desk, a PSP, a wallet signer |
| Processing time | Seconds on SEPA Instant, minutes for chain finality, hours for a manual review |
| Machine calendar | Operating hours and cut-offs |
| Due date | When the money must arrive, and what lateness costs |
| Shared resource | The balance in each account, spent by outgoing payments and refilled by incoming ones |
Four things make the payments version harder than the textbook one. Machines switch off: an operation that misses T2's 17:00 CET customer cut-off waits until the next business day. Liquidity is a shared resource that every payment draws down, which turns the problem into a resource-constrained schedule, the same family CHIPS works in when it decides which queued payments to release.
Lateness also comes in steps. A payment one minute past the cut-off loses a full business day, and a Friday payroll that misses Fedwire lands on Monday. And some processing times are uncertain: a sanctions hit, a congested chain, an off-ramp partner that pauses withdrawals.
Writing the day down
Written down, a treasury objective for one day looks like this:
In words: pay a penalty w for every obligation j that completes after its due date d, add the fees and FX costs f of the routes chosen, and charge the cost of capital r on the average balance B parked in each account a. Every operation must follow its job's order, fit inside its rail's open hours, and leave each account above its minimum balance.
Open-source constraint solvers model this directly: each operation becomes a time interval, each machine a no-overlap rule, each cut-off a window. The schedule answers when. Before that, someone has to decide which account pays for which obligation, and that is an assignment problem.
Continue to Part 3: Who pays what