Print Farm: Filament-Aware Dispatch, Failed Prints and Maintenance Windows

Print Farm: Filament-Aware Dispatch, Failed Prints and Maintenance Windows

You've picked up the queue software behind the Northside Makerspace print farm: a handful of 3D printers that members submit jobs to. The dispatcher decides which printer prints which job, and when a printer should swap its filament spool. Times are integer minutes, filament is whole grams.

Last Saturday the farm wasted a lot of plastic. Three prints died at about 90% because the spool under them ran out, a rush job sat in the queue for an hour while a lower-priority one was "just waiting for a colour change", and one member swears her job jumped the line because of its name. The farm manager has also filed two follow-ups (PF-212 failed prints, PF-230 maintenance windows). The work comes in three parts, and later parts change rules from earlier ones.

Codebase

How your code is run

run(operations: list[list]) -> list executes the operations in order against a fresh farm and returns one result per operation. Each operation is [name, ts, *args]; ts is the time in minutes. Errors are returned as "error: <code>" strings, never raised.

• stock puts a new spool on the rack. add_printer registers a printer with a bed size (bed, the longest footprint edge in mm), the list of materials it supports, and optionally (null for none) a rack spool to load. The spool must be on the rack and of a supported material.
• A job needs material, color, grams of filament, minutes of printing, and a size (its longest footprint edge in mm). A larger priority number is more urgent. invalid job means grams, minutes or size is <= 0.
• status returns ["waiting"|"printing"|"done", finish], where finish is the minute the job finished (only when done, otherwise null). trace returns one entry per print attempt, [printer_id, start, end, outcome], ordered by (start, printer_id); outcome is "running" (with end null) or "done". queue returns the waiting jobs' ids.
• printer returns the state ("idle", "printing", "swapping"), the id of the loaded spool (null while swapping or empty), and until: the minute the current print or swap ends (null when idle). spool returns ["rack", grams], [printer_id, grams] (a spool being loaded already counts as that printer's) or ["discarded", 0]. stats counts jobs by status; swaps is the number of spool swaps started; makespan is the latest finish minute of any done job (0 if none).
• Ids and colours are case-sensitive non-empty strings. Integers must be real integers (true is not one). A wrong argument count or a wrongly typed argument returns "error: invalid arguments"; an unknown operation name returns "error: unknown operation". An operation that is not a list of at least [name, ts], or whose ts is not an integer or is earlier than the previous operation's, returns "error: invalid arguments" and does nothing at all.

Part 1: Dispatch that respects the filament

Goal. Make the dispatcher follow the farm's dispatch rule exactly. The current code has bugs behind all three of the Saturday complaints (and one more). Find and fix them in the code. Read how time, passes and the rack work before you change anything. Do not change the operation formats.

The rules (this is the intended behaviour):

1. The clock. Every well-formed operation first advances the clock to its ts, even if the operation then fails (that includes unknown operations and wrong argument counts). Advancing means: while some printer has an event (a print finishing or a swap finishing) at a minute <= ts, jump to the earliest such minute T, finish every printer event at T (printers in id order), then run one dispatch pass at T. After the operation itself has been applied (successful or not), one more dispatch pass runs at ts. So an operation at minute 60 sees a print that finishes at minute 60 as already done.
2. A dispatch pass visits the idle printers in ascending printer_id order (plain string comparison, so "p10" comes before "p2"). Each idle printer does at most one of the following, in this order of preference.
3. Start. The waiting job a printer takes is the first one, in dispatch order, that *fits* the printer's loaded spool. Dispatch order is higher priority first, then earlier submission (the order in which jobs were submitted; two jobs submitted in the same minute keep their submission order whatever their ids). A job *fits* the printer when the printer has a spool, the job's material and color equal the spool's, spool.grams >= job.grams (needing exactly what is left is fine), job.size <= bed, and the printer supports the job's material. A job is never started on a spool that cannot finish it.
4. Swap. Only if no waiting job fits the printer's spool does the printer consider a swap. It looks at the waiting jobs in dispatch order and takes the first one that the printer could ever print (size <= bed, supported material) and for which the rack holds a spool with the same material and colour and grams >= job.grams. From the matching rack spools it chooses the one with the fewest grams, ties broken by the lowest spool_id (string order). That spool leaves the rack at once, and the printer's old spool (if any) goes back to the rack at once, unless it has 0 grams, in which case it is discarded. The swap takes 10 minutes (SWAP_MINUTES), during which the printer is swapping with no spool; when it ends the new spool is loaded and the printer is idle (the pass that follows decides what happens next). A lower-priority job that fits the loaded spool therefore goes ahead of a swap that a higher-priority job would need.
5. If neither applies, the printer stays idle until the next pass.
6. When a print finishes, the job's grams are subtracted from the printer's spool. Spools only change when a print ends or a swap happens.

Worked example

[["stock", 0, "s1", "PLA", "red", 500], ["stock", 0, "s2", "PLA", "blue", 300],
 ["add_printer", 0, "p1", 200, ["PLA"], "s1"],
 ["submit", 0, "a", "PLA", "red", 400, 60, 100, 5],
 ["submit", 1, "b", "PLA", "red", 150, 30, 100, 9],
 ["submit", 1, "c", "PLA", "red", 80, 20, 100, 1],
 ["stock", 2, "s3", "PLA", "red", 200],
 ["queue", 3], ["status", 60, "a"], ["status", 70, "c"], ["printer", 85, "p1"],
 ["status", 95, "b"], ["status", 120, "b"], ["spool", 120, "s1"], ["spool", 120, "s3"],
 ["trace", 120, "a"], ["stats", 120]]

returns

[true, true, true, true, true, true, true,
 ["b", "c"], ["done", 60], ["printing", null],
 {"state": "swapping", "spool": null, "until": 90},
 ["printing", null], ["done", 120], ["rack", 20], ["p1", 50],
 [["p1", 0, 60, "done"]],
 {"done": 3, "waiting": 0, "printing": 0, "failed": 0, "swaps": 1, "makespan": 120}]

a starts at once (400 g of 500 g) and ends at 60, leaving 100 g. Then b (priority 9, 150 g) does not fit, but c (80 g) does, so c runs [60, 80), leaving 20 g. At 80 nothing fits; b needs a red spool with at least 150 g, and the rack's best fit is s3. The swap runs [80, 90) (the 20 g spool s1 returns to the rack), then b prints [90, 120) and leaves s3 with 50 g.

Part 2: Failed prints and retries (PF-212)

Goal. Prints fail mid-run (a clog, a bed detach). Add the fail operation, which reports that the print running on a printer just failed, consumes the filament that was already extruded, and re-queues the job with a bump, at most twice.

["fail", ts, printer_id] returns true. Errors, in order: unknown printer, not printing (the printer is idle or swapping).

1. As always, the clock is advanced to ts first, so a print that finishes at exactly ts is already done and fail answers not printing.
2. With elapsed = ts - start of this attempt, the filament used is grams * elapsed // minutes (integer floor) and is subtracted from the spool. The attempt is closed at ts with outcome "failed" and the printer becomes idle.
3. A job may be retried at most twice (RETRY_LIMIT). On its first and second failure the job goes back to waiting with its priority raised by 10 (RETRY_PRIORITY_BUMP), cumulatively. It keeps its original place in the submission order for ties, and it needs its full grams again on whatever spool it next starts on. On its third failure the job is failed for good.
4. status can now answer ["failed", null]; trace outcomes can be "failed"; stats.failed counts failed jobs. The dispatch pass at ts runs after the failure, so the freed printer can immediately start something (the retry included).

Worked example

[["stock", 0, "s1", "PLA", "red", 100], ["stock", 0, "s2", "PLA", "red", 200],
 ["add_printer", 0, "p1", 200, ["PLA"], "s1"],
 ["submit", 0, "a", "PLA", "red", 70, 30, 100, 5], ["submit", 1, "b", "PLA", "red", 20, 10, 100, 8],
 ["fail", 10, "p1"], ["spool", 10, "s1"], ["queue", 10], ["trace", 10, "a"], ["status", 60, "a"]]

returns [true, true, true, true, true, true, ["p1", 77], ["b"], [["p1", 0, 10, "failed"], ["p1", 10, null, "running"]], ["done", 40]].

a fails after 10 of 30 minutes: 70 * 10 // 30 = 23 g are gone (77 left). Its retry has priority 15, which beats b (8), so the printer restarts a at minute 10 and it finishes at 40.

Part 3: Maintenance windows, multi-part jobs and a big backlog (PF-230)

Goal. Printers are taken offline for maintenance, big prints come as several parts on different printers, and the farm's Monday backlog has thousands of jobs. Parts A and B change what "fits" means and what a job is. Re-check Parts 1 and 2 when you are done.

A. Maintenance windows

["window", ts, printer_id, start, end] adds a window [start, end) to a printer and returns true. Errors, in order: invalid arguments (types), unknown printer, invalid window (start < ts or end <= start). A printer may have several windows, overlapping or touching.

1. A printer is in maintenance at minute t if start <= t < end for any of its windows. In a dispatch pass a printer in maintenance does nothing. printer reports state "maintenance" for an idle printer in maintenance, with until = the first minute at which it is no longer inside any window (touching or overlapping windows chain).
2. A job may only start at minute t if it finishes before the printer's next window: let limit be the earliest start of this printer's windows with start > t (none means no limit); then t + minutes <= limit is required. Finishing exactly at the window's start is allowed.
3. A swap obeys the same rule. It is only started at t if t + 10 <= limit, and for the job J chosen in rule 4 of Part 1 it must also hold that t + 10 + J.minutes <= limit. The first job in dispatch order that satisfies this, is printable by the printer and has a matching rack spool is the swap's target.
4. This tightens what "fits" means in Part 1: a job that cannot finish before the window is not startable. If no waiting job is startable, the swap rule applies as stated above.
5. A window never interrupts a print or swap that is already running; the printer simply stays offline once it is free.
6. Window ends are events. At the end minute of every window the farm runs a dispatch pass, exactly like it does when a print finishes (and it is merged with other events at the same minute).

Worked example

[["stock", 0, "s1", "PLA", "red", 1000], ["add_printer", 0, "p1", 200, ["PLA"], "s1"],
 ["window", 0, "p1", 100, 120],
 ["submit", 60, "long", "PLA", "red", 10, 50, 100, 5], ["submit", 60, "short", "PLA", "red", 10, 30, 100, 1],
 ["status", 95, "short"], ["printer", 100, "p1"], ["status", 119, "long"],
 ["printer", 120, "p1"], ["trace", 200, "long"]]

returns [true, true, true, true, true, ["done", 90], {"state": "maintenance", "spool": "s1", "until": 120}, ["waiting", null], {"state": "printing", "spool": "s1", "until": 170}, [["p1", 120, 170, "done"]]].

long (priority 5) would end at 110, past the window at 100, so it cannot start at 60; short can (it ends at 90). At 120 the window ends and long starts.

B. Multi-part jobs

["submit_set", ts, job_id, priority, parts] submits one job made of 1 to 8 parts; each part is [material, color, grams, minutes, size]. It returns true. Errors, in order: invalid arguments (parts not a list, or a part not a list of 5, or wrong types), invalid job (no parts, more than 8, or a part with grams, minutes or size <= 0), duplicate job (job_id already used by any submission).

1. Every part is an independent entry in the waiting list with the set's priority and consecutive submission order (part 1 first). Parts are labelled "<job_id>/1", "<job_id>/2", ... in queue; a plain submit is a one-part job labelled with its id. Parts are dispatched like any other job and may print at the same time on different printers, in any order.
2. status of a job: ["failed", null] if it has failed; else ["done", finish] when every part is done (finish = the latest part end); else ["printing", null] if any part is printing; else ["waiting", null]. trace lists the attempts of all its parts, ordered by (start, printer_id). stats counts jobs, not parts.
3. Failures (Part 2) apply per part: each part has its own retry count and priority bump. When a part fails for the third time the whole job is failed: its parts that are still waiting are removed from the queue and never print. Parts already printing continue (and their filament is accounted normally when they finish or fail), but a part of an already-failed job that fails is never retried.

["submit_set", 0, "set1", 3, [["PLA","red",50,30,100],["PLA","red",60,45,100],["PLA","blue",20,20,100]]] on a farm with a red printer p1 and a blue printer p2 prints part 1 on p1 at 0, part 3 on p2 at 0 and part 2 on p1 at 30; the job is done at 75.

C. Bulk import (scale)

["bulk_submit", ts, prefix, count, material, color, grams, minutes, size, priority] submits count jobs at once, "<prefix>-1" .. "<prefix>-<count>", in that order, and returns count. color is either a string or a non-empty list of strings; job k (1-based) uses color[(k - 1) % len] for a list. Job k needs grams + k % 4 grams and minutes + k % 3 minutes; size and priority are the same for all. Errors, in order: invalid arguments, invalid job (count < 1, or grams, minutes, size <= 0), duplicate job (if any generated id already exists nothing is created).

Example: ["bulk_submit", 0, "k", 5, "PLA", "red", 10, 20, 100, 1] creates jobs needing 11, 12, 13, 10, 11 g and 21, 22, 20, 21, 22 minutes. On one idle printer with enough filament they run back to back, finishing at minute 106.

The Monday backlog is thousands of jobs submitted with a handful of bulk_submit calls, with six printers working through them and constantly swapping spools. The final tests run on inputs of that size; the tests have a time limit and an implementation that re-sorts or re-scans the whole waiting list for every dispatch will time out.

Notes

• Everything is deterministic: no wall clock, no randomness, and no dependence on dict or set order.
• Keep each rule in one place. Several rules above are about the *same* decision made at different times (when a printer finishes, when a job is submitted, when a window ends).