PaperlayerView exact revision on arXiv

Source-linked AI summary

BOLT: Multi-Bottleneck Bound-Guided Learning for Flexible Job-Shop Scheduling with Time Lags and Resource-Coupled Transport

Ziheng Zhang, Wei Zhang, Yunyi Zhao, Zuming Liu, Wei Zhou, Boon Ping Gan

arXiv:2610.22433v1cs.LGmath.OC

TL;DR

When a scarce vehicle fleet makes transport waits depend on the schedule, BOLT guides dispatch with a certified bound combining chain, machine-capacity, and fleet-capacity relaxations. On the tested PPVC instances, explicit coupling helps most under high fleet load, and BOLT improves on dispatching-rule baselines across most zero-shot production batches.

  • Problem

    When a scarce fleet moves jobs between stations, transport waits depend on the schedule, so fixed delays do not represent fleet contention.

    Source: §I · p. 1

  • Method

    BOLT takes the maximum of chain, machine-capacity, and fleet-capacity lower bounds, using bound changes as rewards and candidate-specific bound increases as action prices.

    Source: C. Certified Action Prices · p. 6, §VII · p. 12

  • Results

    Across five zero-shot 50- and 80-module batches, BOLT beat the best dispatching-rule pair on four; in the three-vehicle 80-module batch, mean makespan was 13.0% below that pair and 4.2% below hour-budget CP-SAT.

    Source: §I · p. 2

  • Takeaways & Limitations

    BOLT makes decisions in 2.3–5.9 ms per event on one processor core and re-plans after disruption in seconds.

    Source: §I · p. 2

Abstract

from arXiv · show

Flexible job-shop scheduling becomes resource-coupled when a scarce vehicle fleet moves jobs between stations, because the schedule sets the transport waits. BOLT (bound-oriented learning for transport-coupled scheduling) builds a lower bound from chain, machine-capacity, and fleet-capacity relaxations. The bound equals the makespan at termination, so its per-step changes form a reward that sums to a constant minus the makespan. Because it never exceeds the attainable makespan, each candidate's bound increase is a proven rise of the makespan floor, which the policy reads as a price. The root bound certifies a completed schedule's suboptimality gap without a solver. On industry-motivated 10-module prefabricated-construction instances, explicit transport coupling outperforms a transport-penalty policy in every tested cell where loaded moves occupy at least 66% of fleet time and in none at or below 56%. Across five zero-shot 50- and 80-module production batches, BOLT outperforms the best dispatching-rule pair on four and the penalty policy on the three with long moves. In the three-vehicle 80-module batch, its mean makespan is 13.0% below the best pair and 4.2% below an hour-budget constraint-programming solver whose proven gap averages 34%. BOLT decides in 2.3-5.9 ms per event on one processor core and re-plans a disruption in seconds.

I. Introduction

When a scarce fleet sets schedule-dependent transport waits, BOLT combines certified bottleneck bounds with learning to guide machine and vehicle decisions. On the tested PPVC instances, the benefit of explicit transport coupling depends on fleet load, while prior methods do not provide the same certified learning signal.

I. Introduction

  • A scarce fleet makes transport waits schedule-dependent: machine decisions set when requests arise, while fleet availability determines when the next operation can start.Prior prefabrication and learning studies omitted transport or represented it as a fixed surcharge or transfer delay, while bound-guided methods did not model an explicit vehicle resource.Source: §I · pp. 1–2
  • BOLT’s certified multi-bottleneck bound supports objective-faithful rewards, candidate-specific action prices, and a solver-free bound on a completed schedule’s relative suboptimality gap.Its fleet-capacity term also strengthens CP-SAT’s lower bound in tested one-vehicle cells.Source: §I · pp. 2–3
  • At the 10-module training size, explicit coupling shortened makespan in every tested cell at or above 66% loaded utilization, while a transport-penalty policy was adequate at or below 56%; across five zero-shot production batches it beat the best dispatching-rule pair on four.In the three-vehicle 80-module batch, mean makespan was 13.0% below the best pair and 4.2% below hour-budget CP-SAT, whose proven gap averaged 34%.Source: §I · p. 2
  • The study uses deterministic PPVC instances from an industry-motivated generator, not plant production records, and does not report a plant deployment.Processing, waiting, and travel times are assumed known before scheduling.Source: §I · p. 2
  • The paper formalizes flexible job-shop scheduling with machine-free time lags and a finite vehicle fleet, including vehicle seizure during moves and destination-machine reservation in transit.Its delay-semantics taxonomy distinguishes resource-coupled transport from machine-free and machine-side delays.Source: §I · p. 2

