💻 computer science

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

This paper analyzes the coordination gap between joint and modular training in multi-agent reinforcement learning for job-shop scheduling with transportation resources, revealing that while joint training generally yields superior performance, modular training becomes a viable and efficient alternative in bottleneck environments where a single scheduling task dominates.

Original authors: Moritz Link, Jonathan Hoss, Noah Klarmann

Published 2026-04-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Moritz Link, Jonathan Hoss, Noah Klarmann

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a busy factory floor as a giant, high-stakes dance floor. On one side, you have the dancers (the jobs or products) who need to move through a specific sequence of steps on different machines. On the other side, you have the ushers (the Automated Guided Vehicles, or AGVs) whose job is to carry the dancers from one machine to the next.

The goal is simple: get everyone through the dance as fast as possible without anyone bumping into each other or waiting too long. This is the "Job Shop Scheduling Problem with Transportation Resources."

The paper by Link, Hoss, and Klarmann asks a very specific question about how we teach the computer brains (Artificial Intelligence) to manage this dance: Should we teach the dancers and the ushers to dance together in one big class, or should we teach them separately and then just tell them to work together later?

Here is the breakdown of their findings using simple analogies:

The Two Training Methods

Joint Training (The "Rehearsal Together" Approach):
Imagine teaching the dancers and the ushers in the same room at the same time. They learn to anticipate each other's moves. If a dancer is about to finish a step, the usher learns to be waiting right there. They develop a "team chemistry" because they are learning simultaneously.
- Technical term: Multi-Agent Reinforcement Learning where both agents train together.
Modular Training (The "Separate Rehearsal" Approach):
Imagine teaching the dancers in one studio and the ushers in another. They become experts at their own specific jobs. Then, on the day of the show, you just tell them, "Okay, dancers, go do your thing; ushers, go do yours." They haven't practiced together, so they have to rely on general rules (like "always pick up the nearest dancer").
- Technical term: Training agents independently and integrating them later.

The Big Discovery: It Depends on the "Traffic"

The researchers ran thousands of simulations to see which method wins. They found that the answer isn't "always one or the other." It depends entirely on how crowded the factory is.

1. The "Balanced Dance Floor" (Joint Training Wins)

When the factory has a good mix of machines and enough ushers to go around, the Joint Training method is the clear winner.

Why? Because there are no major traffic jams. The system is flexible. When the dancers and ushers learn together, they can find clever, non-obvious shortcuts. They learn to coordinate perfectly, squeezing out extra speed that separate training misses.
The Result: The "Joint" team finished the dance about 4% faster on average than the best "Separate" teams. In a factory, that's a huge deal.

2. The "Gridlock" (Modular Training is Just as Good)

The paper found something surprising: When the factory is extremely crowded (either not enough ushers to move things, or the machines are so slow that the ushers are just waiting around), the advantage of "Joint Training" disappears.

The Analogy: Imagine a highway during rush hour. It doesn't matter if the drivers and the traffic lights are perfectly coordinated (Joint Training) or if they are just following basic rules (Modular Training). If there is a massive bottleneck, nothing can move faster than the slowest part of the system.
The Result: If you have a severe shortage of ushers or a severe shortage of machine speed, the "Joint" team only gets a tiny, almost invisible advantage over the "Separate" team. In these cases, the expensive, complex joint training isn't worth the extra effort.

The "Coordination Gap"

The authors call the difference in performance between the two methods the "Coordination Gap."

Wide Gap: When resources are balanced, the gap is wide. Joint training is much better.
Narrow Gap: When there is a bottleneck (too few ushers or too slow machines), the gap shrinks to almost zero.

The Takeaway for Factory Managers

The paper provides a simple rule of thumb for decision-makers:

If your factory is well-balanced (you have enough vehicles and machines working at a similar pace), train your AI agents together. The extra coordination will pay off with faster production.
If your factory is broken (you are severely short on vehicles or your machines are the bottleneck), you don't need to train them together. You can train them separately and just plug them together. The bottleneck will limit your speed anyway, so the fancy coordination won't help much.

Summary

Think of it like a relay race.

If the track is clear and everyone is fit, having the runners practice the hand-off together (Joint Training) makes the team faster.
But if one runner is injured or the track is blocked (a Bottleneck), practicing the hand-off together won't help. The team will be slow no matter what, so you might as well just have everyone run their own leg separately.

The paper proves that you don't always need the most complex, expensive AI training; sometimes, a simpler approach works just fine, provided you know exactly what kind of "traffic" your factory is facing.

1. Problem Definition

The paper addresses the Job Shop Scheduling Problem with Transportation Resources (JSSPT), a complex variant of the classic Job Shop Scheduling Problem (JSSP).

Context: In modern "decentralized factories," production operations must be coordinated with material handling using Automatic Guided Vehicles (AGVs).
Objective: Minimize the makespan ( $C_{max}$ ), defined as the completion time of the last job at the unload machine.
Constraints:
- Production: Jobs follow fixed routing sequences; machines process one operation at a time without preemption.
- Transportation: AGVs have unit capacity (one job at a time) and cannot be preempted. An operation can only start after its transport is completed, and transport can only begin after the previous operation finishes.
- Buffers: Input buffers are infinite (FIFO); output buffers are infinite with no ordering constraints.
The Core Challenge: Traditional methods (Dispatching Rules, Genetic Algorithms) struggle with real-time adaptability or computational cost. While Multi-Agent Reinforcement Learning (MARL) offers a solution, it is unclear when Joint Training (simultaneous training of job and AGV agents) is necessary versus when Modular Training (independent training followed by integration) suffices.

