Work Order Scheduling: Keep Headroom for What the Factory Is Waiting On

◎ Overview

Operations are assigned to machines late — when at least one of their inputs exists — and an assigned operation holds a reservation on that machine's input and output buffer capacity until its run has consumed its inputs and its outputs have left. Nothing decides how much of a machine's capacity one kind of work may take. Where a machine sits on two paths of a work order, the first kind of work to arrive can take all of it, and the second kind — which the first is waiting on — never gets any.

The answer is a single refusal predicate on assignment: never take the last capacity that a run of a recipe the factory is already waiting on needs. Nothing is reserved on behalf of unassigned work, nothing is assigned early, and no started run is undone. The other half of the guarantee is that a held output always has somewhere to go: its consumer's reservation, or the machine whose demand for it ranks highest — and one machine wants every component kind and makes nothing of it, so it always has room.

Aa Vocabulary

type = shared definition · instance = a particular thing in a particular factory at a particular moment.

Two operations with the same recipe are interchangeable for coverage; two with different recipes are not, even when those recipes use the same process. "Capacity" unqualified always means input and output buffer capacity. "A machine" always means one specific machine, usually named M; a set of machines is always named: an operation's or an entry's eligible machines.

# The scheme's quantities

⊘ The lock

A machine's input and output buffer capacity is released only as the operations occupying it progress: input capacity when a run consumes its inputs, output capacity when the output components leave. Output components leave only once a consuming operation has been assigned with input buffer capacity for them. If every machine able to run a recipe has its capacity held by operations or components whose progress depends — somewhere up or down their work order — on a run of that recipe, nothing on those machines can progress, so that recipe never gets capacity.

It needs no cycle in any work order. It needs only a work order that passes through one machine more than once: a machine feeding itself, a machine the work order comes back to through another, or two branches that rejoin.

The smallest factory that locks

Operations are named recipe + instance: A1 and A2 are the two operations of recipe A in this work order, B1 and B2 the two of recipe B. The number is not a work order id — there is one work order.

Step through it. Only the ledger is consulted — an assignment goes ahead whenever the operation's own reservation fits.

The same lock, two machines

The work order leaves M, passes through N, and comes back to M. Ledger only, as before.

Neither refused operation wants anything its own machine's output holds: B2's ingot is on M, C1's rod is on N. Each machine is full of what the other is waiting for, and no rule that looks at one machine can see it. With the invariant, A1's assignment puts B and C in the needed set, and A2 is refused the moment it is requested, because M would have no headroom for C — the same refusal as above, one hop further from the reason. It is stepped through in the section with the invariant.

≡ The invariant

The check

Assigning operation O to one machine M asks two separate questions.

1. 1The ledger. Does M have free capacity for O's own reservation? If not, O cannot go on M. This is ordinary bookkeeping, not the invariant.
2. 2The invariant. Once O's reservation is taken, is every entry of the needed set still covered? The set is evaluated as if O were assigned: the paths of every operation already assigned, plus O's own. If any entry would be uncovered, O is refused and never joins the set.

The second question is about other operations, not O: O's own reservation fits by question 1, and O is refused when it would take the last headroom some already-assigned operation's path depends on. Nothing is reserved on behalf of unassigned work — the check protects free capacity, and which machine hosts the needed run is decided late, as usual. Refusal is the only action, and the check runs on every assignment.

Eligibility

An operation is eligible for assignment when at least one of its inputs exists — and not while an upstream operation of the same recipe in the same work order is unassigned. A recipe on a cycle can appear twice on one path of a work order, the later run needing what the earlier one makes; if the later run were assigned first, it would hold the machine's room for that recipe while waiting on the run that needs it. The run that comes first in the plan takes the machine first. Nothing is held while waiting, and the earlier run never depends on the later, so the wait always ends.

∴ Why checking at assignment is sufficient

Coverage can break in only two ways: free capacity goes down, or the needed set grows. Both happen only at an assignment or a checked re-plan (Held outputs, rule 3).

A run starting is a wash: the input buffer capacity it releases is exactly what it stops standing for, so coverage is unchanged by it. So if every assignment preserves coverage, coverage holds at every moment. No other trigger is needed.

▶ The same factory, with the invariant

Same recipes, machine, buffers and work order as above. Now every assignment answers both questions, and the needed set is shown after each step.

Step 2 is the whole mechanism. A2's own reservation fits the ledger; it is refused because A1's path needs a B and A2 would take the last headroom a B could use. One assignment refused, nothing assigned early, nothing evicted. Work then runs serially through the kept headroom and never locks.

Two machines, with the invariant

The two-machine factory from above: M, N, and a work order that comes back to M. From the first assignment the needed set reaches across both machines.

Step 7 is the one to read twice. When C1 is assigned, the rod is still physically in N's output, and it is the departing rule — a held component whose consumer is assigned has room reserved at its destination, so it does not count — that keeps B covered on N. It is what lets C1 be assigned at all.

◇ Demand

A machine may want things. A demand says what: I want this many results of this recipe, at a priority, and either the factory may make what is needed for it (make) or may only use components nothing else has claimed (unclaimed only). How a machine picks the number, and when it changes it, is the machine's own business. Most machines want nothing: a smelter runs only operations that other machines' demands were planned down to.