II. Related Work

  • Prior transport-aware learning either uses designed rewards or omits aggregate fleet capacity from its bound, while per-instance search does not provide a reusable analytic bound for reward, action guidance, and solver propagation.The paper positions BOLT as combining certified multi-bottleneck bounds with certified action pricing, a solver-free gap bound, and solver strengthening.Source: §II · p. 3

III. Resource-Coupled FJSP with Time Lags

The paper formulates a flexible job shop with machine-free time lags and transport served by a finite vehicle fleet. It distinguishes transport’s schedule-dependent resource-coupled delay from waits whose durations are fixed by the instance.

A. Formulation

  • In FJSP-TL-T, jobs move through operation chains on eligible machines, with machine-free lags, and a homogeneous finite fleet serves inter-cell moves.Each transport task occupies one vehicle for the full move, including empty repositioning and loaded travel.Source: §III · p. 3, A. Formulation · p. 4
  • A transport task arises when successive operations use different cells; the job becomes ready after its preceding operation and lag, and a same-cell successor requires no transport.The destination machine is committed when the task is released.Source: A. Formulation · p. 4

B. A Taxonomy of Scheduling Delays

  • Machine-free and machine-side delays have instance-fixed durations, but resource-coupled transport blocks the job and seizes a third resource whose schedule-dependent availability sets the effective wait.A per-transition minimum can remain admissible yet be arbitrarily loose because it ignores fleet competition, motivating an aggregate fleet-capacity bound.Source: B. A Taxonomy of Scheduling Delays · p. 4

C. Scope and Modeling Assumptions

The model isolates scheduling with known processing, waiting, and travel times and a shared fleet, then constructs schedules through machine- and vehicle-class events. Its partial-schedule state supports both bound evaluation and re-planning after a breakdown.

C. Scope and Modeling Assumptions

  • The scope excludes sequence-dependent setups, road networks, congestion, routing, heterogeneous fleets, station-buffer limits, and maximum time lags; station buffers are assumed unbounded.Blocking machines and curing stages that seize a capacity-limited resource are also outside the model.Source: C. Scope and Modeling Assumptions · p. 4

D. Decision Model

  • Machine-class events commit eligible operation-machine pairs, while vehicle-class events dispatch a free vehicle to one pending released task.A different-cell machine commitment reserves the destination machine idle until the job arrives; construction terminates at the realized makespan.Source: D. Decision Model · pp. 4–5

A. Instance, State, and Completion Classes

  • The bound is evaluated on a partial schedule whose operations are realized, in transit, or uncommitted, using machine busy times, vehicle free times, and job-ready times.The environment’s constructive completion class respects precedence, lags, machine capacity, reservation, and service timing; CP-SAT searches a larger space that drops the reservation.Source: §IV · p. 5, A. Instance, State, and Completion… · p. 5
  • The machine-capacity component requires type-pure eligibility, but omitting it leaves the chain and fleet components with all three stated guarantees for arbitrary eligibility sets.The type-pure assumption means eligible machines for an operation share a cell and are interchangeable within an eligibility group.Source: A. Instance, State, and Completion… · p. 5

B. Three Bottleneck Relaxations and Their Composition

BOLT takes the maximum of chain, machine-capacity, and fleet-capacity relaxations to bound the makespan still attainable from each partial schedule. Admissibility and terminal tightness give the bound both a meaningful learning signal and a fleet-aware lower bound.

B. Three Bottleneck Relaxations and Their Composition

  • The fleet-capacity relaxation aggregates mandatory loaded transport work across vehicles, closing cases where chain and machine bounds stay fixed while one vehicle serializes more jobs’ moves.For the stated one-vehicle example, the root fleet bound is Kτ, matching the mandatory workload of K loaded moves.Source: B. Three Bottleneck Relaxations and… · p. 5
  • The fleet component reuses the certified bound as reward, action price, schedule certificate, and solver constraint.The paper identifies this reuse, including admissibility at reachable states with destination reservations, as an addition to aggregate transport-workload reasoning.Source: B. Three Bottleneck Relaxations and… · p. 6