2. Methodology

A. Multi-Agent Reinforcement Learning Framework

The authors formulate the problem as a Markov Decision Process (MDP) with two distinct agents:

Job Scheduler Agent: Decides which operation to schedule next.
AGV Scheduler Agent: Decides which AGV to assign to the selected operation.

State Representation:

Job State ( $S^o_t$ ): Represented as a Disjunctive Graph ( $G=\{V, E\}$ $G = {V, E}$ ).
- Vertices: Operations and Machines.
- Features: Binary indicators for scheduling status, machine type, and a Lower Bound (LB) scalar representing the minimum remaining time for a job. Machine vertices include the ratio of scheduled operations.
- Architecture: Encoded using a Graph Isomorphism Network (GIN) to capture graph topology and message passing.
AGV State ( $S^{agv}_t$ ): A vector of six scalars per AGV, including earliest pick-up time, travel times, and machine availability.
- Architecture: Encoded using a Multi-Layer Perceptron (MLP).

Action Space:

Joint Action: A pair $(a_o, a_{agv})$ where $a_o$ is the selected operation and $a_{agv}$ is the assigned AGV.
Policy: The AGV policy is conditional on the Job policy's action ( $\pi(a_{agv}|S^{agv}_t, a_o)$ ).

Reward Function:

Sparse reward based on the negative makespan ( $-C_{max}$ ) normalized by a lower bound. This forces agents to optimize the global objective rather than local efficiency.

B. Training Modalities

The study compares two distinct training strategies:

Joint Training: Both agents are learnable parameters trained simultaneously using MAPPO (Multi-Agent Proximal Policy Optimization). They learn cooperative behaviors end-to-end.
Modular Training: Agents are trained independently. One agent is a learnable policy (GNN or MLP), while the other is a fixed Dispatching Rule (DR) (e.g., Shortest Processing Time, First Come First Serve). The best modular combinations are identified post-hoc.

C. Experimental Design

Baselines: 10 operation selection rules $\times$ 4 AGV selection rules = 40 DR combinations.
Sensitivity Analysis: The authors introduce two key metrics to analyze the "Coordination Gap" (performance difference between Joint and Modular):
- Resource Scarcity ( $\rho$ ): Ratio of AGVs to Jobs ( $k/n$ ).
- Temporal Dominance ( $\tau^*$ ): A normalized index representing the balance between processing time and transportation time.
Evaluation: Performance is measured using Relative Percentage Increase (RPI) against the best DR baseline and Win Rate (WR).

3. Key Contributions

Novel Training Framework: A flexible architecture allowing independent agent learning while maintaining compatibility for joint evaluation, enabling a direct comparison of training modalities.
Systematic Sensitivity Analysis: The first rigorous quantification of the "coordination gap" in JSSPT, identifying specific environmental conditions where joint training is essential.
Characterization of Interdependence: A mathematical characterization of how resource scarcity and temporal dominance non-linearly impact the efficacy of joint vs. modular learning.
Practical Guidelines: Empirical evidence guiding decision-makers on when to invest in complex joint training versus simpler modular approaches.

4. Results

A. Overall Performance

Joint Superiority: The Joint Solver ( $J_0 A_0$ ) consistently outperforms all modular solvers and Dispatching Rule baselines.
Average Gain: The joint solver achieves an average 4.2% improvement in makespan compared to the best global DR combination.
Modular Variance: Modular solvers show high variance; their success depends heavily on the specific heuristic pairing used during independent training.

B. The Coordination Gap & Environmental Factors

The study identifies a non-linear relationship between environmental conditions and the benefit of joint training:

Balanced Environments (High Coordination Gap): In regimes where resources are neither scarce nor abundant, and processing/transport times are balanced, joint training yields the highest gains (up to 8.5% RPI). Here, the system relies on the coupling between job scheduling and AGV allocation.
Bottleneck Environments (Low Coordination Gap):
- Transport-Constrained: Severe AGV scarcity ( $\rho < 0.4$ ).
- Process-Constrained: Dominant processing times with abundant AGVs ( $\rho > 0.8$ ).
- Finding: In these regimes, the performance gap narrows significantly (dropping to 0.6% - 1.5%). When a single bottleneck dominates the system, the marginal benefit of holistic coordination diminishes because the system is constrained by that single factor regardless of agent cooperation.

C. Statistical Validation

Regression Analysis: An Ordinary Least Squares (OLS) model confirms that Bottleneck Dominance (single task constraint) and Task Balance significantly predict the coordination gap ( $R^2 = 0.67$ ).
Key Insight: Negative coefficients for bottleneck variables indicate that as a single task dominates, the advantage of joint training decreases. Positive coefficients for the balance metric indicate that balanced systems benefit most from joint learning.

5. Significance and Implications

Strategic Resource Allocation: The paper provides a decision framework for industrial practitioners. If a factory operates in a bottleneck regime (e.g., chronic AGV shortage or extremely slow machines), the computational cost of joint MARL training may not be justified; a well-tuned modular approach (or even advanced dispatching rules) may suffice.
Optimization in Flexible Factories: In balanced, flexible environments (typical of high-performance manufacturing), joint training is essential to unlock the full potential of decentralized systems by optimizing the complex interplay between production and logistics.
Future Directions: The work lays the groundwork for extending MARL to more complex scenarios, such as flexible job shops with machine selection agents and multi-objective optimization (energy, cost, delay).

In summary, the paper demonstrates that while Joint Training is generally superior, its advantage is context-dependent. The "coordination gap" is largest when production and logistics are tightly coupled and balanced, and smallest when the system is dominated by a single, severe constraint.