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

Xiangjie Xiao; Cong Zhang; Wen Song; Zhiguang Cao

cs.LGMar 7, 2026

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

Authors: Xiangjie Xiao, Cong Zhang, Wen Song, Zhiguang Cao

Organizations: 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

Abstract

Neural approaches to the Flexible Job Shop Scheduling Problem (FJSP), particularly those based on deep reinforcement learning (DRL), have gained growing attention in recent years. However, existing methods rely on complex feature-engineered state representations (i.e., often requiring more than 20 handcrafted features) and graph-biased neural architectures. To reduce modeling complexity and advance a more generalizable framework for FJSP, we introduce ReSched, a minimalist DRL framework that rethinks both the scheduling formulation and model design. First, by revisiting the Markov Decision Process (MDP) formulation of FJSP, we condense the state space to just four essential features, eliminating historical dependencies through a subproblem-based perspective. Second, we employ Transformer blocks with dot-product attention, augmented by three lightweight but effective architectural modifications tailored to scheduling tasks. Extensive experiments show that ReSched outperforms classical dispatching rules and state-of-the-art DRL methods on FJSP. Moreover, ReSched also generalizes well to the Job Shop Scheduling Problem (JSSP) and the Flexible Flow Shop Scheduling Problem (FFSP), achieving competitive performance against neural baselines specifically designed for these variants.

Figures & tables

Panel of Figure 1 — Figure 1: (a) Illustration of the formulation for a 2‑job, 2‑operation, 2‑machine (2-2-2) FJSP instance. (b) Changes in topology and O2M/O2O Connection between two steps for a 3-3-3 instance.

Figure 2: The ReSched framework. The state consists of four information, resulting in four key features (available time and minimum duration for operation; available time for machine; duration), and incorporates three (underlined) architectural enhancements for Transformer-based network. For decision-making module, we concatenate the embeddings of each feasible operation–machine pair, feed them into an MLP to obtain a score.

Table 1: Results on datasets: in-distribution (top); out-of-distribution (middle); benchmark (bottom)

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: The illustration of JSSP and FFSP instances, respectively.

setting	Obj. $\downarrow$	Avg. $\Delta(\%)\downarrow$
DANIEL	589.44	56.28
Del Global	589.12	56.19
Del Global MA	588.66	56.07
Del Gloabl MA P(-P6)	588.76	56.10
Del Gloabl MA P(-P6) O(-O2379)	587.68	55.81

Appendix

Table 3: Ablation study on DANIEL.

Ablation		In-Distribution	Out-of-Distribution		Open Benchmark	Avg. $\Delta(\%)\downarrow$ 1
Ablation		$10\times 5$	$30\times 10$	$40\times 10$	Brandimarte	Avg. $\Delta(\%)\downarrow$ 1
ReSched	Gap(%) $\downarrow$	12.25	3.44	2.54	9.08	+0.00
ReSched	$\Delta(\%)\downarrow$	0.00	+0.10	0.00	0.00	+0.00
Connection	Gap(%) $\downarrow$	16.42	6.74	3.83	14.48	+3.54
Connection	$\Delta(\%)\downarrow$	+4.17	+3.30	+1.29	+5.40	+3.54
Relative Available Time	Gap(%) $\downarrow$	13.33	5.02	3.77	14.84	+2.41

Appendix

Table 4: Ablation study on ReSched .

In-distribution
Dataset	DANIEL	ReSched -Avg.	ReSched -Orig.	Seed1	Seed2	Seed3
$\text{SD}_{1}$ -10 $\times$ 05	10.87	11.75	12.25	11.40	12.33	11.03
Out-of-distribution
$\text{SD}_{1}$ -30 $\times$ 10	5.10	3.10	3.44	2.46	3.39	3.09
$\text{SD}_{1}$ -40 $\times$ 10	3.65	2.23	2.54	1.64	2.46	2.26
$\text{SD}_{2}$ -30 $\times$ 10	14.85	9.04	8.79	9.35	9.78	8.22

Appendix

Table 5: Performance of ReSched trained with REINFORCE across four random seeds.

Size	PDRs				DRL-based		Opt. Rate(%) 1
	SPT	MWKR	FDD/MWKR	MOPNR	L2D	ReSched
	SPT	MWKR	FDD/MWKR	MOPNR	L2D	$10\times 10$
$6\times 6$	42.0	34.6	24.0	29.2	17.7	7.0	100
$10\times 10$	50.0	42.6	36.6	36.5	22.3	9.5	100
$15\times 15$	59.2	52.6	45.1	42.6	26.7	14.3	99
$20\times 20$	62.0	58.6	49.6	45.5	29.0	15.0	4

Appendix

Table 6: Performance on synthetic datasets of JSSP.

Size	PDRs				DRL-based		UB 1
	SPT	MWKR	FDD/MWKR	MOPNR	L2D	ReSched
	SPT	MWKR	FDD/MWKR	MOPNR	L2D	$10\times 10$