C. Guarantees

  • The composite bound takes the maximum of the chain, machine-capacity, and fleet-capacity terms, and each component is at most the makespan of every feasible completion.The maximum selects among the bottlenecks without a tuned weight.Source: C. Guarantees · p. 6, B. Three Bottleneck Relaxations and… · p. 6
  • At termination the bound equals realized makespan, so undiscounted rewards from its per-step decreases sum to a constant minus makespan and maximize the return by minimizing makespan.Admissibility also makes each positive action price a proven rise in the makespan floor, while the root value bounds the optimum.Source: C. Guarantees · p. 6

D. Certified Action Prices and the Root Certificate

BOLT uses an admissible multi-bottleneck bound to guide candidate commitments and certify schedule quality without a solver. Bound differences also provide objective-faithful learning rewards, while an optional analytic credit does not improve scheduling.

D. Certified Action Prices and the Root Certificate

  • The root bound certifies a completed schedule’s relative suboptimality gap without running a solver.The certificate applies at the root; reservations can make the bound exceed the reservation-free optimum once an operation is in transit.Source: D. Certified Action Prices and the… · p. 6

B. Objective-Faithful Bound-Difference Reward

C. Certified Action Prices

D. Optional Analytic Credit

E. Policy Realization and Deployment

BOLT uses two event-class policy heads over a shared encoder, with separate output layers that support independent adjustment or rollback. Its evaluation uses an industry-motivated PPVC-T benchmark and compares the approach with dispatching, search, learned, and solver baselines.

E. Policy Realization and Deployment

  • Two actor heads handle machine-class and vehicle-class events over a shared dual-attention encoder, with one head acting at each event.Vehicles enter the machine-side attention stream as a third node set; operation nodes retain lag channels and both node types gain anticipatory transport channels.Source: E. Policy Realization and Deployment · p. 7
  • Separate output heads let a plant fine-tune, validate, or roll back one decision class while the other head stays fixed.The encoder is shared, so changing it affects both classes; the structural property’s value is not measured in the experiments.Source: E. Policy Realization and Deployment · p. 7

A. Experimental Setup

  • The PPVC-T benchmark uses four 22-operation routing classes, a 3 × 3 station-cell layout, and a homogeneous fleet; production batches span 50 and 80 modules.Instances follow published PPVC process documentation but are not plant production records.Source: A. Experimental Setup · pp. 7–8
  • BOLT outperforms the transport-penalty anchor only with longer tested moves; with short moves, the anchor and genetic algorithm are at least as good.The longer settings represent moves between production areas or a slow fleet and are not calibrated to a plant’s travel times.Source: A. Experimental Setup · p. 8
  • Comparisons include nine dispatching-rule pairs, a genetic algorithm, a merged-head control, and warm-started CP-SAT; the best rule pair is selected per cell, favoring that baseline.The reported protocol uses three training seeds for each arm, with single-run arms marked where they appear.Source: A. Experimental Setup · p. 8

B. Comparison Study

BOLT’s comparison results vary with operating regime and evaluation budget. It beats the best dispatching-rule pair throughout the primary grid and across the production batches, while comparisons with search and an external benchmark qualify where its advantage holds.