A demand is met by completed runs of its recipe — the arm is met by assembled parts, and a completed run cannot be taken away, so the demand is finished when the count is reached. The one exception is a recipe that only moves a component, K → K: it is met by the K the machine holds, and those can be taken, so that demand is ongoing and refills. That is the whole difference between a storage and an arm. Whatever else a recipe makes is an ordinary held output: claimed by an operation that references it, otherwise surplus. The arm's shavings are surplus.

Two things follow from a demand, and nothing else does:

• Asking. Whenever fewer results meet the demand than it wants, counting the operations already planned for it, the planner adds operations of the recipe to make up the difference. These are ordinary operations: they reference the components they will take, are assigned when an input exists, reserve capacity, and run. For a make demand the planner sources their inputs — from a component the work order may claim if one exists, else from production planned down to sources. For an unclaimed only demand nothing is planned beneath them; each waits for a spare component of its kind to exist.
• Keeping. A demand whose recipe is K → K claims the K the machine holds, up to its count, at its priority. An operation may take one only if its own priority is higher. This is what stops the airlock emptying a storage, and what lets an urgent work order draw on one — after which the storage has one fewer, and asks for one more.

There is no other kind of machine. What the player sees as a production line, a storage or an airlock is a machine with these values:

Demand { recipe, count, priority, policy }
met(d)         = components held,  if d.recipe is K → K
               = completed runs,   otherwise
shortfall(d)   = d.count − met(d) − outstanding(d)
outstanding(d) = operations of d.recipe not yet run; the planner keeps it == shortfall(d)
// a K → K demand claims the machine's held K, up to d.count, at d.priority

The claim is not stored: it is a check, from the demand's count and priority and the held count, when another operation would claim a held component. A component under a demand's claim only ever moves to a higher priority, so this always settles. A smelter has no demand, so its ingots are open to any operation; a storage demanding 7 held ingots at priority 3 keeps its first 7 from operations at 3 or below and loses any of them to one at 10; an 8th is open to all.

Every demand roots a work order. The scheduler never branches on which machine is asking.

⇢ Held outputs

An output stays in the machine's output buffer until it departs. Where it departs to:

1. 1A held output claimed by an assigned operation stays until it departs into that operation's reservation.
2. 2An unclaimed held output — surplus — goes to the highest-priority unclaimed-only demand for its kind with room for it.
3. 3A held output claimed by an operation still in the backlog stays for it until the stall threshold passes. Then the claim is dropped — it is unclaimed and goes as in rule 2 — and that operation's input is re-sourced: from a component the work order may claim if one exists — none references it, and no demand of priority at or above the work order's claims it — else by planning a producer chain. Planning operations into a work order that already has assigned operations is a checked event, like an assignment: it goes ahead only when the needed set with them is covered, and is retried on every release of capacity until it does. Until then the operation has no source for that input and is not eligible for assignment.

The threshold is a duration today; it can be made more sophisticated later — for instance, counted only while a run on that machine is blocked for the space.

There is always a demand

If no operation in a work order wants a held output, some unclaimed-only demand does: one machine wants every component kind at the lowest priority, and its recipe consumes any component kind and makes nothing — a run of it needs no output room, so it can always start, and its input buffer always drains. Every other unclaimed-only demand outranks it, so a component goes there last.

✓ Preconditions

• Buffer sizes. Every machine's input buffer fits the sum of the input counts of the recipes it can carry out, and its output buffer the sum of their output counts. A property of the machine type: a content check, not something the scheduler evaluates.
• Reachability. From every machine, every component kind can reach a machine that wants every component kind and turns it into nothing (i.e. the airlock).

⇒ Corollaries

? Open

• Player edits. Deleting a machine, shrinking a buffer or adding a routing restriction removes capacity without an assignment, so it is the one event that can break the invariant. Needed: re-run the coverage check after an edit and unassign operations that have received nothing until it holds again. Which to unassign first is undecided; last assigned, first unassigned is the candidate.
• Recipe cycles. The eligibility rule prevents the one lock found: a later run of a recipe taking the machine's room ahead of an earlier run it depends on. No argument covers cycles in general.
• Routing restrictions. Eligible machines account for them by construction, but the argument has not been made with restrictions on. Two things to settle: whether refusing an assignment that would leave an entry uncovered can itself lock a restricted factory, and the next item.
• Eligible machines before the producers are known. A planned operation whose producers are not yet assigned does not know where its inputs will come from. Its eligible machines are taken over the routing graph — any machine a possible producer could send to that can also send on to the consumer — per machine pair, cached. Whether that over- or under-approximates in a restricted factory is untested.
• Re-pointing references. Letting an assigned operation take an identical component that another operation references — the sandbox's swap — would let work move sooner. It needs an upstream-first rule to stay lock-free. Later.
• Pre-emption. Undoing the assignment of an operation that has received nothing to free capacity for higher-priority work, or handing components an operation has received to another on the same machine that wants them. Either would let higher-priority work move sooner; neither is needed for any guarantee here, and neither is part of this iteration.