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

cs.LGOct 15, 2026

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

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

Organizations: Infocomm Technology Cluster, Singapore Institute of Technology, Singapore 828608 · College of Smart Energy, Shanghai Jiao Tong University, Shanghai, China · School of Computer Science and Informatics, Cardiff University, Cardiff CF24 4AG, U.K. · D-SIMLAB Technologies, Singapore

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.

Figures & tables

Work	Transport	Time lags	Destination machine at dispatch	Training signal
Moon et al. [ 17 ]	seized vehicle, empty and loaded legs	none	chosen with the vehicle, blocked from dispatch	chain estimate, no fleet term, uncertified
Li et al. [ 14 ]	AGV allocated per task	n.s.	n.s.	hand-designed (machine idle time)
Zhang et al. [ 5 ]	transfer time, no vehicle agent	n.s.	not applicable	hand-designed shaping
Wang et al. [ 15 ]	transbots serve a fixed job-machine sequence	n.s.	assigned before the move, hold n.s.	hierarchical, n.s.
Yang et al. [ 16 ]	AGV selection	n.s.	n.s.	hand-designed
Link et al. [ 23 ]	seized AGV, empty leg, anticipatory pickup	none	fixed by the route, not held	sparse terminal, bound as normalizer

TABLE I: Learned transport-aware schedulers closest to BOLT. n.s.: not specified in the published description.

Panel of Figure 2 — Fig. 1: The three delay-semantics classes (Definition 2 ), with machine (Mch), job, and, where one is used, vehicle (Veh) lanes. Blue marks processing, hatching marks instance-fixed waits, gray marks the job waiting with no resource seized, amber marks the empty ( $\tau_{e}$ ) and loaded ( $\tau$ ) legs that seize the vehicle, and an outline marks the destination machine reserved idle until the job arrives. The vertical dashed rule marks the boundary of the class studied here.

Panel of Figure 3 — Fig. 2: BOLT framework with one certified bound $B=\max(B_{\mathrm{chain}},B_{\mathrm{mch}},B_{\mathrm{veh}})$ and its four uses (i)–(iv). Amber marks the bound and quantities derived from it, blue the learned policy, and the dashed band optional deployment extensions.

Panel of Figure 4 — Fig. 3: (a) Coupling-regret map: relative makespan penalty of the penalty anchor, a transport-penalty policy (one seed, half budget), against BOLT (3-seed mean; $n=100{}$ per cell, $10\times 25$ ). The second line of each cell is the minimum loaded utilization. (b) The bound component attaining the root maximum, per cell (share of instances; blue chain, amber fleet); the machine component never attains the maximum on this grid.

Regime cell		Online dispatch			Solver reference
$\|V\|$	$\bar{\tau}/\bar{p}$	Best PDR a	BOLT	W/T/L b	CP-SAT c	$\Delta$ % d
$1$	$0.3$	288.3 $\pm$ 10.2	284.6 $\pm$ 7.6	62/0/38	257.4 $\pm$ 8.1	+10.5%
$1$	$0.6$	449.7 $\pm$ 23.5	422.1 $\pm$ 9.4	93/0/7	394.2 $\pm$ 9.6	+7.1%
$1$	$1.0^{\ast}$	726.1 $\pm$ 40.1	672.1 $\pm$ 17.7	90/0/10	639.7 $\pm$ 16.9	+5.1%
$2$	$0.3$	252.8 $\pm$ 8.7	248.1 $\pm$ 8.5	83/0/17	225.5 $\pm$ 8.7	+10.0%
$2$	$0.6$	309.2 $\pm$ 10.6	304.4 $\pm$ 7.9	69/0/31	274.1 $\pm$ 9.6	+11.1%

TABLE II: Makespan on the FJSP-TL-T regime grid at

10\times 25

(jobs

\times

machines): hours, mean

\pm

std (

n=100{}

per cell; learned arms: per-instance 3-seed means). Bold: shortest makespan in the row. Light-travel column and merged-head control: supplement.

		Online		Solver reference
Cell	$u$	Best PDR	BOLT	CP-SAT 1800 s	CP-SAT 3600 s
$50$ , $2$ , $0.6$	76%	1113.9 $\pm$ 19.3	1061.1 $\pm$ 18.2	1034.3 $\pm$ 23.5	1029.8 $\pm$ 24.4
$50$ , $2$ , $1.0$	80%	1789.9 $\pm$ 39.5	1668.0 $\pm$ 31.9	1709.4 $\pm$ 46.7	1704.1 $\pm$ 45.6
$80$ , $3$ , $1.0$	74%	2173.7 $\pm$ 36.7	1890.8 $\pm$ 23.4	2002.0 $\pm$ 83.7	1974.2 $\pm$ 83.2