B. Comparison Study

  • With 60 CPU-seconds, the PDR-seeded genetic algorithm outperforms BOLT by 4% to 14% on heavy cells; best-of-64 sampling narrows the margin to 1.7%–4.7%.Longer per-instance search can recover the advantage, while BOLT produces stronger incumbents within its online budget at these sizes.Source: 1) Scheduling Quality on the Regime Grid · p. 8, 2) BOLT Remains Competitive under… · p. 9
  • Retraining on a 10/15/20-module mixture puts BOLT’s mean makespan below the best dispatching-rule pair in every tested cell from 15 to 80 modules.At 15 × 25, the 10-module policy is overtaken at moderate, but not heavy, travel; the best pair also wins at 15 modules with moderate travel and at 80 modules with one vehicle.Source: 2) BOLT Remains Competitive under… · p. 8
  • BOLT yields shorter makespans than the best of nine dispatching-rule pairs in every cell of the primary regime grid.Source: 1) Scheduling Quality on the Regime Grid · p. 8, Table II · p. 9
  • 13.0% lower mean makespan than the best dispatching-rule pair and 4.2% below warm-started CP-SAT in the three-vehicle 80-module batch.The solver’s proven gap averages 34%; the comparison does not show that BOLT approaches the optimum.Source: 2) BOLT Remains Competitive under… · pp. 8–9, Table III · p. 9
  • Across the five production batches, BOLT is shorter than the best dispatching-rule pair on every instance, by 4.7% and 6.8% at 50 modules and 13.0% at 80 modules.At 80 modules with one vehicle and short moves, it is 1.5% longer than the best pair.Source: 2) BOLT Remains Competitive under… · p. 8, Table III · p. 9
  • On the external benchmark, BOLT outperforms all three references at fleet size 3, while all three references are shorter from fleet size 6 upward.The comparisons use different training budgets and do not rank BOLT; at fleet size 6, loaded utilization is 62%, between the tested 56% and 66% boundary values.Source: 3) External Benchmark as a Consistency… · p. 9

C. Mechanism and Ablation Analysis

BOLT’s gains depend on fleet load and arise from candidate-specific action pricing; the fleet-capacity term is especially consequential when transport binds. The tests also delimit where coupling helps and how far the price-guidance findings extend.

Fleet-load regime

  • At 10 modules, explicit coupling wins every tested cell at or above 66% loaded utilization; the moderate-travel premise test failed, and its heavy-travel retry was exploratory.The anchor matches or outperforms BOLT at or below 56%; no grid cell lies between the thresholds.Source: 1) Fleet Load Determines When Explicit… · p. 10

Production-scale results

  • Across the three production batches, BOLT is shorter than the anchor on every instance by 8.0–16.8%.All arms ran on one processor thread; the reported comparison has W/T/L 20/0/0 in each cell.Source: 1) Fleet Load Determines When Explicit… · p. 10

Bound components by regime

  • The active root-bound component varies by regime: fleet capacity dominates the two most transport-constrained cells, while light-travel factories with 25, 15, or 9 stations are machine-bound.At 25 and 15 stations the policy outperforms the 60-CPU-s GA; at nine stations the methods are not distinguishable.Source: 2) Different Operating Regimes… · p. 10

Action-price ablation

  • In four pre-specified cells, action-price input beats credit-only training by pooled gains of +1.63%, +0.62%, +2.11%, and +0.84%; analytic credit alone is equivalent to shared-reward training within ±2%.The action-price result passed the stated rule on every cell and seed.Source: 3) Candidate Action Pricing Drives the… · p. 10

Fleet-capacity ablation

Price comparisons

  • A dense myopic duration price is 0.86% longer than the certified-price arm in one pre-specified cell and indistinguishable in the other three; a learned counterfactual critic is 2.5–9.8% longer across 14 cells.The counterfactual-critic comparison is descriptive because no test was fixed for that arm.Source: 3) Candidate Action Pricing Drives the… · pp. 10–11

Processing-time heterogeneity

  • With processing-time dispersion up to R = 100, the certified floor remains below the best-known makespan on all 1,500 transformed instances, while price-channel advantages vary by travel regime.On the held-out heavy-travel cell, the advantage is positive from R = 5 upward; at moderate travel, the policy’s zero-shot margin over the best rule pair is overtaken near a realized ratio of 2.5.Source: 4) Price Guidance under… · p. 11

D. Deployment and Industrial Decision Support

BOLT’s factorized deployment offers separate station and vehicle decision layers, with a makespan cost against a merged head in some production settings. It dispatches quickly, can re-plan disruptions in seconds, and uses its root bound to certify schedules and strengthen CP-SAT bounds.

