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

AI summary

Overview

Research area: Machine learning for combinatorial optimization, specifically deep reinforcement learning applied to production scheduling (flexible job-shop scheduling with transport resources).

Technical level: Advanced. The paper combines a formal scheduling formulation, an admissible (provably valid) lower bound built from three relaxations, a proof of reward faithfulness, and a reinforcement-learning policy with two action heads.

Scope (one sentence): The paper proposes BOLT, a bound-guided learning method for flexible job-shop scheduling where jobs must be moved between machine cells by a scarce, shared vehicle fleet, and shows that a single certified multi-bottleneck lower bound can serve as reward, per-action guidance, a solver-free quality certificate, and a solver-strengthening constraint.

What This Paper Is About

In many factories, partly finished products have to travel between stations on a small fleet of transporters or automated guided vehicles, and how long a product waits for a vehicle depends on the schedule itself. Existing learned schedulers either ignore the fleet, treat transport as a fixed time surcharge, or use hand-designed rewards, so they cannot see when vehicles become the real bottleneck. BOLT's goal is to build one provable lower bound on completion time that captures job chains, machine capacity, and fleet capacity together, and then reuse that same quantity to train a fast dispatcher, to score each candidate decision, to certify how far a finished schedule is from optimal, and to strengthen an exact solver.

Key Contributions

1. A resource-coupled scheduling formulation. The authors formalize flexible job-shop scheduling with time lags and transport (FJSP-TL-T), in which vehicles are seized for a whole move (empty leg plus loaded leg) and destination machines are reserved idle while the job is in transit. They also introduce a delay-semantics taxonomy separating machine-free delays (e.g., curing lags), machine-side delays (e.g., setups), and resource-coupled delays (transport), where only the third has a duration set by the schedule rather than by the instance.

2. A certified multi-bottleneck lower bound. The bound is the maximum of a chain component, a machine-capacity component, and a fleet-capacity component. It is proved admissible at every reachable partial schedule (the machine term under a "type-pure eligibility" assumption matching the studied layouts) and equal to the realized makespan at termination, which makes its one-step change an objective-faithful reward.

3. Bound-oriented learning and decision support. The same bound yields certified action prices (a proven minimum increase of the makespan floor for each candidate action), a solver-free certified relative suboptimality gap for any completed schedule, and a redundant constraint that raises the lower bound proved by warm-started CP-SAT in the tested one-vehicle cells.

4. An operating-regime and deployment study. The paper identifies when explicit transport modeling pays off versus when a fixed transport penalty suffices, compares a merged-head policy against a factorized machine/vehicle policy, and reports latency, breakdown re-planning, and robustness behaviour.

Main Findings

• The fleet term is necessary. The paper gives a worked argument (Remark 1) in which many jobs must all make the same inter-cell move on one vehicle: the chain and machine components stay flat as the number of jobs grows, while the true makespan grows as the number of jobs times the loaded travel time. The fleet-capacity component, which divides aggregate transport workload by the fleet size, closes this gap.

• Explicit coupling pays off only above a load threshold. At the 10-module training size, explicit coupling shortened makespan in every cell at or above 66% loaded utilization, whereas a transport-penalty policy was adequate at or below 56%; the tested crossover lies between these two values. Gains over a fixed transport allowance appeared only in tested cases with loaded moves of 2.8 to 4.7 hours.

• Strong results on the 80-module, three-vehicle batch. Mean makespan was 13.0% below the best dispatching-rule pair and 4.2% below warm-started CP-SAT given an hour, whose proven gap averages 34%.

• Mixed results on production batches. Across five 50- and 80-module batches outside the trained sizes, the policy beat the best dispatching-rule pair on four and lost by 1.5% where one vehicle served 80 modules. On the three batches with long moves, BOLT outperformed the penalty policy on every instance.

• The action price drives the training gain. Ablations on four pre-specified cells attribute the training improvement to the action-price feature.

• Removing the fleet term hurts. Dropping the fleet-capacity component lengthened schedules by 4.8% and 6.2% in the two 10-module cells where that term sets the bound, and by 12.9–23.0% on three production batches.

• Fast inference and re-planning. BOLT takes 2.3–5.9 ms per event on one processor core, or 0.8–15.9 s for a whole schedule, from 10 to 80 modules. After a machine breakdown it re-plans in 7–14 s, while CP-SAT at budgets of 1 and 10 s returned the right-shifted plan unchanged; a genetic algorithm needed 33–120 s to find a schedule shorter than BOLT's.

• The bound is loose on large batches. The solver-free certified gap averaged 38–47% on large batches, meaning the certificate is valid but weak there.