TABLE III: Makespan in hours on the 50- and 80-module production batches (

n=20

per cell; policy: per-instance 3-seed means). Bold: shortest makespan in the row. The GA comparison is in Table S-IV.

$\|V\|$	BOLT	$\Delta$ joint	$\Delta$ modular	$\Delta$ heuristic
$3$	4239 $\pm$ 284	-14.7%	-16.3%	-8.4%
$6$	2949 $\pm$ 166	+27.8%	+23.0%	+30.7%
$9$	2725 $\pm$ 172	+49.2%	+44.1%	+45.5%
$12$	2725 $\pm$ 173	+57.2%	+54.4%	+49.8%
$15$	2711 $\pm$ 158	+56.8%	+56.8%	+49.5%
$18$	2720 $\pm$ 162	+57.8%	+58.4%	+50.1%

TABLE IV: External benchmark (Link et al. [ 23 ] ),

15\times 10

, makespan in simulator units (mean

\pm

std,

n=100{}

; per-instance means over 3 runs, every seed agreeing in sign).

\Delta

: relative difference to their joint model, best modular pair, and best heuristic (negative favors BOLT; bold: the fleet size where BOLT outperforms all). All differences significant (Mann–Whitney; at

|V|=3

all

p\leq 9.2\times 10^{-14}

Fig. 4: Validation makespan (hours) against PPO updates (line: seed mean; band: seed range; mean over the nine training cells).

Panel of Figure 9 — Fig. 5: Merged-head (left) and factorized (right) realizations of BOLT.

Flexible Job Shop Scheduling

See all 14 papers

Time-Lag-Aware Deep Reinforcement Learning for Flexible Job-Shop Scheduling in PPVC Module Factories
Jul 13, 2026Ziheng Zhang, Wei ZhangManufacturing Reinforcement Learning
Singapore Institute of Technology, Singapore
An Analysis of the Coordination Gap between Joint and Modular Learning for Job Shop Scheduling with Transportation Resources
Apr 27, 2026Moritz Link, Jonathan Hoss, Noah KlarmannMulti-Agent Coordination Combinatorial Optimization
Faculty of Management and Engineering, University of Applied Sciences, 83024 Rosenheim, Germany
CoRS: Fast Neural Flexible Job-Shop Scheduling via Composite Interval State Reuse
Oct 19, 2026Jiang Sutong, Zhao Peng, Wu Xuan +6Flexible Job Shop Scheduling Neural Combinatorial Optimization
College of Computer Science and Technology, Jilin University, China · College of Software, Jilin University, China · College of Computing and Data Science, Nanyang Technological University, Singapore +1

Jul 13, 2026J/K move · Enter open · S save

Time-Lag-Aware Deep Reinforcement Learning for Flexible Job-Shop Scheduling in PPVC Module Factories

Ziheng Zhang, Wei Zhang

Singapore Institute of Technology, Singapore

Manufacturing Reinforcement Learning Flexible Job Shop Scheduling Combinatorial Optimization RL for Combinatorial Optimization Job Shop Scheduling

Open paper AskPDF arXiv

Prefabricated prefinished volumetric construction moves most building work into module factories, whose production floor operates as a flexible job shop. A major complication is decisive: long post-operation time-lags caused by concrete curing, watertightness ponding tests, and paint drying, during which a module is blocked while its workstation stays free. On benchmark instances grounded in an official national prefabrication guidebook, these lags inflate even the optimal reference makespan by about 67% on average, and ignoring them at decision time, then repairing to feasibility, is worse than every dispatching rule. We adapt a state-of-the-art dual-attention deep reinforcement learning solver through three minimally invasive, individually ablatable extensions: lag-aware dynamics with an admissible reward bound, two anticipatory lag feature channels, and liveness-masked operation- and station-type embeddings. With every extension disabled the implementation reproduces the original solver exactly, so all gains are attributable to the adaptations. We release a public, guidebook-grounded benchmark generator. On held-out instances the learned policy is the strongest solver-free scheduler: it reaches within about 4% of a constraint-programming reference and beats every dispatching rule and a genetic-algorithm metaheuristic, with its advantage widening under capacity contention, and a single size-mixed policy carries this lead across the trained range of factory sizes. It needs no solver, model, or license in the loop and re-plans within seconds of a disruption; where an exact solver can be deployed, that solver remains the quality ceiling, a boundary we map explicitly.

Abstract

Flexible Job Shop Scheduling

Explore similar work

Time-Lag-Aware Deep Reinforcement Learning for Flexible Job-Shop Scheduling in PPVC Module Factories

An Analysis of the Coordination Gap between Joint and Modular Learning for Job Shop Scheduling with Transportation Resources

CoRS: Fast Neural Flexible Job-Shop Scheduling via Composite Interval State Reuse