D. Deployment and Industrial Decision Support

  • On production batches, the merged head is shorter in all five greedy-decoded cells; its lead exceeds the equivalence margin in the two one-vehicle cells, while factorization is equivalent in both 80-module cells.At training sizes, factorized and merged-head policies are equivalent within ±2% in 15 of 16 cells.Source: 1) Factorized Control and Its Makespan… · p. 11
  • Replacing learned vehicle decisions with nearest-vehicle-first still beats the best fixed rule pair by 3.8–13.1% on all five production batches; shortest-travel-time fallback loses 11–20% against learned decisions.The fallback rule matters, and BOLT retains factorization for separate decision layers.Source: 1) Factorized Control and Its Makespan… · p. 11
  • On one processor core, dispatch takes 2.3 ms per event at 10 modules and 5.9 ms at 80; after specified breakdowns, re-planning takes 7–14 s on the two heavy production batches.The policy’s repaired schedule is shorter than right-shift repair and re-dispatching in those tests; a GA overtakes it after 33–120 s of wall time.Source: 2) Millisecond Dispatch and… · p. 11
  • The root-bound certificate is valid for every instance but loosest where the fleet term sets the bound; on production batches it places schedules within 38–47% of optimal on average per cell.The guarantee remains valid where the time-limited solver does not close the problem.Source: 2) Millisecond Dispatch and… · p. 12
  • Adding the fleet term as a redundant CP-SAT constraint raises the proven lower bound by 3.6–4.7% at travel ratio 0.6 and 2.2–2.8% at 1.0, but closes no instance within 300 s.The incumbent is 4.8% shorter at 0.6 and unchanged at 1.0.Source: 2) Millisecond Dispatch and… · p. 12

VII. Conclusion

  • The conclusion limits the tested scope: stochastic arrivals, routing and congestion, heterogeneous fleets, finite buffers, and dispatch without destination-machine reservations remain future work; other objectives need their own bound.Within the tested scope, BOLT dispatches in milliseconds per event and re-plans disruptions in seconds.Source: §VII · p. 12

Supplementary Material for “BOLT: Multi-Bottleneck Bound-Guided Learning for Flexible Job-Shop Scheduling with Time Lags and

I. Positioning Table

The supplement positions BOLT among scheduling approaches, reports how explicit transport modeling varies with fleet load, and examines light-travel and larger-scale comparisons. Its scale-up sweep shows search quality changing with instance size and solver initialization.

I. Positioning Table

  • The positioning table compares related works by scheduling setting, transport modeling, bound structure and uses, and controller structure.Its dimensions include reward construction, certified candidate-action guidance, schedule-quality certificates, and solver strengthening.Source: §I · p. 13, §IV · p. 14

III. Fleet Utilization by Regime Cell

  • Explicit transport modeling helps in all three cells with loaded utilization at least 66%, but not in the nine cells at or below 56%.The ported external benchmark does not test this crossover, and its six-vehicle setting lies in the untested 56–66% interval.Source: §III · p. 13

IV. Scale-Up Compute Sweep

  • At 50 and 80 modules, a 60-CPU-s GA beats the 3600-s CP-SAT incumbent in every cell, while at training size CP-SAT wins seven of nine cells.Both methods use the same dispatching schedules as seeds; the ranking reversal reflects search progress alone.Source: §IV · p. 13

II. Light-Travel Column of the Regime Grid

  • With light travel, the GA outperforms both learned policies on every instance.The light-travel table reports means for three fleet-size cells and compares the GA, learned policies, and dispatching pairs.Source: §IV · p. 14

V. Sampled Decoding (Best-of-𝑁)

The supplement examines sampled decoding, control and ablation arms, and production-batch behavior. It reports that removing fleet capacity can substantially worsen production schedules, while the merged-head mixture improves on fixed dispatching pairs in two short-move cells.

Sampled Decoding (Best-of-N)

  • Best-of-64 decoding samples 63 schedules beyond the greedy rollout and returns the best schedule accepted by an independent feasibility validator.Reported times come from a GPU rerun and are not hardware-equalized against the GA's CPU-seconds.Source: §V · p. 14

One-Vehicle Production Batches with Short Moves

  • The deployed policy's lead over dispatching rules ends at 80 modules with one vehicle and short moves: it is 1.5% longer than the best pair.At 50 modules it is 3.6% shorter than the best pair; both cells exceed 66% minimum loaded utilization, but their fleets are sparser per module than any trained setting.Source: §V · pp. 14–15
  • The merged-head mixture is 7.6% and 2.8% shorter than the best dispatching pair at 50 and 80 modules, while the deployed policy is longer than the anchor in both cells.The 10-module price-channel policy is 11.4% and 9.8% longer than the anchor; the 60-CPU-s GA is shorter than every online arm in both cells.Source: §V · p. 15