• The analytic credit option gives no scheduling gain. The optional per-head credit correction, formed by subtracting the virtual-pass reward from the generalized advantage estimate, leaves the gradient estimator unbiased but produced no scheduling improvement in the tests.

• Factorized control has a modest cost. The factorized (separate station and vehicle) realization costs up to 4.4% in makespan there against one merged head, while giving each decision class its own output layer.

• Robustness to duration noise. A schedule executed under duration noise of up to ±30% stayed within 0.7% of re-planning.

Methodology in Plain English

The researchers start from a standard flexible job shop, where each job is a chain of operations that can run on any of several eligible machines, and add two things: fixed waiting periods that occupy the job but no machine (such as curing), and a shared fleet of vehicles that must carry jobs between machine locations. A vehicle is occupied for the entire move, and the destination machine is held idle until the job arrives.

They then build three separate "optimistic estimates" of how long the remaining work must take. One follows each job's own remaining path. One treats each group of interchangeable machines as a pool of capacity and divides the remaining work by the pool size. The third divides the total remaining transport workload by the number of vehicles. None of these can overestimate the true best achievable completion time, so their maximum is also a valid lower bound. Because that maximum picks out whichever resource is currently limiting, no hand-tuned weighting is needed. At the end of scheduling, the bound coincides with the actual makespan.

This coincidence is the key to training. If the bound ends up equal to the makespan, then rewarding the learner with each decrease in the bound is equivalent to rewarding it with progress toward a shorter makespan — the total reward is just a shifted, scaled negative makespan. The same successor bound is computed for every candidate action, giving each candidate a "price": the amount by which it provably raises the floor. That price is fed to the policy as an input feature, not used as a hard mask, so the network can override it.

The policy itself uses a dual-attention encoder over operation, machine, and vehicle nodes, with two output heads — one for machine-class decisions and one for vehicle-class decisions — trained with proximal policy optimization and one critic. The bound's fleet term is additionally handed to a constraint-programming solver (CP-SAT) as a redundant constraint, and the root bound is used to certify how far any finished schedule is from optimal.

Experiments use instances from an industry-motivated generator whose routing classes and operation structure follow published process documentation for prefabricated prefinished volumetric construction (PPVC). The paper states that the instances contain no plant production records and that no plant deployment is reported.

Why This Matters

For research, the paper shows that a single admissible bound can serve four different roles at once — reward, per-action guidance, quality certificate, and solver constraint — and it extends bound-guided scheduling from machine-only job shops to settings with a scarce, schedule-dependent transport resource. It also gives a concrete criterion (loaded fleet utilization) for deciding when explicit transport modeling is worth the modelling effort.

Real-world applications:

• Prefabricated volumetric construction (PPVC): the motivating case, where whole room modules weighing 26 to 31 tons are moved between stations; one documented project moved 1,866 modules and another erected two 56-story towers from 3,034 modules.
• Heavy-module fabrication yards that rely on a few heavy transporters and need millisecond dispatch decisions plus quick re-planning after a breakdown.
• AGV-served machining or assembly cells where a small vehicle fleet is shared across stations and travel time is comparable to processing time.
• Fab or plant scheduling with curing, drying, or ponding lags, where some waits occupy the product but not the machine.

Industry relevance: the dispatcher runs in milliseconds on a single processor core and re-plans in seconds after a breakdown, and the separate station and vehicle output layers let a plant retune or roll back one decision class while the other stays fixed. The solver-free gap certificate lets a plant report a guaranteed bound on how far a schedule is from optimal without running a solver, although that certificate is loose (38–47% on average) on large batches.

Future Directions

• Extending the method to stochastic arrivals and online dispatch without a reserved destination machine, which the paper explicitly names as the next step.
• Closing the looseness of the certified gap on large batches, since the current certificate averages 38–47% on those.
• Adding the effects the model leaves out: vehicle routing and congestion, heterogeneous or mixed fleets, station-buffer limits, sequence-dependent setups, machine availability, blocking machines, and maximum time lags.
• Improving the high-load regime, where the dispatcher lost to the best dispatching rules in one tested case with one vehicle serving 80 modules, and reducing the up-to-4.4% makespan cost of the factorized deployment relative to a merged head.

Target Audience

Researchers and graduate students in machine learning for combinatorial optimization and reinforcement learning for scheduling; industrial engineers and operations researchers working on job-shop and AGV-assisted scheduling; and practitioners in prefabrication, heavy manufacturing, or automated logistics who need a fast, certifiable dispatcher and want guidance on when modeling transport explicitly is worth it. Readers should be comfortable with scheduling formulations, lower bounds, and policy-gradient methods.

Authors’ abstract

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.