Scheduling a fleet that cannot wait

A fleet scheduler decides which machine does what, and when. Put that way it sounds like solved territory — scheduling is one of the oldest problems in computing and the literature behind it is deep. Most of that literature transfers badly here, for one reason: the work items have bodies.

Work in a facility has a place. Getting to it costs time and charge that come out of the same budget as the work itself, and the trip occupies aisles that other machines need. The prerequisites are physical rather than logical, so a task is not ready because a flag says so but because the tote is actually at the station and the fixture is actually free. The resources being allocated include shared space and shared infrastructure — a charger, a lift, a door, a single-width aisle — which behave nothing like a pool of interchangeable workers. And a task that sits in a queue can go stale on its own, because the world it was planned against kept moving while it waited.

None of this makes the problem quantitatively harder. It changes what a correct answer is.

Work that has a location

A job in a compute cluster can run wherever a suitable machine exists, and choosing badly costs efficiency. A task on a floor is a commitment to send a physical object across a shared space. Assigning it to a machine on the far side of the building spends minutes of travel, depletes charge that will be needed later, and puts a moving obstacle into corridors that other machines were planning to use. The cost of a bad assignment is not paid by the scheduler; it is paid by every machine near the route.

The shared resources are stranger still. Space is a resource with geometry and exclusivity, and its availability depends on who else is moving and where they intend to go. A charger is a resource with a queue whose service time depends on the state of the thing queuing for it. A lift or a door is a resource that gates whole regions, so contention for it propagates far beyond the machines actually waiting at it.

Staleness closes the loop. A task admitted against the state of the building at the start of a shift may be unexecutable by the time a machine is free to take it, because the pallet moved, the lane is blocked, or the machine that was the obvious candidate is now on charge. A scheduler that treats its queue as durable truth will dispatch machines against a world that no longer exists. The queue has to be understood as a set of intentions, re-validated at dispatch against current state, and the cost of that re-validation is part of the scheduler's own budget.

Objectives that genuinely conflict

Ask what a fleet scheduler is optimizing and there is no single honest answer. Throughput matters, because the facility has work to finish. Deadline adherence matters, because some of that work is tied to a line, a truck, or a procedure. Charge state matters, because a machine that runs itself flat mid-task becomes an obstacle. Wear matters, because duty cycle is a maintenance cost that arrives later. Fairness across machines matters for the same reason, and also because an operator who watches one robot do everything will stop trusting the system.

These conflict structurally, not incidentally. Chasing throughput means deferring charging and running machines hot, which spends charge margin and wear. Holding deadlines usually means keeping slack in the fleet, which looks like idle capacity to anyone watching a utilization chart. Spreading wear evenly costs throughput directly and immediately.

A single scalar objective can express any of these tradeoffs, and doing so is a reasonable implementation technique. But expressing a tradeoff is not the same as being accountable for it. The interesting engineering is not in the weighted sum. It is in what the scheduler does when it cannot satisfy all of these at once, and in whether that behavior was chosen deliberately or is simply what the implementation happened to do.

The honest refusal

A scheduler that accepts everything it is offered has not solved a capacity problem. It has converted one, and converted it into a worse category.

Accepting work the facility cannot complete on time produces missed deadlines spread thinly across the fleet. On a floor, a missed deadline is not a slow page. It is a machine holding a position it should have cleared, a handoff that arrives after the thing it was meant to meet, and an operator improvising a workaround inside a space where machines are moving. A capacity shortfall silently becomes a reliability problem sitting next to a safety boundary.

So admission control belongs at the center of the design rather than at its edge. The scheduler should be able to decline work at the moment it is requested, visibly, with the reason attached and the constraint named. A facility told that a request does not fit in the window it was asked for can respond usefully — reschedule it, split it, defer it, add capacity. A facility told that the request was accepted and then discovering hours later that it was not honored has been denied the information it needed while there was still time to act on it.

Admission control also has to be honest about what capacity means. It is not the sum of what the machines can do. It is bounded by the shared resources they contend for, and by the fact that coordination overhead grows as a fleet approaches saturation rather than staying flat. A scheduler that admits against nameplate capability will find the last increment of accepted work costs several times what the arithmetic promised.

Degradation order is a decision, not an outcome

Every facility is over-subscribed sometimes — a surge, a machine out of service, a lane closed for maintenance. Something has to give. The question is what gives first, and that has to be a designed and declared ordering rather than a property that emerges from queue discipline and timeout values.

Emergent degradation is the common failure, and it has a predictable shape. Under load, the first property to break is whichever one had the least explicit protection in the implementation, and that is almost always timing, because timing is the guarantee people write down least often. Nobody decided that. It is an accident of where the retry loops were.

A designed order runs the other way. Throughput ambitions go first, because a slower facility is a working facility. Then deadlines on work not yet started, which can be renegotiated while it is still cheap. Then optional and background activity — opportunistic repositioning, non-urgent charging, data movement that can happen later. Then fairness, which is real but survivable. What goes last, and what the rest of the ordering exists to protect, is timing for machines already in motion. A machine executing a committed motion through claimed space has to keep its coordination guarantees, because withdrawing them halfway is exactly the situation where the consequence stops being economic and becomes physical.

The ordering also has to be legible from outside. When the system sheds, the facility should be able to see what it lost and why, in those terms.

The average machine does not exist

Scheduling is usually evaluated with averages: mean wait, mean utilization, mean time to completion. Those are the right statistics for a batch system, where the aggregate output is the product.

A fleet does not work that way. Its observable behavior is set by its worst-served machine — the one that waited longest at the charger, the one whose claim on a lane was denied repeatedly, the one that has been stopped for a while waiting on a decision. A fleet that is fine on average still contains a machine that is not fine, and that machine is standing in a doorway. Nobody watching the floor experiences the mean.

The design consequence is that the scheduler's guarantees have to be stated per machine and measured at the tail. It is the difference between a system that is usually responsive and a system that can say something true about its worst case, and only the second one can be reasoned about by the people who have to work around it.

Where the scheduler has to run

Placement follows from the inputs and the timescale. The scheduler arbitrates local shared resources on a cadence close to the machines' own, reading the shared world model and the live state of the fleet — all of which exists inside the building. Reaching outside for any of it would add a round trip and a failure mode to every decision.

It also has to keep working when the fleet plane is unreachable, which for an air-gapped or intermittently connected site is the normal condition rather than an outage. A facility whose machines stop coordinating because a wide-area link dropped never had autonomy; it had remote control with extra steps. So the scheduler runs on the facility plane, takes its policy from above as signed artifacts, and requires nothing from above while it operates.

What none of this settles is scale. Coordinating a large mixed fleet while keeping the worst-served machine inside its timing bound is an open problem, named as one on the architecture page. Admission control and a declared degradation order are the parts of the answer we are most confident belong in the design. They are not the same thing as having finished it.