Credit-and-guidance ladder

  • The price-channel arm has the shortest makespans among the listed ladder arms in all four gate-cell values.The reported means are 284.6 and 248.1 hours at |V|=1 and 422.1 and 304.4 hours at |V|=2; control-arm tests distinguish it in only one cell.Source: §V · p. 16

Fleet-term ablation

  • Removing the fleet term makes production-batch schedules 12.9–23.0% longer; the 50- and 80-module increases are 13.0% and 12.9%, and 23.0%, respectively.The 50- and 80-module cells each have W/T/L 20/0/0 and Holm-adjusted p=2.9×10^-6.Source: §V · pp. 16–17

Gate Statistics and the Credit-and-Guidance Ladder

  • The two-level bootstrap intervals are approximate because three seeds yield only ten distinct seed-level draws.Across production batches, every seed of the size-mixture policy is shorter on average than the best dispatching pair.Source: §V · p. 18

A. Timing Rules of the Solver Space

The supplement compares BOLT schedules with schedules retimed under the solver's timing rules and gives proofs for the admissible bound components. Retiming shortens schedules while preserving BOLT's assignments and sequences; the proofs establish the chain, machine, and vehicle bounds.

A. Timing Rules of the Solver Space

  • The timing comparison preserves BOLT's machine assignments and machine and vehicle sequences, changing only start times.The solver model differs by not holding the destination machine during a move and by allowing an empty vehicle leg before task release.Source: A. Timing Rules of the Solver Space · pp. 18–19
  • Retiming under CP-SAT timing rules shortens pooled 10-module schedules by 3.2%, closing 33% of the gap to the CP-SAT incumbent.At production scale, retiming shortens schedules by 1.9–3.5%; the decomposition keeps BOLT's sequences, so its timing share is a lower bound on the gap due to the constructive class.Source: A. Timing Rules of the Solver Space · p. 19

XI. Proofs for the Admissible Bound

  • The chain and machine-capacity components each bound makespan from below for every schedule in the constructive class.The chain bound is admissible at every reachable state; the machine bound sums pending workload within eligible-machine groups.Source: §XI · p. 20
  • The fleet component is admissible because mandatory loaded moves consume vehicle time, while the aggregate form is monotone and the head form can decrease along a trajectory.The two forms coincide at root states and with one vehicle; the aggregate form is tighter on most mid-episode states, but changes the composed bound on at most 7.1% of states.Source: §XI · pp. 20–21

XII. Proof of Theorem 1 and Extended Remarks

Theorem 1 makes the multi-bottleneck bound admissible at every reachable state and exact at termination, linking its reward to makespan; extended remarks delimit that guarantee and examine credit variants.

XII. Proof of Theorem 1 and Extended Remarks

  • The bound never exceeds an attainable makespan and equals the realized makespan at termination, so its undiscounted reward return is a positive-affine transform of negative makespan.The theorem’s admissibility is stated over the set C; the proof shows the chain component attains the makespan at termination.Source: §XII · p. 21
  • The main bound is the maximum of chain, machine-capacity, and fleet-capacity terms, but the F-bound guarantee does not extend to general mid-episode states with an in-transit operation.The stated CP-SAT lower bound is at the root, and the paper makes no universal F-bound claim.Source: §XII · p. 21
  • Bound-counterfactual credit subtracts an action-independent state control variate from the advantage; its unbiasedness does not establish a scheduling gain.The pre-specified credit test found no significant advantage over shared-reward training, while the M2 return arm raised makespan by 19% to 50% on gate cells.Source: §XII · pp. 21–22
  • The M2 pass-state correction is not a potential difference, so optimal-policy invariance does not follow; the paper reports that this empirical arm collapses.The correction uses a virtual sibling state rather than the realized successor.Source: §XII · p. 22

XIV. Per-Cell Certificates

The per-cell certificates remain admissible and vary in tightness with the active bottleneck and instance regime; the accompanying delay-semantics and production-batch results compare policy realizations and fallbacks.

