Learning Flexible Job Shop Scheduling under Limited Buffers and Material Kitting Constraints

Shishun Zhang; Juzhan Xu; Yidan Fan; Chenyang Zhu; Ruizhen Hu; Yongjun Wang; Kai Xu

cs.AIFeb 27, 2026

Learning Flexible Job Shop Scheduling under Limited Buffers and Material Kitting Constraints

Authors: Shishun Zhang, Juzhan Xu, Yidan Fan, Chenyang Zhu, Ruizhen Hu, Yongjun Wang, Kai Xu

Organizations: National University of Defense Technology · Shenzhen University · Institute of AI for Industries, Chinese Academy of Sciences

Abstract

The Flexible Job Shop Scheduling Problem (FJSP) originates from real production lines, while some practical constraints are often ignored or idealized in current FJSP studies, among which the limited buffer problem has a particular impact on production efficiency. To this end, we study an extended problem that is closer to practical scenarios--the Flexible Job Shop Scheduling Problem with Limited Buffers and Material Kitting. In recent years, deep reinforcement learning (DRL) has demonstrated considerable potential in scheduling tasks. However, its capacity for state modeling remains limited when handling complex dependencies and long-term constraints. To address this, we leverage a heterogeneous graph network within the DRL framework to model the global state. By constructing efficient message passing among machines, operations, and buffers, the network focuses on avoiding decisions that may cause frequent pallet changes during long-sequence scheduling, thereby helping improve buffer utilization and overall decision quality. Experimental results on both synthetic and real production line datasets show that the proposed method outperforms traditional heuristics and advanced DRL methods in terms of makespan and pallet changes, and also achieves a good balance between solution quality and computational cost. Furthermore, a supplementary video is provided to showcase a simulation system that effectively visualizes the progression of the production line.

Figures & tables

Fig. 1: Comparison of the makespan, pallet changes, and computation time (the closer to the bottom and left, the better). Our method establishes an effective balance between solution quality and computational cost.

Fig. 2: FJSP with limited buffer and material kitting constraints. Green, white, and yellow circles indicate scheduled, unscheduled, and currently being scheduled operations. Parts of the same job share color; identical shapes denote the same part type. Operation $O_{22}$ is subject to limited buffer and kitting constraints: (1) Six pallets are available, each preloaded with parts; (2) Job $J_{2}$ ’s parts must be split across two pallets, but one type is not in existing categories; (3) A pallet must be replaced with an empty one; (4) Once an empty pallet is available, all parts can be properly assigned.

Fig. 3: Example of state transition. At timestep $t$ , both unscheduled operations $O_{32}$ and $O_{22}$ are subject to buffer constraints; therefore, the buffer node is connected to both of them. The algorithm then prepares to execute the $O_{22}-M_{2}$ action. Upon execution, the graph transitions to state $s_{t+1}$ . The newly scheduled operation node is marked green, and its associated connections are updated accordingly.

Fig. 4: Heterogeneous GNN uses multiple state features as input, and outputs the O-M pair decision.

Fig. 5: Message passing between the buffer and the part-sorting operations,

w

is the weight of the edge

Size ( $n\times m$ )	$n_{i}$ 1	$\|\mathcal{M}_{ij}\|$ 2	$\bar{p}_{ij}$ 3	$n_{ps}$ 4	$c_{j}$ 5	$C$ 6	$t_{p}$ 7	$t_{r}$ 8	$P$ 9
$10\times 5$	U(4, 6)	U(1, 5)	U(1, 20)	1	U(3, 5)	10	2	5	6
$20\times 5$	U(4, 6)	U(1, 5)	U(1, 20)	1	U(3, 5)	10	2	5	6
$15\times 10$	U(8, 12)	U(1, 10)	U(1, 20)	1	U(3, 5)	10	2	5	6
$20\times 10$	U(8, 12)	U(1, 10)	U(1, 20)	1	U(3, 5)	10	2	5	6
$30\times 10$	U(8, 12)	U(1, 10)	U(1, 20)	1	U(3, 5)	10	2	5	6
$40\times 10$	U(8, 12)	U(1, 10)	U(1, 20)	1	U(3, 5)	10	2	5	6