$20\times 15$	64.1	62.1	53.6	49.2	39.0	23.7 2	3023.8
$20\times 20$	64.6	58.2	52.5	45.2	37.7	22.2	3472.6
$30\times 15$	62.6	60.9	54.1	47.1	41.9	27.8	3879.0
$30\times 20$	65.9	63.2	60.1	52.0	39.5	28.3	4248.4

Appendix

Table 7: Performance on DMU benchmark of JSSP.

	Greedy			Sampling
setting	FFSP20	FFSP50	FFSP100	FFSP20	FFSP50	FFSP100
Matnet20	28.05	52.58	93.00	27.31	52.36	93.40
Matnet50	27.78	52.05	92.17	27.05	51.55	91.86
Matnet100	27.64	51.79	91.79	27.09	51.40	91.50
ReSched20	26.65	51.24	92.28	25.12	49.65	90.80

Appendix

Table 8: Performance on FFSP.

Figure 5: Illustration of the KV cache mechanism in ReSched .

\mathcal{L}_{\text{policy}}=-\mathbb{E}_{t\in\mathcal{B}}\!\left[\min\!\big(r_{t}\hat{A}_{t},\,\mathrm{clip}(r_{t},1-\varepsilon,1+\varepsilon)\hat{A}_{t}\big)\right];

Appendix

Algorithm 2 Training ReSched with PPO

Table 9: Results on FJSP: in-distribution (top); out-of-distribution (middle); benchmark (bottom)

In-distribution
Dataset	Est LB	Est Mean	$\Delta$ -Makespan
$\text{SD}_{1}$ -10 $\times$ 05	12.25	12.56	13.05
Out-of-distribution
$\text{SD}_{1}$ -30 $\times$ 10	3.44	3.29	3.30
$\text{SD}_{1}$ -40 $\times$ 10	2.54	2.15	2.41
$\text{SD}_{2}$ -30 $\times$ 10	8.79	9.19	7.53

Appendix

Table 10: Effect of different reward on the performance of ReSched .

In-distribution
Dataset	ReSched -0.99-Avg.	ReSched -1.0-Avg.	ReSched -1.0-seed1	ReSched -1.0-seed2	ReSched -1.0-seed3
$\text{SD}_{1}$ -10 $\times$ 05	11.75	11.75	11.41	11.76	12.07
Out-of-distribution
$\text{SD}_{1}$ -30 $\times$ 10	3.10	3.10	2.63	3.69	2.97
$\text{SD}_{1}$ -40 $\times$ 10	2.23	2.19	2.00	2.51	2.06
$\text{SD}_{2}$ -30 $\times$ 10	9.04	10.03	8.28	11.58	10.22

Appendix

Table 11: Effect of the discount factor

\gamma

on the performance of ReSched .

Dataset	Avg. machines/oper	HGNN 10 $\times$ 5	DANIEL 10 $\times$ 5	ReSched 10 $\times$ 5
Hurink (edata)	1.15	15.53	16.33	15.48
Hurink (rdata)	2	11.15	11.42	10.18
Hurink (vdata)	$m/2$	4.25	3.28	3.48

Appendix

Table 12: Perfprmance degradation analysis for RL approaches.

Flexible Job Shop Scheduling

See all 14 papers

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
PLAN: Parallel Liquid-Inspired Approximation Network for Efficient Representation Learning in Flexible Job Shop Scheduling
Aug 4, 2026Dhivya Dharshini Kannan, Wei Zhang, Jieyi Bi +5Efficient Neural Network Inference Liquid Neural Networks
Singapore Institute of Technology (SIT) · Nanyang Technological University (NTU) · Shanghai Jiao Tong University +1
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

May 21, 2026J/K move · Enter open · S save

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

Yu Tang, Muhammad Zakwan, Efe Balta, John Lygeros+1

Centre for Artificial Intelligence, Zurich University of Applied Sciences, Switzerland · Inspire AG, Zurich, Switzerland · Automatic Control Laboratory, ETH Zurich, Switzerland

Reinforcement Learning Flexible Job Shop Scheduling Combinatorial Optimization Job Shop Scheduling

Open paper AskPDF arXiv

The Flexible Job Shop Scheduling Problem (FJSP) is the optimal allocation of a set of jobs to machines. Two primary challenges persist in FJSP: the unpredictable arrival of future jobs and the combinatorial complexity of the problem, rendering it intractable for conventional mixed-integer linear programming solvers. This paper proposes an event-based \gls{DRL} approach to solve FJSP with random job arrivals. Specifically, we employ the Proximal Policy Optimization algorithm and use lightweight Multi-Layer Perceptrons to train the \gls{DRL} agent for minimizing the total completion time of all jobs. We design the state representation to be directly accessible from the environment, and limit the learning agent to selecting from among a set of well-established dispatching rules. Simulations show that our \gls{DRL} approach outperforms any of the individual dispatching rules on datasets with varying heterogeneity and job arrival rates. We benchmark our \gls{DRL} against an arrival-triggered mixed-integer linear programming solution and show that our method achieves good performance especially when the datasets are heterogeneous.

Abstract

Flexible Job Shop Scheduling

Explore similar work

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

PLAN: Parallel Liquid-Inspired Approximation Network for Efficient Representation Learning in Flexible Job Shop Scheduling

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