XIV. Per-Cell Certificates

  • Root-bound tightness declines as loaded utilization rises and recovers as stations grow scarce; processing-time dispersion affects tightness only when the chain term is active.The reported utilization correlation is Spearman ρ = −0.97 across twelve primary-grid cells.Source: §XIV · p. 22
  • Across 1,600 instances, the root bound averages 87.6% of best-known makespan, reaching 90.3% when chain-bound and 76.0% on the 304 fleet-bound instances.Because best-known makespan is at least optimal makespan, these ratios are lower limits on tightness.Source: §XIV · p. 22
  • A proposed root refinement adds the earliest mandatory-move readiness floor, fleet work per vehicle, and subsequent processing time; BOLT does not use it.In one-vehicle cells, the refinement matches or exceeds the 300-second CP-SAT bound on every instance.Source: §XIV · p. 22
  • Across 1,600 instance-cell pairs, the root bound never exceeded the CP-SAT upper bound; the price check found no admissibility violation on 2,674 candidates.CP-SAT closed 267 of 1,600 instances.Source: §XIV · p. 22

XVI. Delay-Semantics Table

  • Machine-free and machine-side delays have instance-fixed durations, whereas resource-coupled delay duration is set by the job-and-fleet schedule.Source: §XVI · p. 23
  • The merged head is inconclusive in two cells, equivalent in two, and worse than factorized heads in the two one-vehicle cells under the pre-specified rule.The one-vehicle comparisons favor factorized heads 0/0/20 in each cell.Source: §XVI · p. 23
  • Both size-mixture policies beat the penalty anchor on every production-batch instance; vehicle-rule fallbacks beat the best fixed pair by 3.8–13.1%, while shortest-travel-time fallbacks lose 11–20%.Source: §XVI · pp. 23–24

XIV. Per-Cell Certificates

  • In the illustrated one-vehicle, τ̄/p̄ = 0.6 instance, BOLT keeps the vehicle moving toward makespan, whereas the penalty anchor makes only a few isolated moves.The instance has the largest makespan difference between the policies among the first 20 test instances.Source: §XIV · p. 23, Figure S-7 · p. 24

XVIII. Recovery from a Machine Breakdown

This section evaluates schedule recovery after machine breakdowns, comparing replanning approaches and control variants across duration-noise and processing-time-heterogeneity settings. Results vary with search budget and show seed-sensitive outcomes, with no measurable replanning gain under duration noise and no systematic dispersion effect.

XVIII. Recovery from a Machine Breakdown

  • At 50/80 modules, policy re-plans are 11.0–19.0% shorter than warm-started CP-SAT at every budget, but 4.8–9.5% longer than GA, which takes 33–120 s.The policy takes 7 s at 50 modules and 14 s at 80 modules; the crossover to the GA’s shorter result occurs between 33 s and 120 s after breakdown, depending on cell and budget.Source: §XVIII · p. 24, §XXI · p. 26
  • After a 20%-duration outage beginning at 30% of baseline makespan, policy replanning beats right shift by 11.7% in both cells and dispatching by 2.4% and 6.0%.The breakdown affects the machine with the largest remaining workload; comparisons are across 20 instances per setting.Source: §XVIII · p. 25

XIX. Execution Under Duration Noise

  • With duration noise up to ±30%, the policy stays ahead of rule re-dispatch but behind search methods at every level, while replanning changes realized makespan by at most 0.7% versus right shift.At σ = 0.3, right-shift execution raises the policy’s realized makespan by 1.7% at 50 modules and 2.5% at 80 modules; replanning did not significantly improve on right shift.Source: §XIX · p. 25

XX. Merged-Head Control on the Regime Grid

  • Across the primary regime grid, merged-head and factorized policies are equivalent except at 15×25 with τ̄/p̄ = 1.0, where factorized control is better; equivalent-cell differences reach at most 0.37%.Source: §XX · p. 25, §XXI · p. 27