TABLE I: Parameters of the Synthetic FJSP-LB-MK Datasets

Size ( $n\times m$ )	$n_{i}$	$\|\mathcal{M}_{ij}\|$	$n_{ps}$	$c_{j}$	$C$	$t_{p}$	$t_{r}$	$P$
A: $20\times 16$	8	$\{5:1,1:3,2:4\}$	1	1-11	18–47	14	90	18
B: $20\times 12$	9	$\{8:1,1:4\}$	3	1–12	16–38	14	180	48
C: $20\times 10$	9	$\{8:1,1:2\}$	3	1–9	17–28	14	180	24
D: $20\times 12$	11	$\{10:1,1:2\}$	4	1–8	26–55	14	90	20

TABLE II: Parameters of the Real Production Line Dataset

Parameter	Value
lr (learning rate)	2e-4
gamma (discounting factors)	1.0
K_epochs (update epoch in PPO)	3
A_coeff (weight of policy loss)	1
vf_coeff (weight of value loss)	0.5
entro_coeff (weight of entropy loss)	0.05

TABLE III: Training parameters.

Panel of Figure 9 — Fig. 6: Gantt Chart Comparison (Test Case: 10j5m test_set instance). The white rectangles represent time delays caused by pallet changes. Rectangles of other colors represent the time intervals when parts from different jobs are loaded onto the pallet (where $T_{n}$ denotes the $n$ -th type of part).

		PDRs					Greedy strategy		Sampling strategy
Size		FIFO	MOR	SPT	MWR	LWR	[ 15 ]	Ours	[ 15 ]	Ours	OR-Tools 1
$10\times 5$	Makespan	198.11	189.27	193.23	191.74	201.81	177.02	169.85	171.48	158.25 *	142.45 (9.01)
	Gap 2	39.1%	32.9%	35.6%	34.6%	41.7%	24.3%	19.2%	20.4%	11.1%
	Time (s)	0.16	0.16	0.16	0.16	0.16	0.39	0.43	0.68	0.71
	Switches	15.52	15.02	15.02	15.08	14.93	14.50	12.10	12.01	9.65
$20\times 5$	Makespan	359.06	373.83	361.26	373.95	373.54	342.69	300.70	327.17	296.88	279.45 (20.68)

TABLE IV: Performance on Synthetic FJSP-LB-MK Datasets.

		PDRs					Greedy strategy		Sampling strategy
Dataset		FIFO	MOR	SPT	MWR	LWR	[ 15 ]	Ours	[ 15 ]	Ours	OR-Tools
A	Makespan	8946.92	8946.92	9188.00	8618.30	10413.75	8057.74	7753.52	7656.92	7392.72	6706.06 (18.85)
	Gap	33.4%	33.4%	37.0%	28.5%	55.3%	20.2%	15.7%	14.2%	10.2%
	Time (s)	0.92	0.92	0.92	0.92	0.92	2.17	2.31	4.57	4.77
	Switches	20.36	20.36	21.93	15.28	27.12	16.36	18.34	15.86	16.42
B	Makespan	11867.21	11867.21	12731.46	12425.45	12902.02	11372.99	10855.39	10737.66	10207.62	9949.58 (3.33)

TABLE V: Performance on Real Production Line Datasets.

	Makespan		Switches
	Value	Gap_to_ours	Value	Gap_to_ours
PS+SwEst	183.94	8.3%	15.41	27.4%
PS+Type	187.73	10.5%	15.42	27.4%
Type+SwEst	172.41	1.5%	12.08	-0.2%
PS+Type+SwEst (Ours)	169.85	0.0%	12.10	0.0%

TABLE VI: Effectiveness of Key State Features.

	Makespan		Switches
	Value	Gap_to_ours	Value	Gap_to_ours
