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

BOLT: Bound‑Guided Learning for Transport‑Coupled Flexible Job‑Shop Scheduling

Flexible job‑shop scheduling (FJSS) traditionally focuses on assigning operations to machines while respecting precedence and capacity limits. In many real‑world settings—such as prefabricated construction or semiconductor manufacturing—jobs must also be moved between stations by a limited fleet of vehicles. This resource‑coupled transport introduces additional waiting times and creates a multi‑bottleneck problem where both machines and the transport fleet constrain the overall makespan.

BOLT (Multi‑Bottleneck Bound‑Guided Learning) tackles this challenge by embedding a provable lower‑bound computation directly into a reinforcement‑learning (RL) policy. The bound is derived from three relaxations:

1. Chain relaxation – ignores machine capacities, yielding a simple precedence‑based lower bound.
2. Machine‑capacity relaxation – respects machine limits but assumes unlimited transport.
3. Fleet‑capacity relaxation – respects vehicle limits while assuming unlimited machine capacity.

The maximum of these three values forms a global bound that never exceeds the optimal makespan. As the RL agent steps through scheduling decisions, the bound can only increase; each increment is interpreted as a price that the policy pays to raise the makespan floor. Because the bound’s final value equals the makespan of the produced schedule, the sum of per‑step price changes equals a constant minus the makespan, providing a natural reward signal that directly aligns learning with the objective.

---

Why Bound‑Guided Learning Matters

Traditional RL approaches for scheduling rely on handcrafted reward functions (e.g., penalizing tardiness or idle time) that only loosely correlate with the true performance metric. BOLT’s bound‑based reward has two key advantages:

• Monotonicity: The bound can never overshoot the optimal makespan, guaranteeing that every reward increase reflects a genuine tightening of the schedule’s lower bound.
• Interpretability: The root bound at any point quantifies the suboptimality gap of the current partial schedule without invoking a separate solver, enabling on‑the‑fly assessment of how far the policy is from optimality.

These properties allow BOLT to learn policies that are both sample‑efficient (because the reward signal is informative) and transparent (because the bound can be inspected by practitioners).

---

Performance Highlights

BOLT was evaluated on industry‑motivated instances derived from prefabricated‑construction projects. The test set includes:

• 10‑module scenarios with varying transport intensities (fraction of fleet time occupied by loaded moves).
• Zero‑shot batches of 50 and 80 modules, where the policy must generalize to unseen problem sizes.
• Disruption replanning cases where a vehicle breakdown or a sudden order change occurs.

Key findings:

• When loaded moves consume ≥ 66 % of fleet time, BOLT’s explicit transport coupling consistently outperforms a baseline transport‑penalty policy; the advantage disappears when utilization drops to ≤ 56 %.
• Across five zero‑shot batches, BOLT beats the best handcrafted dispatching‑rule pair on four batches and surpasses the penalty policy on the three batches with long transport moves.
• In the most demanding 80‑module batch with three vehicles, BOLT’s mean makespan is 13 % lower than the best rule‑based pair and 4.2 % lower than a state‑of‑the‑art hour‑budget constraint‑programming solver whose proven optimality gap averages 34 %.
• Decision latency is modest: 2.3–5.9 ms per scheduling event on a single CPU core, and full replanning after a disruption completes within a few seconds.

These results demonstrate that BOLT not only narrows the performance gap to exact solvers but also does so with orders‑of‑magnitude faster decision times, making it suitable for real‑time production environments.

---

Practical Implications and Next Steps

For practitioners managing complex manufacturing lines or construction sites, BOLT offers a plug‑and‑play scheduling engine:

1. Model the workflow – define operations, machine capacities, precedence constraints, and transport requirements (including vehicle fleet size and loading times).
2. Generate the bound – the three relaxations are computed automatically; no manual tuning is required.
3. Deploy the learned policy – the RL agent can be trained on representative historical data and then applied to live scheduling, with the bound continuously reporting the current suboptimality gap.
4. Handle disruptions – when a vehicle fails or a new order arrives, BOLT can re‑plan in seconds, preserving near‑optimal performance.

Future research directions include extending the bound formulation to stochastic travel times, integrating energy consumption metrics for electric fleets, and exploring multi‑objective extensions that balance makespan with work‑in‑process inventory.

---

Closing Thoughts

BOLT illustrates how theoretical guarantees (a provable lower bound) can be woven into data‑driven decision making (reinforcement learning) to solve a notoriously hard class of scheduling problems. By treating the bound’s incremental increase as a price signal, the method aligns the learning objective with the true performance metric, delivering schedules that are both high‑quality and computationally lightweight. As manufacturing and construction continue to adopt autonomous transport resources, approaches like BOLT are poised to become essential tools for achieving tight, reliable production timelines.