XXI. Processing-Time Heterogeneity Study

  • Processing-time dispersion raises the mean eligible-machine max/min ratio from 1.21 at baseline to 5.09 at R = 20 and 7.6 at R = 100, where total mean work rises about 2.7%.The 7.6 figure is the mean at R = 100; the median is 6.0 and the 95th percentile is 18. The work increase reflects a one-hour integer floor on processing times.Source: §XXI · p. 27
  • On the held-out heavy-travel cell, the bound-guided arm trails shared reward by 2.08% at baseline (p < 10^-4), but is ahead from +1.57% at baseline to +1.54% at R = 20 when averaging seeds 301 and 303.The baseline loss is driven by bound-guided seed 302, whose mean is 737.7 h versus 649.9 and 628.2 h for seeds 301 and 303.Source: §XXI · p. 27
  • The results do not show that heterogeneity creates the advantage: the three-seed baseline loss is concentrated in one checkpoint, indicating seed sensitivity rather than a systematic dispersion effect.The evaluation code reproduces that checkpoint’s stored baseline evaluation within 0.05%; the largest discrepancy across 18 seed-cell pairs checked is 0.11%.Source: §XXI · p. 28
  • Excluding the same seed preserves the advantage trend: at |V| = 1, τ̄/p̄ = 0.6, it rises from +1.99% at baseline to +3.11% at R = 20, and at |V| = 2 from +0.21% to +1.60%.The corresponding three-seed trends are +1.96% to +3.54% and +0.55% to +2.15%, respectively.Source: §XXI · p. 28
  • Against the best fixed-rule pair, the margin reverses to −3.59% at |V|=1, τ̄/p̄=0.6 and −3.96% at |V|=2, τ̄/p̄=0.6 at the stress level; on the held-out heavy-travel cell, |V|=1, τ̄/p̄=1.0, it remains +0.38%.Every result is zero-shot; retraining for this processing-time variation is untested.Source: §XXI · pp. 28–29

XXII. Bound-Component Summary

The section reports external benchmark comparisons and explains how timing semantics affect them. It also identifies the chain, machine-capacity, and fleet-capacity components of the bound.

Bound components

  • The bound-component summary identifies what Bchain, Bmch, and Bveh capture, relax, and when each binds.The overall bound is B = max(Bchain, Bmch, Bveh).Source: §XXII · p. 29

External benchmark

  • The port was checked against 100 regenerated instances: none of 24 deterministic released combinations differed significantly from released per-instance makespans at α=0.01.External comparisons are therefore distribution-level, unpaired comparisons with n=100 per side.Source: §XXII · p. 29

Timing semantics

  • Replaying schedules under the comparator’s anticipatory vehicle rule shortened makespan by 1.0% at three vehicles and by up to 15.3% at fleet sizes of at least nine.The anticipatory rule permits an empty vehicle to travel to a pickup before the job is ready; timing differences are negligible when the fleet is scarce and largest when it is not.Source: §XXII · p. 29

External benchmark

  • At three vehicles, the credit-only run scored 4213±286, within 0.6% of the bound-guided arm, and outperformed all three released anchors.The anchor comparisons were −15.3%, −16.9%, and −8.9% against the joint model, best modular pair, and best heuristic, respectively.Source: §XXII · p. 29

XXIV. Deployment Cost by Instance Size

The deployment evaluation reports per-event inference times across instance sizes. The accompanying decision record documents pre-specified evaluation gates, including failed tests and the decision not to claim parity where the merged-head control led.

XXIV. Deployment Cost by Instance Size

  • Per-event time on one processor core rises from 2.3 ms at 10 modules to 5.9 ms at 80 modules.Forward pass and action selection account for 1.5–4.2 ms; the environment step takes the remainder.Source: §XXIV · p. 29, §XXV · p. 30

XXV. Pre-Specified Decision Record

  • The premise gate compared explicit coupling with a penalty anchor that knew travel times but never faced vehicle contention; its moderate-travel first attempt failed.A single permitted heavy-travel retry was exploratory, not confirmatory evidence.Source: §XXV · p. 30
  • The pre-specified analytic-credit gate required outperforming shared-reward training on four scarce-fleet cells pooled over three seeds, but it failed.The recorded response was to report the result and avoid searching for a cell where the gate passed.Source: §XXV · p. 30
  • The action-price channel was adopted only conditional on beating the credit-only arm on all four gate cells, first at seed 301 and again across three seeds.Source: §XXV · p. 30
  • Equivalence tests used a ±2% margin fixed before parity comparisons were run.Source: §XXV · p. 30
  • Solver results for a production-batch cell were reported only when all 20 instances returned full-protocol incumbents; partial cells were left empty.Source: §XXV · p. 30
  • The merged-head control led beyond the equivalence margin in the two one-vehicle production cells, so the main text makes no parity claim.Source: §XXV · p. 30

Related papers

Loading 2610.22433v1…