Base	172.62	1.6%	12.18	0.7%
Pallet_AllOps	172.80	1.7%	12.22	1.0%
Pallet_SortOnly	171.03	0.7%	12.31	1.7%
Pallet_SortOnly_InverseWeight	170.82	0.6%	12.28	1.5%
Pallet_SortOnly_Weighted (Ours)	169.85	0.0%	12.10	0.0%

TABLE VII: Effectiveness of Selective Connectivity and Cost-sensitive Propagation.

Panel of Figure 14 — Fig. 7: Training curve comparison on State Features.

Panel of Figure 15 — Fig. 8: Training curve comparison on selective connectivity and cost-sensitive propagation.

Flexible Job Shop Scheduling

See all 14 papers

Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling
Mar 3, 2026Jiaqi Wang, Zhiguang Cao, Peng Zhao +4Flexible Job Shop Scheduling Job Shop Scheduling
Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University · College of Software, Jilin University · Singapore Management University +2
Deep Reinforcement Learning for Flexible Job Shop Scheduling with Random Job Arrivals
May 21, 2026Yu Tang, Muhammad Zakwan, Efe Balta +2Reinforcement Learning Flexible Job Shop Scheduling
Centre for Artificial Intelligence, Zurich University of Applied Sciences, Switzerland · Inspire AG, Zurich, Switzerland · Automatic Control Laboratory, ETH Zurich, Switzerland
RESCHED: Rethinking Flexible Job Shop Scheduling from a Transformer-based Architecture with Simplified States
Mar 7, 2026Xiangjie Xiao, Cong Zhang, Wen Song +1Flexible Job Shop Scheduling Job Shop Scheduling
School of Computing and Information Systems, Singapore Management University, Singapore · College of Computing and Data Science, Nanyang Technological University, Singapore · Institute of Marine Science and Technology, Shandong University, China

Mar 3, 2026J/K move · Enter open · S save

Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling

Jiaqi Wang, Zhiguang Cao, Peng Zhao, Rui Cao+3

Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University · College of Software, Jilin University · Singapore Management University+2

Flexible Job Shop Scheduling Job Shop Scheduling Combinatorial Optimization RL for Combinatorial Optimization Heterogeneous GNNs

Open paper AskPDF arXiv

The rise of smart manufacturing under Industry 4.0 introduces mass customization and dynamic production, demanding more advanced and flexible scheduling techniques. The flexible job-shop scheduling problem (FJSP) has attracted significant attention due to its complex constraints and strong alignment with real-world production scenarios. Current deep reinforcement learning (DRL)-based approaches to FJSP predominantly employ constructive methods. While effective, they often fall short of reaching (near-)optimal solutions. In contrast, improvement-based methods iteratively explore the neighborhood of initial solutions and are more effective in approaching optimality. However, the flexible machine allocation in FJSP poses significant challenges to the application of this framework, including accurate state representation, effective policy learning, and efficient search strategies. To address these challenges, this paper proposes a Memory-enhanced Improvement Search framework with heterogeneous graph representation--MIStar. It employs a novel heterogeneous disjunctive graph that explicitly models the operation sequences on machines to accurately represent scheduling solutions. Moreover, a memoryenhanced heterogeneous graph neural network (MHGNN) is designed for feature extraction, leveraging historical trajectories to enhance the decision-making capability of the policy network. Finally, a parallel greedy search strategy is adopted to explore the solution space, enabling superior solutions with fewer iterations. Extensive experiments on synthetic data and public benchmarks demonstrate that MIStar significantly outperforms both traditional handcrafted improvement heuristics and state-of-the-art DRL-based constructive methods.

Abstract

Flexible Job Shop Scheduling

Explore similar work

Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling

Deep Reinforcement Learning for Flexible Job Shop Scheduling with Random Job Arrivals

RESCHED: Rethinking Flexible Job Shop Scheduling from a Transformer-based Architecture with Simplified States