Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling
Authors: Jiaqi Wang
Zhiguang Cao
Peng Zhao
Rui Cao
Yubin Xiao
Yuan Jiang
You Zhou
Venue: NeurIPS 2025 poster ()
Keywords: Flexible Job-Shop Scheduling Problem
Graph Neural Network
Reinforcement Learning
Combinatorial Optimization
Primary area: optimization
TL;DR: We propose a memory-enhanced improvement search framework based on deep reinforcement learning to solve flexible job-shop scheduling problems.

Abstract: 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 $\textbf{M}$emory-enhanced $\textbf{I}$mprovement $\textbf{S}$earch framework with he$\textbf{t}$erogeneous gr$\textbf{a}$ph $\textbf{r}$epresentation—$\textit{MIStar}$. It employs a novel heterogeneous disjunctive graph that explicitly models the operation sequences on machines to accurately represent scheduling solutions. Moreover, a memory-enhanced 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 $\textit{MIStar}$ significantly outperforms both traditional handcrafted improvement heuristics and state-of-the-art DRL-based constructive methods.

Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling
Jiaqi Wang!2, Zhiguang Cao', Peng ! :3; Rui Cao Yubin Xiao Yuan Jiang You Zhou
Key Laboratory of Symbolic Computation and Knowledge Engineering Ministry of Education, Jilin University
*College of Software, Jilin University
CColleee of Computer Science and Technology, Jilin University
"Singapore Management University *Nanyang Technological University
{jqwang24, pengzhao23, ruicao24, xiaoyb21) (iaoyb21)@mailss j.u. edu. zhiguangcaoBoutlook com, yuan0050e. ntu, edu. sg, zyou@jlu. edu.iuluu.uuccm edu, cn
Abstract
The rise of smart manufacturing under Industry 4.0 introduces mass customization and dynamic production, demanding more advanced and flexible scheduling tech- niques. The flexible job-shop scheduling problem (FJSP) has attracted significant attention due to its complex constraints and strong alignment with real-world pro- duction scenarios. Current deep reinforcement learning (DRL)-based approaches to FJSP predominantly employ constructive methods. While effective, they often fall short of reaching (near- )optimall solutions. In contrast, improvement-be based meth- ods iteratively explore the neighborhood of initial solutions and are more effective in approaching optimality. However, the flexible machine allocation 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-enhanceee framework with heterogeneous graph representationnMMMirrr It employs a novel heterogeneous disjunctive graph that explicitly models the operation sequences machines to accurately represent scheduling solutions. Moreover, a memory- enhanced heterogeneous graph neural network (MHGNN) is designed for feature extraction, leveraging historical trajectories to enhance the decision pocciion--aaing capa- bility of the policy network. Finally, parallel greedy search strategy adopted explore the solution space, enabling superior solutions with fewer iterations. Exten- sive experiments on synthetic data and public benchmarks demonstrate that M/Star significantly outperforms both traditional handcrafted improvement heuristics and state-of-the-ars DRL-based constructive methods.
Improvement Search
Introduction
As an emerging paradigm integrating advanced manufacturing and digital technologies, Industry 4.0 is transforming production toward dynamic, large-scale, and customized manufacturing 2 The job-shop scheduling problem (ISP) [3) classic NP-hard combinatorial optimization problem (COP), has been widely studied and plays critical role in manufacturing systems [4] As an extension of JSP [5] 6) the flexible job-shop scheduling problem (FJSP) allows each operation to be assigned to
"Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

one of several eligible machines [7], making it more suitable in handling the flexibility and diversity of fask-resource relations in new manufacturing paradigms (8) While this increased flexibility enables FJSP to better meet the demands of mass customization and automation in smart manufacturing (SM)
S
9
10],
it also introduces greater challenges developing effective solution strategies []].
Recent advances in neural models have shown remarkable effectiveness in solving complex COPs
15 16 17 [8). As one promising paradigm among them, Deep Reinforce- ment Learning (DRL) formulates the scheduling task as a Markov decision process (MDP), learning a parameterized policy network that receives scheduling state as input and outputs feasible actions. DRL approaches to scheduling can be categorized into construction and improvement [19 20 Con- struction methods build schedules by assigning an operation to a machine at each step, progressively extending partial solutions to complete ones [21]. However, their performance heavily relies on state representations [22]. Many studies (3 24
12
13
14
25 26 model scheduling states using disjunctive graphs, but the incompleteness of partial solutions often leads to the omission of important components [2] (e.g., the disjunctive ares among undispatched operations (33)- Additionally, disjunctive graphs struggle to incorporate essential work-in work-in-progress information required during construction [2]] (e.g., current machine load and job status). These limitations lead to suboptimal schedules and reduce their adaptability in SM. In contrast, improvement methods start from a complete initial solution and iteratively refine it through small adjustments [27]. As the MDP state represents a fully scheduled solution, it avoids the information loss inherent in partial ones. Morcover, the structure of disjunctive graphs naturally encodes topological relationships among operations (28), enabling complete schedules to be effectively represented with all necessary information (1]. This better supports the nigh-performance demands of complex scheduling scenarios in SM.
Despite the promising results, most existing DRL-based improvement methods focus only on nonflex- ible problems, such as the JSP [21 29]. The increased complexity of FJSP over JSP poses significant challenges for designing effective improvement approaches. First, the one-to-many relationships between operations and machines make the scheduling state more intricate (8) challenging its rep- resentation and demanding more expressive neural networks for encoding. Second, improvement methods explore solutions through local moves within neighborhoods. In FJSP, due to the complex decisions involving both operation sequencing and machine assignment (6]. this process requires tailored local moves as actions in the MDP (27] Moreover, the existence of flexibility in FJSP signif- icantly enlarges the solution space, increasing the risk of local optima entrapment and necessitating more efficient search strategies to reduce the extensive number of iterations for convergence [27 30.
To address the above challenges, we propose DRL-based improvement heuristic framework for FJSP. First, to represent complex scheduling states, we design a novel heterogeneous disjunctive graph by adding machine nodes with directed hyper-edges to encode the complete solution, effectively capturing critical information about operation sequencing on machines. We also propose a hetero- gencous graph neural network and enhance its exploratory capability via a memory module, which stores compact representations of visited solutions and retrieves relevant information to enrich the current state embedding. This module leverages historical schedules to improve decision- making and alleviate local optima issues. Second, we construct the action space based on the Nopt2 neighborhood structure, enabling simultaneous adjustment to operation sequences and machine assignments, and further reduce its dimensionality via constraint relationships to enhance search efficiency. Finally, we propose a parallel greedy exploration strategy that evaluates multiple candidate actions at each step, achieving comparable solution quality with fewer iterations. Extensive experiments on synthetic data and public benchmarks demonstrate the superior performance of our approach in solving FJSP.
The contributions of this paper are summarized as follows: 1) The first DRL-based improvement heuristic framework for JJSP-MIStar capable of learning size-agnostic policies that outperform both traditional handcrafted improvement and state-of-the-art DRL construction methods. 2) An MDP formulation with heterogeneous disjunctive graph for state representation of complete scheduling solutions in FJSP, and an action space that enables simultaneous adjustments to operation sequences and machine assignments. 3) A memory-enhanced heterogeneous graph neural network (MHGNN) that leverages historical solutions to improve decision-making and alleviate local optima issues. 4) A parallel greedy exploration strategy that improves efficiency of solution space exploration.
2

---

2
Related work
This section reviews the limitations of DRL-based construction methods and recent advances in improvement methods, highlighting the challenges in solving FJSP.
Construction methods construct complete solutions by assigning operation to a machine each step. Compared to the heuristic guidance offered by conventional dispatching rules, DRL employs
DNNs to score actions, but their effectiveness heavily relies on state representations 22 B1 32]
Early
approaches (33 34 35 36) extract multiple general state features as input, which overcompresse presses state
information and neglects the structural nature of FISP 337 Recent works R 23
24
38
39 integrate
GNNs with DRL. by modeling scheduling states as graphs, learning rich graph embeddings with
structural information for decision-making However, the incompleteness of partial solutions often
results in the omission of important components [21] (e.g., the disjunctive ares among undispatched operations (3]), and work-in-progee progress information required during construction is hard explicitly represent in disjunctive graphs [21], leading to suboptimal performance.
Improvement methods iteratively refine solutions by performing local moves within the neighborhood. Conventional methods use handcrafted rules to greedily select the best solution at each step, but suffer
from myopia and costly neighborhood evaluation [21]. Recent studies [1] 29] 41 have addressed
these limitations by leveraging deep policy networks in DRL. to directly generate local moves. Such
44 and have since been adapted to scheduling domains. By representing complete solutions as MDP states through disjunctive graphs, these approaches circumvent the inaccuracies in state representation that arise from partial solutions (21). Falkner et al. (40) train a GNN-based JSP solver using DRL to adapt local search strategies according problem-specific features. However, their design of local operators relies heavily on expertise. limiting the generalizability. Closer to our work, Zhang et al. [2] [29 represent JSP solutions with disjunctive graphs and define the action space as set of exchangeable operation pairs based on the N5 neighborhood structure [5], training GNN- based policy network via DRI.. While effective for JSP, extending this framework to FJSP- flexible machine assignments better suit mass customization and dynamic production in Industry 4.0
DRL-based improvement heuristics were initially applied routing problems 42 43
[9] 10
faces critical challenges. First, conventional disjunctive graphs lack machine nodes, making them insufficient for complex states of FJSP. In addition, the N5-based action design does not account for machine assignment adjustments(See Appendix A for analysis). Furthermore, the increased flexibility of FJSP over JSP enlarges the solution space and aggravates local optima issues in local search [46).
An effective approach this issue is leveraging memory mechanisms by incorporating past experience to promote exploration [47]. Garmendia et al. [48] maintain a tabu memory to filter redundant visits in routing problems. yet such methods fail to integrate historical data into the decision- making of the policy. leaving historical information underutilized. A closely related work is MARCO [7], which aggregates contextually relevant information from the memory module to enhance state embeddings and improve policy decisions. However, its application in improvement methods is limited to simple binary optimization problems (i.e., maximum cut and maximum independent set), and its approach to information aggregation is unsuitable for the complex constraints in FJSP. In contrast, we simplify scheduling representations, which are stored in the memory module and aggregated via a soft voting mechanism [49] to better accommodate the intricate constraints of FJSP.
M2
M2
6v
Oa
(b)
(c)
Figure 1 Graph representations of FJSP. (a) FJSP instance in a disjunctive graph; (b) feasible solution in disjunctive graph; (c) feasible solution in our graph.
3 Preliminaries
This section presents the formulation of FISP, disjunctive graphs, and Nopt2 neighborhood structure.
3

---

Flexible job shop scheduling problem. FJSP is defined as follows: Given a set of jobs J = (2...2..... , and set of machines M {M, M2.... M each job J, consists of n; J. The operations within a job must be processed
operations denoted by O= = (O;,: Oig:'... Oin, in a specific order, known as precedence constraints. Each operation Oiz can processed by any machine Ms for a processing time pt from its compatible set Maj S M,, and the processing is non-preemptive. Each machine can process only one operation at a time. The objective of FJSP is to assign each operation to compatible machine and determine its processing sequence on the selected machine to minimize the makespan, defined as the maximum completion time Cmax = m (Ci where City denotes the completion time of Oig.
Disjunctive graph. An FISP instance can be represented by a disjunctive graph G = (O,C,)) 50 The operation set O = {O vi. j} U {Os, Or) includes all operation nodes and two dummy representing the start and end states. The conjunctive are set C' consists of directed ares that describe the precedence constraints between operations of the same job. The disjunctive comprises undirected edges, and each DD connects operations processed on the same machine M In FJSP, each operation
set DD Up
be connected to multiple disjunctive arcs. Therefore, solving FISP instance is equivalent to selecting a disjunctive arc for each node and fixing its direction to construct DAG (28). In the graph, the longest path from Os Or is called the critical path (CP), whose length represents the makespan of the solution. See Figure Ta and Tb for examples.
The Nopt2 neighbourhood Structure. Given solution s, the Nopt2 constructs the neighbour- hood N (s) as follows. First, the critical path CP(s) is identified. Then, an operation Of, on the critical path is chosen and deleted from its current processing sequence of M₁. It is reinserted into the optimal insertion interval within the sequence of an alternative compatible machine My yielding new solution s'. The optimal insertion interval is determined based on the precedence relations between the newly inserted operation and existing operations on My' ensuring that all constraints are satisfied and the makespan of s' is potentially reduced. We adopt the Nopt2 neighborhood structure [31] (Figure 2 to define the local move during the search process of MIStar. By identifying optimal insertion interval, this structure significantly reduces the size of neighborhood. The neighborhood size [Nop12(s)] is influenced by both the instance scale and the flexibility of machine selection.
Critical
O-O Insen ortical operation into optinal interval
Optimal Insertion Interval
Process list My
Figure 2 Nopt2 neighborhood structure.
4 Methodology
This section details our framework, illustrated in Figure 3
Given an FJSP instance, an initial solution is generated and transformed into heterogeneous graph, from which a memory-enhanced GNN learns embeddings. The policy network samples several local moves from the neighborhood and evaluates in parallel. The best one is executed to update the current solution. yielding new one. The process terminates after predefined search horizon. We formulate the iterative solution optimization as a MDP. This section first formalizes the MDP, then presents a novel heterogencous graph representation and the memory-enhance GNN-based policy network. Finally, we describe the parallel greedy exploration strategy and the training algorithm.
4.1 MDP Formulation
We formulate the iterative optimization process of the FJSP discrete MDP. At each step the agent, the decision-makee based on a given policy, selects an action (local move) from the action space (neighborhood), and the state transitions accordingly to represent new solution. The MDP is defined as follows.
State. The state 8 encodes complete solution and is defined by a set of feature vectors, including Xoy E I for each operation Oij and yM, E IRA for each machine Mg. detailed in Appendix B Action. The action space A, comprises local moves in the Nopt2 neighborhood, changing with

---

Parallel Exploration
Problem Instance
Best Solution
New Solution
& Rank
Mr
Yes
Machine
Terminal
Criterion
No
Multiplesampling
MHGNN
Operation node embodding
Policy Network
Machine node embedding
Historical actions embedding
Current Solution
Embedding Learning
Decision Making
Figure 3 The architecture MIStar.
the state 8t. Each action 0₁ = [0m, On, M&] denotes inserting critical operation Om before op- eration On in the processing sequence of machine Mj. where Om E (r, and O, # Os- Reward. The reward comprises two components: improvement in solution quality Tgaan and penalty for redundant solution visits ppenatyy. The term r rgainn measures the improvement over the incumbent best solution Jf (initialized as sp), and is defined as: 'gain = max (m where maximizing the cumulative reward equivalent to minimizing the makespan Crax (sā ). The term Fpenalty discourages redundant exploration by evaluating similarity between and previous states. Formally, it is computed as: Tpenalty = À x EweDnex w, where Ωopk denotes the top-K similarity scores between 8; and stored states, and À the penalty coefficient. The overall reward is defined as (se, dr) = Tgain Tpenalty. which initially dominated by makespan improvement and gradually shifts toward solution diversity improvements diminish.
ma (St4 0),
4.2 Directed Heterogeneous Graph
Conventional disjunctive graphs lack machine nodes, hindering GNNs from accurately capturing machine states in FJSP, which turn limits policies to effectively maximize machine utilization (37]. Inspired by the heterogeneous disjunctive graph H. [8], we introduce novel directed heterogeneous disjunctive graph 7. = (O, C, E) to represent scheduling solutions. In our graph, the operation and machine nodes denoted O and M, while the conjunctive arc set C and hyper-edge set & represent the processing sequences on jobs and machines, respectively. Mathematically, the hyper- edge is special edge that can join any number of vertices (52). Since machine assignment and processing sequence are fixed in FJSP solutions, we reinterpret & as directed hyper-are set of size [M]] i.c., & { (M&, Ok1 Ok2 ...., Ok where nu the number of operations processed on M₁. As shown in Figure Ic each machine nodes M2 connects to its processing sequence via directed hyper-ares E explicitly encode machine status, and the unified directed arcs in H enable clearer delineation and distinction of different solutions. See Appendix for analysis.
4.3 Memory-enhanced Heterogeneous Graph Neural Network
We propose memory-enhanced heterogeneous graph neural network (MHGNN) to extract state features from scheduling solutions. As shown in Figure MHGNN encodes the topological and sequential constraint information to generate operation embeddings, which are aggregated into machine nodes to obtain machine embeddings. Meanwhile, relevant historical information retrieved and extracted as historical action embeddings, which are then concatenated with machine and operation embeddings hefore being fed into the policy network to produce an action distribution. The following sections detail the embeddings design for operations, machines, and historical information.
5

---

4.3.1 Operation Node Embedding
Following [21], we focus on two key aspects of the FJSP graph: (1) the topology dynamically changes due the transitions of MDP state, and (2) rich semantics are conveyed through two types of neighbors-jof predecessors and machine and processing order on machines via conjunctive ares and hyper-arcs, respectively. Their joint representation is crucial for distinguishing solutions, forming the foundation for scheduling decisions.
saabecessorr-reffecttt
precedence constraints
To encode the topological information, we employ the Graph Isomorphism Network (GIN) (53). which is known for its strong discriminative power for non-isomorphic graphs. Specifically, given graph H (O, M, E, each operation Oi O is encoded into q-dimensional embedding through an I-layer GIN, where the 1-th layer computes as follows:
Vo. = MLP (1+d) 1 +
Σ
1-1
DEN(O.)
where Po, E R denotes the topological embedding of operation Oij at layer I, initialized with its raw features Xo.y. d is a learnable parameter, and N(O;,) comprises predecessor operation nodes.
To capture rich semantic relationships among operations, we apply an L-layer Graph Attention Network (GAT) with n attention heads, with the feature transformation layer I computed
TO GAT (FOr) Gr E ((O:))))
where To., E R denotes the semantic embedding of operation Oij at layer 1, initialized with raw features Xo,, We obtain the operation embedding h'o,, E 2R at layer I by concatenating the above two embeddingshe final-layer outputs form the set of operation node embeddings (ho., h vO, E O).
Operation raw feature
Operation embedding
GIN
GAT
embedding
V(S,)
HGAT
Pooling
Sampled Action
Machine raw feature
MI
Softmax
Historical
MLP
embedding
Memory
KNN
State
Action
Current solution
Figure 4 The network architecture of the memory-enhanced heterogencou GNN.
4.3.2 Machine Node Embedding
Machine embeddings are incorporated to capture machine load by aggregating the information of their associated operation nodes, serving as an essential heuristic to guide the policy in reassigning
operations from high-load machines to low-load counterparts (8] For each machine Mç, the hyper-
are E (M&, 0 022 .... Ohnz) encodes its full processing sequence. Since the importance of operations different positions varies, we employ an I.-layer heterogeneous GAT g extract machine node embeddings, where nodes with different attributes processed by distinct linear

---

transformations rather than shared one when computing the attention coefficients. The machine node embedding at layer is computed follows:
N'M HGAT (M'A) ( E N(Ma)))
where MM,, E Rst denotes machine embedding at layer I, initialized with raw features M HGAT' is a heterogeneous graph attention layer, and ((M+) comprises operations in its processing sequence. Similarly, the graph-level machine embedding is computed hM [M] EM.EM 2/.
4.3.3 Historical Action Embedding
At step t, we store the state-action pair (st, at) a memory module. To reduce storage and computational costs, we simplify the representation of by omitting node attributes and focusing solely on the processing sequence across machines (see analysis Appendix DD) Specifically, we store the pperation-machine incidence matrix L, at each step, where the non-zero element (L))i represents the processing order index of operation on machine j. and assess the similarity between the current state L, and each historical state Ly (t' < t), by computing the Frobenius inner product as their similarity score Wh, E S2, given by:
101 IMI
Wa,t' (Le, LF
ΣΣ (Liss (Le)ss ==
(4)
The k-nearest neighbors algorithm retrieves K actions with the highest similarity scores, forming the set AL, = {ai. a2...., } We aim to aggregate the information in AL, to enhance the state embedding and encourage exploration of more diverse solutions through the design of reward. However, each historical action = [Om,, . is denoted by discrete integer indices indicating operations and machines. Simply weighted averaging yields semantically invalid continuous values, failing to provide useful guidance. To address this, we adopt soft voting mechanism that aggregates the three dimensions separately based on requencyy-weihhee similarity, as follows:
Om arg max On OmE,,
Wa, 110m, =0m)
(5)
K
O = arg max OnEAY
Wh,1 11(0ms = =n)
(6)
t=1
M arg max M.E.L
Wi, I(M&, M2)
(7)
where wi,; the similarity score between 8t and the i-th most similar historical state, serving as the weight of at, I(.) is the indicator function, and Ai,, Ab, and Ai, denote the unique value in each dimension of Ar,- The aggregated action ãt, = 10m, Ön, MM] is then mapped by a single-layer MLP to the embedding space of ho and hM. resulting in the historical action embedding ha E R?
4.3.4 Decision Making
Given that machine assignments are determined in FISP solutions (i.e., for any action (Om, On, Mr On must be processed by M&), the third dimension be omitted from the action space. We enhance each operation embedding hoú by concatenating ha and ht. then feed them into the policy network to obtain intermediate vectors forming matrix Fo E R|]xa We multiply Fo by its transpose to obtain a score matrix Foo of shape [ [O]. where each element represents the priority score of an action in A.. Based on the Nopt2 neighborhood, we mask infeasible actions by setting their scores to -oo and apply softmax normalization obtain the action probability distribution. By leveraging the FJSP constraints, we reduce the space complexity of Ae from O( 2 to O(1O)), which alleviates the difficulty of learning and accelerates model convergence. detailed analysis of this space complexity reduction is provided in Appendix E
4.3.5 Training Algorithm
We propose an n-step PPO algorithm with parallel greedy exploration strategy to efficiently explore the large solution space of FJSP. At each step t, the policy samples P candidate actions
7

---

Table Results on small synthetic instances
Size
DANIEL
Sample
TIGNN
DANIEL
TONN
G15
F1
leerations
151
MiSar
GD
2000 lerratinns
01
MiSar
GD
F1
lierations
B1
MiSnn
OR-Toold
Ub. 101.57
105.59
106.75
111,57
100,00
10091
100.55
100.02
100000
100391
100.54
59.35
100,00
100,91
100.5
99.09
10x5
Gup
5.55%
9.62%
10.84%
15.94%
3,82%
4.77%
4.39%
3.84%
3.82%
4.77%
4.38%
3.70%
3.82%
4.77%
4.37%
3.50%
96.32(51)
0.26.
0.44s
0.16
0.17s
8.13
12.60s
27
27.54s
26.21s
11,23
58.71s
54.73
Dlg
192.78
207.1
19235
211.23
001.1
191.79
16
190.87
191
19
29
191.56
190.9
191.11
191.79
191.56
190.07
2005
Giap
2,4666
10.30%
5.00%
12.26%
1.68%
1,53%
1.71%
1.45%
686
1.939
1.71%
1.40%
1.68%
1.93%
1.71%
1.34%
158. 150.))
Time
1.14s
1.05s
0.33%
0.346
53,866
70.734
77.324
15.224
1.500
2.46m
2,70m
33.386
3.
160m
5.20m
5,500
1.16m
Dig
151.56
10
15061
152.10
15750
15x10
Gli
6.75%
12.07%
12.57%
305
5.87%
5.07%
5.10%
5.87%
5.97%
5.83%
4.93%
5.97%
5.83%
4.74%
143.53(75)
Time
1.90s
2.37s
01.0%s
0.50s
58.625
N6.436
90.21s
27.09%
1:97m
3.08m
3.11m
54.224
3.93m
6.81m
6.53p
1.81lm
Ob). 198,91
214.81
198.50
215.78
192.92
193:26
193.03
192.71
192.9
193.26
192.03
192.70
192.92
198.26
193.03
192.68
20x10
Gup -1.06%
9.61%
1.291
10.10%
1..56%
1.39%
1.51%
-167%
1.56%
1.38%
1.551%
-1.67%
-1.56%
11.3%%
-1.51%
-1.68% 195.9800%)
Time
2.71s
2.93s
0.68%
2,44m
2,90m
3,00m
32.91s
6.6mm
1.14m
9.86m
12.85m
13.87m
2.5lm
0by
303.25
479.37
413.75
552.80
360.17
355.22
359.00
345.05
300.1
354.22
349.05
345.43
300.17
359,22
369.06
342.50
10:5
Gap 11.90%
16.94%
86.
69.
48.45%
10.40%
8.58%
7.18%
5.77%
40%
5.58%
7.18%
5.27%
10.40%
8.58%
7.18%
4.98% 326.24(96/))
Time
0.30s
0.22s
0.16
0.20s
6.06
10.37
11.744
5.27%
12.21s
22.48
25.65
10.33c
24 79h
48.514
54.57
21 1..5%
Dig
11
61375
Gip 4.57%
49.48%
11.52%
74.05%
4.04%
4.4%
2.17%
4.5
1,95%
4.04%
3.44%
2.8445
1.78% 602.044/88)
Time
(1.76s
0.77%
01.336
0.555
28.4Hs
62.57%
72.25
11 11.55s
1.6tu
2 18m
2.52m
23.50%
3. 5.31mm
4.71m
5,23um
47-915
DS). 322.51
757.15
538.72
524.82
316.79
511000
314.77
458.23
516.79
51
510000
314.75
476.93
536.
311.00
519.23
448.77
15x10 Gup 38.53%
100.75%
56.09%
188,33
37.02%
45.48%
36.47%
29,44%
37.02
02.02%
35.48
36.47%
26.45%
37.02%
38.48% 36.47%
23.47% 377.17(228%)
Time 1.725
1.45%
0.50%
0.57%
60.34;
89.275 79801%
18.09s
2.07ml
3.17m 2.64m
37,424
4.15m
6.87m 5.500 1.31m
0bL 352.38
987.57
005.37
1036,65
549.30
542.39 535.06
$30,93
569.30
542.39
535.05
$28.92
549.30
542.39 535.00
$25.49
20x10 Gap 19.01%
112.76%
30.42%
123,34%
18.34%
16.85%
15.27%
14.3%
18.34%
16.85%
15.
25.27%
13.95%
18.34%
16. 16.85% 15.27%
13.21% 464.18(15))
Time 2,84s
2.91s
0.6%
0.71s
2.35m
3,05m
3.53m
25. 76s
4.61m
7.07m
7.54m
53.25e
9.1mm
15.33m
15.76m
1.88m
NevoR-Ticd.... 2o odaass rato oppemtly aoval paLKO ispared
{al, of....... } from Ar, evaluates their improvements in parallel, and selects the action aj yielding the greatest makespan reduction for execution. This approach enables the exploration of P solutions per iteration, producing high-quality solutions in fewer iterations and significantly reducing search time. More detailed analysis and pseudo-code of our training algorithm are presented in Appendix F
5 Experiments
In this section, we present the experimental setup, performance evaluations on datasets as well as the results of ablation studies.
synthetic and public
5.1 Experimental Settings
Datasets. We evaluate our method on both synthetic data and benchmarks. The synthetic datasets SD1 [ and SD2 [22] cover 6 scales and 100 instances per scale, and differ in distribution. For each x m FISP instance, the number of compatible machines [My for O2y is sampled from (11, m). In SD1, the number of operations per job and the average processing time Pıj of Oig are sampled from (0.88 x m, 1.2 x m) and (1, 20), respectively. The muccine-sspecifee processing time př, is drawn from U00.8 x Pey. 1.2 x Pty). While in SD2, each job has m operations, and pt is sampled from (1, 99). Benchmarks include Hurink (54) (Edata, Rdata, Vdata; 40 instances per set over 8 scales) and Brandimarte (55) (10 instances across 7 scales). Implementation details are in Appendix G
Baselines and Performance Metrics. We compare our method with two DRL-based construction methods, HGNN 8 and DANIEL 22 HGNN is heterogeneous GNN designed to encode features represented by a heterogeneous disjunctive graph, while DANIEL employs a dual-attention network on tight graph representation. Both models are retrained and tested, with results reported for sampling and greedy strategies. We also compare three hand-crafted improvement rules: gre)dy(GD) [46), best-improvement (BI), and first-improvement (FI) [56). Specifically, GD selects the solution with the smallest makespan from the neighborhood, while BI and Fl choose the best and first improving ones, respectively. A restart strategy (57) is applied in BI and FI to escape local optima by continuing the search from new initial solution. We also compares with (near-)opting solutions from Google OR-Tools, a powerful constraint programming solver, under a 1800 s time limit. For benchmarks, we report the results of a two-stage genetic algorithm (2SGA) 588 directly from 22].
As such incremental search methods cannot quickly access very different solutions 27 their performance is sensitive to the initial solution quality. We use DANIEL to sample 100 initial solutions per instance, which are equally applied to three rule-based methods for fair comparison. MiStar then performs parallel iterative search, retaining the best solution. Performance is measured by the average makespan and the relative gap to the best-known solution, which is obtained via OR-Tools for synthetic datasets [22] and from [59] for public benchmarks.
8

---

Table 2 Generalization results on large synthetic instances
Size
Sample
Greedy
100 lterations
200
lerratinss
400
Iverations
OR-Tivlls
DANIEL
HGNN
DANIEL
HGNN
GD
F1
B1
MiS
GD
FI
BC
MiSir
GD
FT
BI
MiSter
Obj.
256.77
308.55
258.61
314.7]
285.04
286.19
285.95 285.79
265.01
286.19
285.95
285.75
256.04
256, 19 285.95 285.68
30x10 Gap
4.41%
12.33%
5,08%
14.58%
4,14%
4.19%
4.11% 4.05%
4.14%
4.19%
4.11%
4,03%
4.14%
4.19%
4,11% 4.01% 274.67666)
SDI
Time
5.60s
6.25%
0.97%
0.975
7.67m
10.51m
10.73m 57 53.03s
15.52m
22.00m
21 4Pt
1.83m
30.65m
43.11m 3,77m
Obj.
579.31
410.76
379.28
417.57
379.04
319,05 378.92 378.82
379,04
579,05
578.92
378.76
379.04
399.05
378,92
378.63
40x10 Gap 3.76%
12.24%
3.64%
14.185
3,57%
3,589 3.54%
3.51% 3,57%
3.58%
3.54%
3.50%
3.57%
3.58%
3.56% 3.46% 365 (65.96(38)
Time
9,945
10.45
1,30s
1.34s
18.20m
25,1
24.04m 1.11m 36.48m
52.01m
46c
2,55m
1.22h
1.82h
1.63h
5.94m
Oby. 756.52
1453.40
800.02
1536.74
753.66
748.41 739.47 735.14 755.66
748.41 739.47
751.84
753.66
748.41
739,47
728.76
30x10 Cup 9.78%
109.95%
15.57%
121
8.87%
8.11% 6.82% 6.19% 8.87% 8.11% 6.82%
5.72%
8.875%
8.11%
6.825
5.27% 092.26001))
Time
5.76s
5,586
0.9%%
1.14s
7.65m 12.13m 12.16m 49.43s 15,04m0 24.58 25 400m
1.60m
29.50m
51. 51.78m 52,62m 3,56m
953.14
1937.96
084.55
2045.78
1941 60 930.44
(34 947 941 60 93044
129.13 947.64
930,44
995.03
4lx1D Gup
4.53%
94.11%
1.399
104.9195
91%
-5. 1099 -5. 69% -6.81 %o- 66755% -5 5..0% -5.09% -6.81% -6.94%
-5.08%
-5. 6999 -6.81% -7.26% 998. 39/0%)
Time
10.064
11.10s
346
18. 29m 25.07m 06m 73 73.20s 35.83m 44.54m--- 18m
2.53m
1.89h
1.42h 5.40m
The DR, Tocks silaton and rate-ot oporuity salwed tecances sn opoorad "wr- aaal 1V souomb sinaks, lown, ropoctiolyy
Table 3 Results on public benchmarks
Method
mk
la(rdata)
In(edata)
la(vdata)
Obj.
Gap
Timets)
Obj.
Gap
Timeis)
Obj.
Gap
Timets)
Obj.
Gap
Timett)
OR- Tools
174.20
0.99%
1447.08
935.80
0.16%
1397.43
1028.93
0.01%
899.60
919.60
.0.01%
639.17
2SGA
175.20
1.57%
57.60
812.20
0.39%
51.43
DANIELZS
180.00
4.81%
1.71
984.63
5.39%
1.99
1120.28
8.88%
2,00
934.75
1.4%%
2.02
HGNN(S)
192.20
11.42%
1.72
1004.60
7.53%
1.84
1123.10
9.16%
2.44
934.23
1.58%
2.12
DANIELIG)
184.30
6.84%
0.45
1044.85
11.84%
0.48
1176.40
14.34%
0.48
965.38
4,97%
0.48
HGNN(G)
200.00
15.94%
0.46
1035.75
10.86%
0.52
1189.33 33
15.59%
0.48
962.48
4.66%
0.47
GD
178.92
3.72%
22.86
963.03
3.08%
26.09
1100.46
6.96%
4.14
924.33
0.33%
89394
FI-100
178.85
3.68%
34.91
968.60
3.67%
36,16
1101.43
7.05%
6.77
927,33
0.83%
131.90
BI-100
178.43
3.44%
37.98
964.8 80
3,27%
41.25
1100.63
6.97%
5,91
927.55
0.86%
122.02
MIStar 100
177.80
(+0.74)330079
17.50
958,90
90 (+4.55)
2.64%
19.86
1099.38
(+4.17)
6.85%
19.60
923.55
(#1.81)
0.42%
20.36
GD:200
178.92
3.72%
45.73
963.03
3.08%
$1.94
1100.46
6.96%
8.27
924.53
0.53%
179.99
FI-200
178.85
3.68%
74.64
968 60
3.67%
76.17
1101.43
7.05%
14.45
927.33
0.83%
272.34
BI-200
178.43
3.44%
81.03
964.65
3,25%
86,20
1100.60
6.97%
12.70
926.55
0.75%
251.11
MISiar 200
177.70
(+0.75)
3.01%
36.45
957.
(+4.72)
2.46%
40.66
1099.30
(+4.13)
6.84%
40.05
922.70
(#1.71)
0.33%
41.83
GD-100
3.72%
91.79
963.00
3.08%
103.81
1100.46
6.96%
16.51
924.53
0.53%
360.28
FI-400
178.85
3.68%
162.16
968 60
3.67%
158.27
1101.35
7.04%
31.56
927.33
0,83%
586.32
B1-400
178.43
3.44%
169.70
964.50
3.24%
180.45
1100.33
6.94%
27.24
925.55
0.64%
$21.21
MIStar- 400
177.60
(210.63)
2,96 9%
76.35
956.38 (15.04)
2.37%
85,45
1099.18 (14.25)
6.83%
83.77
921.85
(a1.77)
0.24%
87.23
The midiequa and of 2SCAA on latvdata) bonchmark ar computad 1-30 insumocs, repurtted in S "US"" denites the sampling strategy and "K37" decones the greedy stratagy.
".000" "-200" and "-400" demoic differzea lomation bolletts
Values are oepected os the owerage (e standiedd destation) over 10 Indeperdent runs.
5.2 Performance on Synthetic Instances
We train our model with 100 iterations on four small sizes (10 x 5, 20 x 5, 15 x 10, and 20 x 10) from two synthetic datasets and evaluate corresponding test instances. Table reports the performance and average runtime per instance across all methods. The generalization capubility of the model, evaluated on large-sized instances (30 10 and 40 x 10 in Table and with extended iterations up to 400, is also reported. The results show that MIStar consistently outperforms two construction methods across various instances, with larger gains on SD2. This is because initial solutions on SD1 are near-optimal, leaving limited room for improvement, as verified by experiments on varying- quality initial solutions (see Appendix[]. Compared with rule- based improvement heuristics, M/Star achieves better solution quality with shorter runtime and maintains consistent improvement over longer iterations, verifying the effectiveness and efficiency of its policy. See detailed analysis in Appendix H
5.3 Performance on Public Benchmarks
We evaluate generalization on Hurink and Brandimarte benchmarks using the model trained on the 10 x 5 instances from SD2. While OR-Tools and 2SGA achieve near-optimal results, their computational cost limits practicality. MiStar maintains stable performance over both based construction and rule-base method across all benchmarks, demonstrating its effective generalization through the learned general policy. Regarding solving time, rule-based methods exhibit notable variation across Hurink dataset, with runtimes increasing from edata to rdata and vdata due to the growing set of assignable machines that enlarge the neighborhood. In contrast, MiStar maintains stable runtime across all distributions.
9

---

Table 4 Generalization Performance on Larger-Seale Instances
Optimality
Instance Size
Method
Objective
Time (min)
Gap
50x15
OR- Tools
881.45
60.0
39.05%
(LB:537.2)
MIStar-200 200
969.7
10.6
44.60%
60x15
OR Tools
1075.
60.0
46.94%
(LB:570.22
MIStar-200
I109.8
14.2
48.62%
100x
OR Tools
1922.65
60.0
62.22%
(LB:726.5)
MIStar- 200
2138.4
15.9
66.03%
50x30
OR Tools
Infeasible
60.0
(LB:N/A)
MIStar-200
1040.1
60.0
5.4 Results on Larger Instances
To further evaluate the generalization and scalability our framework, we conducted experiments on even larger instances (up to 1,500 operations). For each problem size, 10 instances were randomly generated, and both MIStar and OR- Tools were given a one-hour time limit per instance. We report their average optimality gap across different scales, wheih is calculated based on the Lower Bound
(LB) as 1
x 100%. For MIStar, the results were measured at 200 iterations using the model trained on instances of size 20 15.
LB
Objective
The results in Table 4 highlight two critical advantages of our approach. First and most strikingly, on the highly complex 50 x 30 instances, OR-Tools failed produce any feasible solution within the time limit, whereas MIStar consistently found high- -ualitt solutions. This demonstrates MIStar's superior robustness and scalability on truly challenging problems. Second, for the other large instances where OR-Tools did find a solution, MIStar achieves comparable solution quality in a small fraction of the time. For example, on the 100 x instances, MIStar reaches a 66.03% optimality gap in just under 16 minutes, while OR- Tools requires full hour to achieve a 62. 22% gap. This massive speed-up. combined with the strong generalization from a model trained only on smaller instances, confirms that MIStar provides an effective and highly scalable solution for large-scale FISP.
5.5 Ablation Studies
We conducted ablation experiments on the SD2 dataset to assess the memory module and parallel greedy search strategy. As evidenced in Table 7 (Appendix J their combination improves perfor- mance: the parallel greedy search strategy significantly enhances search efficiency and mitigates the risk of early convergence to local optima. Meanwhile, the memory module optimizes policy decisions, leading to higher solution quality. We further investigated the impact of the parallel scale P on our strategy. Figure (Appendix demonstrates that increasing P generally improves performance the cost of longer runtimes, with the optimal value depending on the instance characteristics. Therefore, P should be properly adjusted achieve a trade-off between runtime and solution quality.
6 Conclusion
This study proposes MIStar, the first DRI--based improvement heuristic framework for solving the FJSP. By formulating the iterative refinement as MDP, we introduce heterogeneous disjunctive graph representation tailored for FJSP solutions and employ a socmory-enhanned heterogeneous graph neural network for feature extraction and thorough exploration of the solution space. Furthermore, we propose parallel greedy search strategy that significantly reduces the number of iterations while achieving high-quality solutions. Extensive experiments on synthetic data and public benchmarks demonstrate the superior performance of MiStar over both traditional handcrafted improvement heuristics and DRL-based construction methods. Future work may focus on enabling the network to adaptively adjust the parallel scale P. and on extending our methodology to disruptive local moves in larger neighborhoods, such as the reconstruction of solution segments, to further enhance exploration and reduce sensitivity initial solutions.
10

---

Acknowledgements
This work is supported by the Jilin Provincial Department of Science and Technology Project under Grant Cran220240101361JC..
References
[1] Heiner Lasi, Peter Fettke, Hans- Georg Kemper, Thomas Feld, and Michael Hoffmann. Industry 4.0. Business & information systems engineering. 6:239-244 2014.
[2] Yi Wang, Hai-Shu Ma, Jing-Hui Yang. and Ke-Sheng Wang. Industry 4.0: a way from mass customization mass personalization production. Advances in manufacturing, 5(4):311-320, 2017.
[3] Runwei Cheng, Mitsuo Gen, and Yasuhiro Tsujimura. A tutorial survey of job-shop scheduling problems using genetic algorithms-1 i. representation. Computers & industrial engineering, 30(4):983 997, 1996.
[4] Jian Zhang, Guofu Ding, Yisheng Zou, Shengfeng Qin, and Jianlin Fu. Review of job shop scheduling research and its new perspectives under industry 4.0. Journal of intelligent manufac- turing, 30: 1809-1830, 2019.
[5] Jin Xie, Liang Gao. Kunkun Peng, Xinyu Li, and Haoran Li. Review flexible job shop scheduling. IET collaborative intelligent manafacturing, 1(3):67-77, 2019.
[6] Imran Ali Chaudhry and Abid Ali Khan. research survey: review flexible job shop scheduling techniques. International Transactions in Operational Research, 23(3):551-591, 2016.
[7] Guohui Zhang, Xinyu Shao, Peigen Li, and Liang Gao. An effective hybrid particle swarm optimization algorithm for objeit-beecttvve flexible job-shop scheduling problem. Computers & Industrial Engineering, 56(4): 1309)-319911 2009.
(8) Wen Song, Xinyang Chen, Qiqiang Li, and Zhiguang Cao. Flexible job-shop scheduling via graph neural network and deep reinforcement learning. IEEE Transactions on Industrial Informatics, 19(2):1600-1611) 2022.
[9] Pedro Coelho, Ana Pinto, Samuel Moniz, and Cristovão Silva. Thirty years of flexible job-shop scheduling: a bibliometric study. Procedia Computer Science, 180:787-796, 2021.
[10] Philipp Wenzelburger and Frank Allgöwer. Model predictive control for flexible job shop scheduling in industry 4.0. Applied Sciences, 11(17):8145, 2021.
[11] Stéphane Dauzère-Péne Pérès, Junwen Ding, Liji Shen, and Karim Tamssaouet. The flexible job shop scheduling problem: A review. European Journal of Operational Research, 314(():409-433 2024.
[12] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d' d'horizon. European Journal of Operational Research, 290(2):405 2021.
[13] Mingzhao Wang. You Zhou, Zhiguang Cao, Yubin Xiao, Xuan Wu, Wei Pang, Yuan Jiang, Hui Yang, Peng Zhao, and Yuanshu Li. An efficient diffusion diffusion-based non-autoregressive solver for traveling salesman problem. In Proceedings of the 31st ACM SIGKDD Conference Knowledge Discovery and Data Mining V.I. page 1469-1480, 2025.
[14] Yubin Xiao, Di Wang, Boyang Li, Mingzhao Wang, Xuan Wu, Changliang Zhou, and You Zhou. Distilling autoregressive models to obtain nigh-performance non-autoregressive solvers for vehicle routing problems with faster inference speed. Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 20274-20283, 2024.

---

[15] Yubin Xiao, Di Wang, Boyang Li, Huanhuan Chen, Wei Pang, Xuan Wu, Hao Li, Dong Xu, Yanchun Liang, and You Zhou. Reinforcement learning- based nonautoregressive solver for traveling salesman problems. IEEE Transactions on Neural Networks and Learning Systems, pages 1-15, 2024.
[16] Yubin Xiao, Di Wang, Xuan Wu, Yuesong Wu, Boyang Li, Wei Du, Liupu Wang, and You Zhou. Improving generalization of neural vehicle routing problem solvers through the lens of model architecture. Neural Networks, 187: 2025.
[17] Yubin Xiao, Yuesong Wu, Rui Cao, Di Wang. Zhiguang Cao, Peng Zhao, and Yuan Jiang, Dgl: Dynamic global-local information aggregation for scalable vrp generalization with self- improvement learning. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2025.
[18] Xuan Wu, Di Wang. Chunguo Wu, Lijie Wen, Chunyan Miao, Yubin Xiao, and You Zhou. Efficient heuristics generation for solving combinatorial optimization problems using large lan- guage models. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 2, pages 3228-32222 3239,, 2025.
[19] Xuan Wu, Di Wang, Lijie Wen, Yubin Xiao, Chunguo Wu, Yuesong Wu, Chaoyu Yu, Douglas Maskell, and You Zhou. Neural combinatorial optimization algorithms for solving vehicle routing problems: comprehensive survey with perspectives, 2024.
[20] Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey, Computers & Operations Research, 134: 105400, 2021.
[21] Cong Zhang, Zhiguang Cao, Wen Song, Yaoxin Wu, and Jie Zhang. Deep reinforcement learning guided improvement heuristic for job shop scheduling. In The Twelfth International Conference on Learning Representations, 2024.
[22] Runqing Wang, Gang Wang, Jian Sun, Fang Deng. and Jie Chen. Flexible job shop scheduling via dual attention neework-based reinforcement learning. IEEE Transactions on Neural Networks and Learning Systems, 35(3):3091-3122 2023.
[23] Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Xu Chi Learning to dispatch for job shop scheduling via deep reinforcement learning. Advances in neural information processing systems, 33:1621-1632, 2020.
[24] Kun Lei, Peng Guo, Wenchao Zhao, Yi Wang, Linmao Qian, Xiangyin Meng, and Liansheng Tang. A multi-action deep reinforcement learning framework for flexible job-shop scheduling problem. Expert Systems with Applications, 117796, 2022.
[25] Ruiqi Chen, Wenxin Li, and Hongbing Yang. A deep reinforcement learning framework based on an attention mechanism and disjunctive graph embedding for the job-shop scheduling problem. IEEE Transactions on Industrial Informatics, (122):322-13333 2022.
[26] Junyoung Park, Jachyeong Chun, Sang Hun Kim, Youngkook Kim, and Jinkyoo Park. Learning schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning. International journal of production research, 59(11):330--377, 2021.
[27] Nathan Grinsztajn, Daniel Blanno, Shikha Surana, Clément Bonnet, and Tom Barrett. Winner takes it all: Training performant rl populations for combinatorial optimization. Advances in Neural Information Processing Systems, 36:48485-48509, 2023.
(28) Egon Balas. Machine sequencing via disjunctive graphs: an implicit enumeration algorithm. Operations research, 17(6):941-99) 1-977, 1969.
[29] Cong Zhang, Zhiguang Cao, Yaoxin Wu, Wen Song, and Jing Sun. Learning topological representations with bidirectional graph attention network for solving job shop scheduling problem. In Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, 2024.
12

---

[30] Ke Li, Fei Liu, Zhenkun Wang, and Qingfu Zhang. Destroy and repair using hyper-graphe for routing. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages
18341-18349, 2025.
[31] Peng Zhao, You Zhou, Di Wang, Zhiguang Cao, Yubin Xiao, Xuan Wu, Yuanshu Li, Hongjia Liu, Wei Du, Yuan Jiang, and Liupu Wang. Dual operation aggregation graph neural networks for solving flexible job-shop scheduling problem with reinforcement learning. In Proceedings of the ACM Web Conference 2025, 2025.
[32] Peng Zhao, Zhiguang Cao, Di Wang, Wen Song, Wei Pang, You Zhou, and Yuan Jiang. Visual- enhanced multimodal framework for flexible job shop scheduling problem. In Proceedings of the 33rd ACM International Conference on Multimedia, 2025.
[33] Shu Luo. Dynamic scheduling for flexible job shop with new job insertions by deep reinforce- ment learning, Applied Soft Computing, 91:106208, 2020.
[34] Yi Feng. Lu Zhang, Zhile Yang, Yuanjun Guo, and Dongsheng Yang. Flexible job shop scheduling based on deep reinforcement learning. In 2021 5th Asian Conference on Artificial Intelligence Technology (ACAIT), pages 660-666. IEEE, 2021.
[35] Shu Luo, Linxuan Zhang, and Yushun Fan. Dynamic multi-objectivve scheduling for flexible job shop by deep reinforcement learning. Computers & Industrial Engineering, 1599:07489, 2021.
[36] Renke Liu, Rajesh Piplani, and Carlos Toro. Deep reinforcement learning for dynamic schedul- ing of a flexible job shop. International Journal of Production Reseurch, 60( (0(13))404944069) 2022.
[37] Lanjun Wan, Long Fu, Changyun Li, and Kegin Li. Flexible job shop scheduling via deep reinforcement learning with meta-path patt--pptt-beeedd based heterogeneous graph neural network. Knowledge- Based Systems, 296:1 1 1940, 2024.
[38] Zhengqi Zeng, Xiaoxia Li, and Changbo Bai. A deep reinforcement learning approach to flexible job shop scheduling. In 2022 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pages 884-890. IEEE, 2022.
[39] Wenquan Zhang, Fei Zhao, Yong Li, Chao Du, Xiaobing Feng, and Xuesong Mei. A novel collaborative agent reinforcement learning framework based on an attention mechanism and disjunctive graph embedding for flexible job shop scheduling problem. Journal of Manufacturing Systems, 74:329 345, 2024.
[40] Jonas K Falkner, Daniela Thyssens, Ahmad Bdeir, and Lars Schmidt-Thieme. Learning to control local search for combinatorial optimization. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 361-376. Springer, 2022.
[41] Constantin Waubert de Puiseau, Fabian Wolz, Merlin Montag, Jannik Peters, Hasan Tercan, and Tobias Meisen. Decision transformer for enhancing neural local search on the job shop scheduling problem. arXiv e-prints, pages arXiv-2409, 2024.
[42] Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. Advances in neural information processing systems, 32, 2019.
[43] Hao Lu, Xingwen Zhang, and Shuang Yang. A learning-based iterative method for solving vehicle routing problems. In International conference on learning representations, 2019.
[44] Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving routing problems. IEEE transactions on neural networks and learning systems, 33(9):5057-5069, 2021.
[45] Chao Yong Zhang, PeiGen Li, ZaiLin Guan, and YunQing Rao. A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem. Computers & Operations Research,
2007.
[46] Eugeniusz Nowicki and Czeslaw Smutnicki. A fast taboo search algorithm for the job shop problem. Management science, 72(6):777-813, 1996.
13

---

[47] Andoni I Garmendia, Quentin Cappart, Josu Ceberio, and Alexander Mendiburu. Marco: A memory-augmented reinforcement framework for combinatorial optimization. arXiv preprint arXiv:2408. 2024.
[48] Andoni I Garmendia, Josu Ceberio, and Alexander Mendiburu. Neural improvement heuristics for graph combinatorial optimization problems. IEEE Transactions on Neural Networks and Learning Systems, 2023.
[49]
Zhi-Hur Zhou. Ensemble methods: foundations and algorithms. CRC press, 2025.
[50] Igor G Smit, Jianan Zhou, Robbert Reijnen, Yaoxin Wu, Jian Chen, Cong Zhang, Zaharah Bukhsh, Yingqian Zhang, and Wim Nuijten. Graph neural networks for job shop scheduling problems: survey. Computers & Operations Research, page 106914, 2024.
[51] Monaldo Mastrolilli and Luca Maria Gambardella. Effective neighhourhood functions for the flexible job shop problem. Journal of scheduling, 3(1):3-20, 2000.
[52] Alain Bretto. Hypergraph theory. An introduction. Mathematical Engineering. Cham: Springer, 1:209-216 216, 2013.
[53] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprini arXiv: 081000080000.... 2018.
[54] Johann Hurink, Bernd Jurisch, and Monika Thole. Tabu search for the job-shop scheduling problem with multi-purpose machines. pperations-Researrcd-Seeeee 15:205-215, 1994.
[55] Paolo Brandimarte. Routing and scheduling in flexible job shop by tabu search. Annals of Operations research, 41(3):157-183, 1993.
[56) Pierre Hansen and Nenad Mladenović. First vs. best improvement: An empirical study, Discrete Applied Mathematics, (14
[57] Helena Ramalhinho Lourenço, Olivier C Martin, and Thomas Stützle. Iterated local search: Framework and applications. In Handbook of metaheuristics, pages 129-168. Springer, 2018.
[58] Danial Rooyani and Fantahun M Defersha. An efficient two-stage genetic algorithm for flexible job-shop scheduling. Ifae-Papersonnliee 52(13):2519-22 2019.
[59] Dennis Behnke and Martin Josef Geiger. Test instances for the flexible job shop scheduling problem with work centers. 2012.
[60] Anssi Kanervisto, Christian Scheller, and Ville Hautamäki. Action space shaping in deep reinforcement learning. In 2020 IEEE conference on games (CoG), pages 479-486. IEEE, 2020.
[61] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint vrXiv:1707.06347 2017.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Please see abstract and Section I, which accurately reflect the paper's contribu- tions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of this work are discussed in Section 5.1 and Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

Justification:
The full set of assumptions and complete proofs are provided in Appendix D.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We explained our settings in Section 5.1 and hyperparameters in Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
16

---

Answer: [No]
Justification: Our experiments use only open-source datasets, while the code required to reproduce these findings does not shared at this time.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https
ssicnpolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The training and test details are presented in Section and Appendix F. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: The experiments are expensive to run for sufficient number of times to provide error bars at this point.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
17

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The information on the computer resources is reported in Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpp:///aaurppp..ccpppolaaaaaaa
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The potential societal impacts of this work are discussed in Section and
Section 2.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We did not existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper dose not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper dose not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
20

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs were used for minor language editing, which does not affect the scientific contribution of the paper.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
21

---

A Comparative Analysis of Neighborhood Structures
The critical path, whose length represents the makespan Cmax. is essential in constructing feasible solutions [55]. Operations on this path critical operations, and critical blocks maximal sequences of adjacent critical operations processed on the same machine [45]. In local search, the neighborhood comprises feasible solutions generated by small perturbations the current one (55]. For scheduling, these perturbations typically involve reordering operations on the critical path. The neighborhood structure directly affects the efficiency of the search algorithm, making it important to eliminate unnecessary or infeasible moves [45]. Among various neighborhood designs, the N5 neighborhood is significantly smaller than others 455 It identifies a single critical path and defines move by reversing either the first two or the last two operations within a critical block.
While effective for JSP 21I,, the N5 neighborhood cannot be applied to FISP. Its limitation lies in only permitting reordering within one critical block, where operations are processed on the same machine. This perturbation preserves the original machine assignments, severely constraining the exploration of the solution space. More critically, unlike JSP where operations of the same job processed different machines, FISP allows multiple operations of job to be processed the same one. Consequently, swapping operations within critical blocks in FISP may violate job precedence constraints, resulting in infeasible solutions (Figure [
In contrast, we employ the Nopt2 neighborhood [5]] that simultancously modifies operation sequences and machine assignments while maintaining feasibility through time-constrained reinsertion (see paragraph 3) This structure enables broader solution space exploration and improves efficiency by using optimal insertion intervals to reduce the neighborhood size.
M2
M2
M3
critical blocks
O11
112
O₂
22
0
Or
O31
O32
O33
04
infeasible exchange
Figure Infeasible exchange caused by the NS neighborhood in FJSP. Dotted lines of different colors are critical blocks.
B Definition of Raw Feature Vectors
The raw features of operations and machines at each state 8 (omitting step /) are defined as follows. Features of Operations: Each operation node Oij O (Os, Or) is represented by 9-dimensional feature vector Xo.;
1) Minimum Processing Time: shortest processing time among compatible machines.
2) Average Processing Time: mean processing time among compatible machines.
3) Range of Processing Time: difference between the maximum and minimum processing times among compatible machines.
4) Machine Availability Ratio: ratio of the number of compatible machines to total machines.
5) Processing Time: processing time on the assigned machine.
6) Earliest Start Time: earliest possible start time of the operation.
7) Latest Start Time: latest start time without schedule delay.
8) Scheduling Order on Machine: execution order on machine Mr (starting from 1).
9) Processing Time of Job: total processing time of parent job.
Features of Machines: Each machine node M₁ M owns 4-dimensional feature vector M.
1) Utilization Rate: ratio of active processing time to makespan.
22

---

2) Criticality Degree: proportion of operations on critical path among processable operations.
3) Load Ratio: percentage of assigned operations versus machine capacity.
4) Processing Efficiency: mean processing time of assigned operations.
C Advantages of the Directed Heterogeneous Graph
In the FJSP, the global scheduling state comprises both operations and machines. However, the absence of machine nodes in traditional disjunctive graphs results in an indirect representation of machine information through numerical values [21]. which limits the policy from assigning operations to available machines effectively. The heterogeneous disjunctive graph H { addresses this by introducing machine nodes (Fig. G where each operation connects to compatible machines via undirected edges, such that solving the FISP equivalent to selecting one O-M are per operation
while removing others. This reduces the graph density from E
Σ [M] k= ny with being the number of operations assignable to machine M₁ and enables better injection of machine status X
(m to
While beneficial for construction methods, this structure provides limited advantages for improvement approaches where complete solutions contain fixed machine assignments. This leads to total of |O] disjunctive arcs-moon than the |O| |M] arcs in the conventional graph, negating the benefit of reduced graph density. Most importantly, undirected edges hinder the clear encoding of machine processing sequences, which is crucial for distinguishing between different scheduling solutions and identifying the critical path when constructing the action space 21 [T]. Instead, our heterogeneous
graph 7 (Figure Ic). tailored for complete schedules, overcomes this limitation by encoding machine processing sequences through directed hyper-edges, which effectively represent the ordering of operations across different solutions without significantly increasing graph density. It adopts a unified structure with fully directed arrows, avoiding the complexity of mixed edge types and better aligning with current learning- search graph- basph frameworks (21
M,
M
M2
M
(a)
(b)
Figure 6 Graph representations in [8] (a) FJSP instance; (b) feasible solution.
D Compact State Representation in Memory
D.1
Motivation and Compact Formulation
During the improvement, store the state-action pair (st, az) at each step in memory module. However, the state is represented as a complex heterogeneous graph with rich node attributes and adjacency relations, leading to excessive memory consumption if fully stored. Furthermore, evaluating similarity between such graphs typically requires GNNs to extract embeddings, introducing additional network components and computational cost.
To address this, we simplify the graph representation to better support our memory mechanism. First, since our current goal is to distinguish different scheduling solutions-ratie than using node features as heuristic guidance-we omit the node attributes and retain only the graph topology. Second, for given problem instance, solutions differ only operation sequences machines (i.c., hyper-arcs), while sharing the same job precedence constraints (i.c., conjunctive arcs). Based on this insight,
we isolate the hyper-arcs from H. (see Fig- 7 and use them the key feature to characterize each solution. Specifically, we use the operation- machine incidence matrix L, as compact representation of s, and measure similarity via the Frobenius inner product.
23

---

0.3
(a)
(b)
Figure Decomposition of FJSP solution structure. (a) shared job precedence constraints; (b)
distinct machine processing sequences.
Instead of serving as merely binary indicators machine assignment, the non-zero element (Le) represents the processing order index of operation i on its assigned machine j. This crucial design ensures that two schedules with identical machine assignments but different sequences (c.g., good sequence vs. poor one) are correctly distinguished. For instance, good sequence of operations corresponding to [1, 2, 3, 4, 5] and a poor, reversed sequence [5, 4, 3, 2. I] on the same machine maximally dissimilar by the Frobenius inner product. The mathematical
will be recognized foundation for this lies in the Rearrangement Inequality, which guarantees that the inner product is maximized for similarly ordered sequences and minimized for oppositely ordered ones. This allows our similarity metric to be both computationally efficient and highly sensitive to the quality of the operation sequence.
Theorem 1. The Rearrangement Inequality states that, for two sequences S S. ... S an and b2 S ... S bn, the inequalities
a1bn, + 02 an S a1bx(1) + azbm(2) .... ands(n) I aih, + azb2 + ... + an
hold, where x (2), (2)...., (n) is any permutation of 1, ,.....
D.2 Alternative Designs
We have considered and tested other expressive representations for the historical states that explicitly encode sequence information.
The adjacency matrix A,M of operations on machines encodes the processing order between operations, while the binary operation machine incidence matrix L, indicates machine assignment. The state similarity is then calculated by computing the inner products of both matrices separately and summing the results, expressed as:
Multi matrices:
Wh, (L L + (AM A
Difference matrix: For the operation machhne incidence matrices that store processing order indices, compute the element-wise difference between two schedules, Le and Lv, to obtain difference matrix, and then use the reciprocal of its Frobenius norm to measure similarity, formulated as:
Wh.t
L. L
V M (L.)., (Lc)
However, these alternatives introduced higher storage computational overhead without yielding significant performance gains. Our chosen representation thus strikes deliberate and effective balance between representational power and efficiency.
E Complexity Analysis of Action Space
Let Fo O and FM E M denote the embedding matrices of operation and machine nodes, respectively. To assign a priority score to each possible triple-action [Om, On, M&), we compute the priority matrix FOOM RoOOx x|M] through a two-step tensor operations involving Fo and FM. As result, the space complexity of the action space Aoriginal is (( Prior

---

work [60] has shown that a large number of possible actions is known to lead to over-optimistic estimates of futurr rewards, degrading agent performance and learning efficiency. To address this, we reshape the action space by exploiting the constraint of FJSP: each operation can only be assigned to a unique machine. Given a solution of FJSP, there exists a mapping sas O + MM, which allows us to omit the third dimension and represent actions pairs [Om, On] The space complexity of Aoptimised reduced to O(() and the optimized priority matrix is calculated as follows:
Foo FoFo I [
(10)
We can formalize the relationship between the original and optimized action spaces as follows: Theorem 2. The optimized action space Aoptimized functionally equivalent to Aoriginal in terms of admissible actions under the FJSP constraints.
10m; On, M&] Aoriginal, there exists unique a' [Om, On] E Aoptimized with Mr- = fas (O,). Conversely, any a' E Aoptimized can be mapped back E Aoriginal via fM- Thus, this compaction preserves all feasible actions while eliminating invalid ones (i.e., actions where the operation and machine do not match). This shaping of the action space reduces learning difficulty and accelerates model convergence without compromising the agent's performance.
Proof. For any feasible action
Algorithm 1: Training procedure with n-step PPO using parallel search.
Input: MIStar with trainable parameters è {6, 8, sp,, parallel scale P. iteration limit T, update size n, validate size v, new data generation step d, batch size B, total number of training epochs 1;
Output: Trained MIStar with parameters O = {8" 00 ,
for i 0 do
if mod d 0 then
Randomly generate B instances; end
Compute initial solutions .sh....,,s s6) using DANIEL; for T do for s E {s/, (s),...,s," s.y do
Initialize training data buffer D and memory buffer HD with size 0: Extract embeddings using MHGNN; for p= to P do
10
Sample local move 0, bp TT(-1s?); Compute (max(( (41) w.r.t o.::
12
13
end
14
Identify the best action at" with greatest improvement:
Update oe w.r.t at and compute similarity score Ω from Hb;
15
16
Compute reward re(s), af+t) Taain Peenatty's
17
Store the data (sf: .rr"r)) into D and store (s). alt)) into H¹: if mod n = then
.r,)
18
Compute the generalised advantage estimates As; Compute the PPO loss L, and optimize the parameters θ for R epochs; Update network parameters;
19
21
22
end
Clear buffers D and Hh: end 24
23
end
26
if mod v = 0 then
27
Validate the policy;
28
end
29
i B;
end
25

---

F The n-step PPO Algorithm with Parallel Greedy Exploration Strategy
We adopt the PPO algorithm [61] based on the actor-critic architecture as our training strategy. The actor is the policy network and the critic provides state value estimation. The network parameters updated every n steps, which effectively addresses sparse rewards and out-of-memory issues [21]. The flexibility of FJSP leads to large solution space, requiring numerous iterations converge to high-quality solutions [3).. To address this challenge, we introduce a parallel greedy exploration strategy, which evaluates multiple candidate actions in parallel and greedily selects the one yielding the greatest improvement. This approach enables the exploration of multiple solutions per iteration, yielding high-quality results with fewer iterations. Moreover, by prioritizing solutions with the greatest improvement, the model is guided toward more promising paths, minimizing the interference from inefficient paths during gradient updates and accelerating convergence.
The pseudo-code of the n-step PPO algorithm presented in Algorithm !
G Training Configurations
All hyperparameters were fine-tuned on the smallest-scale instances from SD2 and kept the same for all other models. Experiments were conducted on a platform equipped with Intel 19- 19-12900K processor with 24 cores, 64 GB memory, and an NVIDIA RTX 4090 GPU with 24 GB VRAM. Detailed specifications are provided in Table Upon acceptance of this manuscript for publication. the full code will be made available on GitHub.
Table 5 Training configuration parameters
Parameter
Value
Number of MHGNN layers (L)
Number of Actor network layers
4
Number of Critic network layers
3
Number of attention heads in GAT (nu)
Dimension of hidden layers (g)
64
GIN learnable parameter (c)
0
Discount factor (7)
Clipping ratio
0.2
Policy function coefficient
1
Value function coefficient
0.5
Entropy coefficient
0.01
Learning rate
5 x 10-4
Optimizer
Adam
Memory buffer size
600
KNN retrieval count (K)
15
Similarity penalty coefficient (A)
10
PPO update interval (n)
10
Rounds per PPO update (R)
3
Total training epochs (T)
20,000
Validation interval (v)
5
Instance generation interval (d)
20
Iterations per instance (T)
100
Batch size (B)
20
Parallel scale (P)
50
H Detailed Analysis on Synthetic Instances
Our experiments on four small-sized instances from SD2 reveal that MIStar generates action space consisting of dozens hundreds possible moves per iteration using the Nopt2 neighborhood to 100 times larger than 21 for solving JSP. While this expanded action space provides greater
26

---

Table 6 Results of different initialization methods
SD2
Method
10xc5
20x5
15x10
20x10
Iter.
Obj.
Gap
Obj.
Gap
Obj-
Gap
Obj.
Gap
0
365.26
0.00%
629.56
0.00%
522.51
0.00%
552.38
0.00%
100
345.05
5.53%
615.12
2.29%
488.22 22
6.56%
530.93
3.88%
DANIEL(S)
200
343.43
5.98%
613.75
2.51%
476.93
8.72%
528.92
4.25%
400
342.50
6.23%
612.73
2.67%
465.71
10.87%
525,49
4.87%
0
479.35
0.00%
963.03
0.00%
759.54
0.00%
984.64
0.00%
HGNN(S)
100
375.20
21.73%
745.18
22.62%
677.96
10.74%
879.45
10.68%
200
366.35
23.57%
702.90
27.01%
626.90
17.46%
812.53
17.48%
400
355.100
25.09%
674.93
29. .2%
569.81
24.98%
737.42
25.
0
503.86
0.00%
799.56
0.00%
670.56
0.00%
775.03
0.00%
20.76%
692.43
13.40%
578.48
13.73%
695.34
10.28%
SPT
200
393,74
21.86%
680.62
14.88%
550.94
17.84%
673.44
13.11%
400
389.34
22.73%
671.05
16.07%
521.96
22.16%
648.48
16.33%
0
493,36
0.00%
949.85
0.00%
737.44
0.00%
953.11
0.00%
100
382.09
22.55%
747.12
21.34%
664.69
9.87%
858.45
9.93%
MWKR
200
372.62
24.47%
705.15
25.76%
618.86
16.08%
799.61
16.11%
400
364.99
26.02%
676.88
28.74%
563.56
23,58%
729.91
23.42%
0
476.96
0.00%
931.50
0.00%
763.12
0.00%
978.03
0.00%
100
376.29
21.11%
729.85
21.65%
669.51
12.27%
861.06
11.96%
HIFO
200
367.70
22.91%
693.35
25.57%
618.74
18.92%
799.15
18. 18.29%
400
360.68
24.38%
668.26
28.26%
562.59
26.28%
728.91
25 47%
0
585.08
0.00%
1067.38
0.00%
1062.39
0.00%
1304.70
0.00%
100
382.24
34.67%
750.69
29.67%
733.17
30.99%
960.68
26.37%
RANDOM
200
371.38
36.52%
707.33
33.73%
661.03
37.78%
865.85
33.64%
400
365.33
37.56%
678.00
36.48% %
589.53
44.51 %
772.15
40.82%
optimization potential, it also introduces more suboptimal solutions, increasing the risk of local optima entrapment. Moreover, even for small-sized problems, OR-Tools could only optimally solve a small portion of instances within the time limit [22). These observations underscore the complexity of the FISP. Compared with rule- blsed improvement heuristics, MIStar shows superior performance under the same iteration budget, with only marginal shortfall (0.06%) against the BI rule the SD2 40 x 10 instance at 100 iterations. Notably, even equipped with restart, rule-based methods still tend to stagnate iterations increase-likely due the large and complex solution space-wherent MIStar continues to improve, demonstrating the effectiveness of the learned policy. Additionally, MIStar reduces runtime by directly outputting local moves, avoiding exhaustive evaluations across the entire neighborhood.
I Improvement over Varied Initial Solution Generation Methods
We systematically evaluate the optimization capabilities of MIStar using six initialization strate- gies: two DRL-based construction methods with sampling (DANIEL(S) and HGNN(S)), random initialization, and three classical priority dispatching rules-shorted processing time (SPT), most work remaining (MWKR), and first-in-fist-ouut (FIFO) (55). Experiments conducted the SD2 dataset with models trained on instances of the same size, to assess the performance across different initialization methods under the fixed iteration budget. Improvement is measured by the makespan
gap, calculated as (1 Cie
x 100%, where Co is the makespan of the initial solution and Obest is
Co
the incumbent optimal value.
The results are detailed in Table 6 It can be observed that the quality of initial solutions impacts the search efficiency of MIStar. With the same number of iterations, better initial solutions enable MIStar to generate higher-qualle improvements. Notably, after 400 iterations, solutions initialized by HGNN(S). MWKR, and FIFO outperform those generated by DANIEL(S) with 0 iteration on the 10 x 5 instances. This demonstrates that, with sufficient iteration budget, MIStar has the potential elevate weaker initial solutions to a performance level comparable to that of stronger ones. Moreover, even when starting from (near)-optimal solutions initialized by DANIEL(S), MIStar still achieves notable improvements, further validating the effectiveness of our framework.
schedules, while poorer ones typically allow for larger relative
27

---

Table 7 Performance of ablated models
SD2
Model
10x3
20x3
15x10
20x10
Tier.
Obj
Time!
Obj.
Time
Obj.
Time
Obj.
Time
364.27
0.76s
629,09
1.16s
519.34
1.82s
552.46
2.37s
Baseline
200
364.27
1.48s
629,09
2.44s
519.34
3.69s
552.46
4.78s
400
364.27
2.89s
629.09
4.85s
519.34
7.25s
552.46
9.48s
100
348.31
4.97s
616.71
10.72s
491.78
18.12s
548.61
24.80s
w/o GIN
200
347.06
10.78s
614.98
22.88s
484,36
37.58s
545.97
53.68s
400
345.73
20.56s
613.98
45.90s
477.80
1.45m
544.31
1.91m
100
350.86
5.82s
618.67
11.34s
492.76
17.85s
548.0
22.63s
w/o GAT
200
349.89
9.46s
617.33
22.91s
486.74
36.97s
547.97
51,02s
400
348.33
21.41s
615,99
46.79s
480.66
1.29m
547.87
1.78m
100
350.49
5.44s
618.15
11.39s
491.97
17.95s
535.78
23.89s
w/o HGAT
200
349.08
9.74s
616.56
23.01s
483.46
37.01s
532.83
52.47s
400
347.17
20.10s
614.97
46,38s
473.83
1.29m
529.92
1.67m
10O
363.02
0.59%
627.20
0.98s
518.28
1.68s
551.39
2.41s
w/o Par.
200
363.02
1.22s
627.20
2.13s
518.28
4.02s
551.39
6.18s
400
363.02
2.59s
627.20
5,05s
518.28
11.72s
551.39
17.57s
100
346.11
5,47s
615,99
13,98s
490.63
17.25s
534.31
25,47s
w/o Mem.
200
344.76
11.04s
615.32
25.33s
486.16
35.85s
531.71
51.08s
400
343.53
20.24s
614,80
48.91s
482.16
73.14s
528.44
1.69m
100
345.05
5.27s
615.12
11.55s
488.22
18.09s
530,93
25.76s
Ours
200
343.43
10.33s
613.75
23.50s
476.93
37.42s
528.92
53.25s
400
342.50
21.39s
612.73
47.93s
465.71
1.31m
525,49
1.88m
"s" and "m" denote seconds and minutes, respectively.
Results on Ablation Studies
J.1 Analysis on Components and Strategy
We conducted comprehensive ablation studies to evaluate the contributions of the key components of our framework, including both the model architecture and the search strategy. The experiments were performed on four small-size instances from the SD2 dataset.
We first assessed the roles of the memory module and the parallel greedy search strategy. Three ablated variants are compared: the Baseline model without any enhancements, a version without the parallel greedy search strategy (w/v Par.), and another without the memory module (w/o Mem.). Results in Table 7 demonstrate the critical roles of both components. Although our parallel approach takes longer per ieeration, it achieves superior solutions in fewer steps, improving search efficiency. In contrast, the model without parallelism runs faster but consistently converges to inferior local optima. Furthermore, while the memory module helps enhance the decision-makiin of the policy, alone (i.e., w/o Par:) proves insufficient to escape local optima. This limitation may stem from the fact that the FJSP solution space is extremely large and complex, making it challenging for the policy network to achieve effective global exploration through sparse, single-step sampling. For future work, a critical direction involves dynamically constraining the search space or optimizing the memory mechanism to selectively extract salient historical features.
Our tailored representation module, which is composed of multiple specialized graph encoders, is not only theoretically motivated by the structural characteristics of FISP graphs but is also aligned with mainstream graph learning practices [8 21 50). The ablation results by removing each component (i.c., w/o GAT, w/o GIN and w/o HGAT) confirm that each of them is essential for learning informative and discriminative state representations that support effective policy learning.
J.2 Evaluation of Search Scale
Using models trained with P = 50, we systematically evaluated the search strategy across different parallel scales P E {10, 20,30 30, 40, 50, 60, 70} on SD2 instances of two sizes. The result curves are illustrated in Figure 8 It is evident that increasing P leads to longer runtimes under a fixed number of iterations. Moreover, the runtime scales linearly with the iteration count across different P values. Regarding solution quality, the 10x5 instance has a relatively small neighborhood (approximately 80 solutions), making P 20 sufficient to cover most promising moves. Consequently, further increasing P does not yield noticeable improvement. On the other hand, the 15x 10 instance has
28

---

around 240 neighbors, so increasing P from 10 to 60 continuously improves performance. However, the difference between 60 and which additional evaluations offer little benefit. These observations highlight the importance of selecting an appropriate P based on the problem size and the flexibility of alternative machines to balance performance gains and computational cost. In future work, we plan to enable the network to dynamically adapt P according to instance characteristics, reducing manual tuning efforts.
becomes negligible, indicating saturation point beyond
365
P-20
P=20
P-40
Mean makespan
P-40
P-60
255
P-60
35
350
345
Iteration
Iteration
(a) 10 x instances.
100
520
P-20
P-20
P-30
510
P-40
Mean ma Trakespan
P-40
60
P=50
200
P=50
P-70
400
P-
Time
100
200
300
400
100
200
300
400
(b) 15 10 instances.
Figure 8 Runtime (left) and performance (right) curves across different parallel scale.
29


Reviews:
[{"review_id": "j2q51vZgm8", "reviewer": "Reviewer_19Ys", "summary": "This paper introduces MIStar, a Memory-enhanced Improvement Search framework designed to tackle the Flexible Job Shop Scheduling Problem (FJSP). Traditional deep reinforcement learning approaches often fall short of optimal solutions for FJSP, while improvement-based methods, though effective, face challenges with state representation and efficient search strategies due to flexible machine allocation. MIStar addresses these issues by employing a novel heterogeneous disjunctive graph for accurate solution representation, a memory-enhanced heterogeneous graph neural network (MHGNN) for improved decision-making through historical data, and a parallel greedy search strategy for efficient exploration.", "questions": "1. What is the run time of OR-Tools in Table 1?\n2. How do you plan to incorporate additional constraints (e.g., machine breakdowns) into your model?\n3. What is the actual training time for MIStar? Do you need to retrain the model for different benchmarks? How well can the model transfer knowledge from one benchmark to another?\n4. Given that MIStar also requires an initial solution, how does the quality of this initial solution affect MIStar's overall performance? Do you have any additional experimental results to illustrate this impact?\n5. Do you have scalability results for larger benchmarks where even OR-Tools might struggle to generate good solutions within a reasonable timeframe?", "limitations": "See above.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "- Strength\n  - A DRL-based improvement heuristic framework specifically designed for the FJSP problem.\n- Weakness\n  - The benchmarking examples seem pretty small (40x10). It is challenging to ascertain the model's true scalability given that even conventional optimization tools like OR-Tools can achieve optimal solutions in such settings. For a more comprehensive evaluation, the authors should consider larger, practical scheduling problems often found in domains like systems and networking, which involve datasets with thousands or millions of nodes.\n  - Real-world FJSP often involves multiple objectives (e.g., minimizing total flow time, machine idle time) and additional constraints (e.g., machine breakdowns, dynamic job arrivals). The current MDP formulation, reward function design (which explicitly focuses on makespan improvement and visit penalties), and the Nopt2 neighborhood structure are tailored to makespan minimization. The adaptability of MIStar to these more complex and constrained scenarios is not explored.\n  - The paper does not delve into the impact of different initial solution generation methods on MIStar's performance or how robust the framework is to poor initial solutions.", "was_revised": true, "final_justification": "The authors have addressed most of my concerns, so I would like to raise my score.", "rebuttal": "We appreciate the reviewers' feedback and address each comment below:\n## Regarding performance, benchmark size, and scalability\nWe thank the reviewer for these important questions. Our choice of benchmarks, including instances up to 40x10, was intended to align with standard yet challenging problems in the FJSP literature[2][3].We respectfully note that due to the problem's NP-hard nature, these instances are far from trivial.\n\nTo the reviewer's point about OR-Tools, its runtime was limited to 30 minutes for experiments in Table 1. The results already show that OR-Tools' ability to find and prove optimality degrades significantly as instance size increases; Due to the complexity of FJSP, even on small-to-medium instances (10×5, 20×5, 15×10, 20×10), OR-Tools fails to find optimal solutions within a reasonable time for most cases. For example, the *optimality rate* on 20×5, 30×10, and 40×10 instances is 0%. This indicates these are precisely the sizes where powerful learned heuristics become critical.\n\nTo more directly address the scalability concern, we conducted new experiments on even larger instances (up to 1,500 operations). For each problem size, 10 instances were randomly generated, and both MIStar and OR-Tools were given a one-hour time limit per instance.\n\nThe results, summarized below, highlight two critical advantages of our approach. First and most strikingly, on the highly complex 50x30 instances, **OR-Tools failed to produce any feasible solution within the time limit, whereas MIStar consistently found high-quality solutions**. This demonstrates MIStar's superior robustness and scalability on truly challenging problems.\n\nSecond, for the other large instances where OR-Tools did find a solution, **MIStar achieves comparable solution quality in a small fraction of the time**. For example, on the 100x10 instances, MIStar reaches a solution with a 66.03% optimality gap in just under 16 minutes, while OR-Tools requires a full hour to achieve a 62.22% gap. This massive speed-up, combined with the strong generalization from a model trained only on smaller 20x10 instances, confirms that MIStar provides an effective and highly scalable solution for large-scale FJSP.\n#### Table: Generalization Performance on Larger-Scale Instances\n|Instance Size|Method|Avg. Objective|Avg. Time (min)|Optimality Gap (%)|\n|:-|:-|:-:|:-:|:-:|\n|50×15|OR-Tools|881.45|60.0|39.05%|\n|(LB:537.2)|MIStar-200|969.7|10.6|44.60%|\n|60×15|OR-Tools|1075.1|60.0|46.94%|\n|(LB:570.2)|MIStar-200|1109.8|14.2|48.62%|\n|100×10|OR-Tools|1922.65|60.0|62.22%|\n|(LB:726.5)|MIStar-200|2138.4|15.9|66.03%|\n|50×30|OR-Tools|Infeasible|60.0|-|\n|(LB:N/A)|MIStar-200|1040.1|60.0|-|\n## Adaptation to additional constraints\nWe thank the reviewer for this important point. We would first like to clarify that our focus on the standard, makespan-oriented FJSP is a deliberate methodological choice. It aligns with the mainstream research paradigm in learning-based scheduling[1,2,3], which prioritizes creating powerful solvers for the core NP-hard problem as a foundational step. Even the static, single-objective FJSP remains a formidable challenge, and developing effective heuristics for it is an active and critical area of research [1,4]. \n\nThat being said, we fully agree that adaptability to real-world dynamics is crucial. Our core components are highly modular and allow for the incorporation of additional constraints and objectives with minimal, targeted modifications. We are happy to illustrate this adaptability with two representative examples:\n#### **Handling machine breakdowns：**\nOur framework can elegantly manage unexpected events like machine failures. This is possible because our state representation and action space are inherently flexible.\n* **State:** The machine status is a feature in our graph representation, allowing the breakdown to be modeled by updating the corresponding node. The agent, trained to minimize makespan, will naturally avoid assigning operations to unavailable machines or those with infinite processing times, highlighting the effectiveness of our rich, feature-based state representation.\n* **Action:** All operations currently assigned to failed machine must be re-assigned. Broken machines are masked out when generating candidate actions based on the Nopt2 neighborhood structure. As a result, invalid actions $[O_m, O_n, M_k]$ involving broken machines in the third dimension are effectively filtered out. This ensures the agent always operates within valid constraints.\n* **Reward:** To manage the trade-off between efficiency and stability during rescheduling, the reward function can be augmented. A stability term[5] can be incorporated into the reward to minimize the differences in operation start times between the original and revised schedules $\\sum_{j=1}^{|J|} \\sum_{i=1}^{n_j} \\left| st_t - st_{t-1} \\right|$, thus encouraging minimal disruption to the former schedule[5,6].\n#### **Handling dynamic job arrivals：**\nMIStar is exceptionally well-suited for dynamic re-optimization, a key advantage of our improvement-based approach over constructive methods.\n* **State:** The flexibility of our graph structure allows new jobs to be seamlessly integrated by expanding the state matrices to include their operations and associated constraints. To maintain focus and efficiency, completed operations can be pruned from the state, ensuring the agent always reasons over the most relevant part of the problem.\n* **Action:** Time-based constraints are easily handled. To respect arrival times, we simply filter out any action that would schedule a job's first operation before it is ready. The problem's inherent precedence constraints, already encoded in our graph, automatically handle the sequencing for all subsequent operations.\n* **Reward:** A penalty term can be added to minimize earliness and tardiness across jobs[7], in order to ensure on-time delivery. Additionally, the robustness term above encourages minimal disruption to the earlier schedule[5].\n\nFinally, the size-agnostic nature of our GNN-based policy network [9] is a crucial enabler for these dynamic scenarios. Changes in job or machine quantities do not require scheduling from scratch; MIStar can perform re-optimization from any valid existing solution [8]. Furthermore, our memory mechanism remains robust, as the incidence matrices from schedules of different sizes can be aligned via simple padding or cropping before similarity comparison. This architectural foresight ensures MIStar is not just a static solver, but a truly adaptable scheduling framework.\n## Training cost and generalization\nMIStar is trained on synthetic data for 20,000 episodes (batch size 20, 100 steps/episode), which takes approximately 4 to 13 days depending on the instance size. A key strength of our approach is that the model **does not need to be retrained for different benchmarks**. As demonstrated in Tables 1 and 2, our single trained model demonstrates strong scalability and adaptability across benchmarks (Table 2), achieving the highest average performance across instances and generalizing well to larger, unseen instances (30×10 and 40×10 in Table 1).\n## Regarding the impact of the initial solution\nTo address the reviewer's question, we have performed a systematic evaluation of MIStar's performance starting from initial solutions of varying quality. This new experiment, detailed in Appendix H (Table 4), uses six different initialization strategies, from DRL-based methods to simple priority rules and random solutions.\n\nThe results show that while better initial solutions can lead to higher-quality final schedules within a fixed iteration count, MIStar consistently yields significant improvements regardless of the starting point. Notably, it achieves larger relative improvements when starting from poorer solutions. This demonstrates the robustness of our learned heuristic and its ability to effectively navigate the solution space from diverse initial conditions.\n##\nWe sincerely appreciate the reviewer’s insightful comments in the rebuttal process. Incorporating these insights, along with the new experimental data and discussions, we will revise the final version of the paper to enhance its clarity and strengthen its overall presentation.\n\n[1]Deep reinforcement learning guided improvement heuristic for job shop scheduling, 2022.  \n[2]Flexible job-shop scheduling via graph neural network and deep reinforcement learning, 2022.  \n[3]Flexible job shop scheduling via dual attention network-based reinforcement learning, 2023.  \n[4]Review on flexible job shop scheduling, 2019.  \n[5]Dynamic scheduling in flexible job shop systems by considering simultaneously efficiency and stability, 2010.  \n[6]Robust scheduling for multi-objective flexible job-shop problems with random machine breakdowns, 2013.  \n[7]Multiobjective flexible job-shop rescheduling with new job insertion and machine preventive maintenance, 2022.  \n[8]A review of dynamic scheduling: context, techniques and prospects, 2021.  \n[9] A comprehensive survey on graph neural networks, 2020."}, {"review_id": "SsH6CgAkQ7", "reviewer": "Reviewer_YPJJ", "summary": "This paper presents MIStar, a novel DRL-based improvement heuristic framework for solving the Flexible Job Shop Scheduling Problem (FJSP). Unlike prior approaches that primarily rely on constructive methods, MIStar starts from a complete schedule and iteratively refines it using learned improvement heuristics. Key innovations include: 1) A heterogeneous disjunctive graph representation that models operation sequences and machine assignments explicitly. 2) A memory-enhanced heterogeneous graph neural network (MHGNN) that utilizes past scheduling experiences to improve decision making and reduce local optima traps. 3) A parallel greedy search strategy for efficient exploration of the solution space. Experiments on synthetic and public benchmark datasets demonstrate that MIStar outperforms state-of-the-art DRL-based constructive methods and handcrafted improvement heuristics in both quality and efficiency.", "questions": "How would MIStar adapt to real-time job arrivals or unexpected machine unavailability? The current formulation assumes a fixed problem instance. Please clarify whether the memory mechanism and graph representation can support online updates or dynamic re-optimization.\n\nCan the authors provide a reward curve during training? Understanding how quickly the policy converges and how often it gets stuck in local optima would strengthen the interpretation of results and help in reproducing or fine-tuning the model.\n\nWhy was no ablation on embedding architecture included? Multiple GNN modules are used, including GIN and GAT. How crucial are each of these components? A component-wise breakdown would clarify their individual contributions.", "limitations": "No support for unexpected events: The current model assumes a static schedule and does not consider dynamic changes such as new job insertions or maintenance events. This may limit deployment in real-world systems where dynamic events are common.\n\nNo error bars in reported metrics: Performance results lack standard deviation or confidence intervals, making robustness unclear.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The proposed method is well-motivated and carefully implemented. The combination of memory-augmented GNNs and improvement heuristics is novel and technically sound.\n\nThe methodology is presented in a well-structured manner, with comprehensive figures, examples, and ablation studies to support understanding.\n\nFJSP is a critical real-world problem, and improving its solution quality has significant industrial implications. This work contributes a viable learning-based improvement framework with promising generalization capabilities.\n\nTo the best of my knowledge, this is the first work that brings memory-enhanced GNNs into DRL-based improvement heuristics for FJSP, addressing challenges that existing methods often overlook.\n\nWhile strong comparisons are made against DRL-based constructive and rule-based improvement methods, the absence of comparisons with classic or recent dynamic scheduling algorithms limits the broader applicability assessment of MIStar.\n\nThe framework assumes static environments. In realistic smart manufacturing, events like new job insertions or machine breakdowns are common but not considered or simulated in experiments.\n\nEmbedding choices: The paper uses GIN and GAT for operation nodes and a hetero-GAT for machine embeddings, but ablation studies on alternative embedding strategies or modules (e.g., Transformer variants) are missing.\n\nThe reward function is based on makespan improvement and redundancy penalties, but no detailed reward curve or sensitivity analysis is presented, making it difficult to assess stability.\n\nWhile performance is reported in tables, error bars or statistical confidence measures are absent, making reproducibility and robustness harder to judge.", "was_revised": true, "final_justification": "Thank you for the updates and rebuttals. Since the quality has improved significantly, I change my score.", "rebuttal": "We appreciate the reviewers' feedback and address each comment below:\n## Dynamic events\nWe thank the reviewer for this important point. We would like to clarify that our focusing on static environments is not an oversight of dynamic problems, but aligns with the mainstream research paradigm in learning-based scheduling[1,2,3]. Even the static, deterministic FJSP remains a formidable challenge, and developing effective heuristics for it is an active and critical area of research[4].\n\nThat being said, we fully agree that adaptability to realistic dynamics is crucial. A key strength of MIStar is its modular architecture, designed for future extensibility and minimal modification to handle dynamic environments. Below, we detail how the graph representation, memory mechanism, and action space can be adapted for two representative examples.\n\n**Handling real-time job arrivals**:\n\nMIStar is exceptionally well-suited for dynamic re-optimization, a key advantage of our improvement-based approach over constructive methods.\n1. **Graph representation**: The flexibility of our graph structure allows new jobs to be seamlessly integrated by expanding the state matrices to include their operations and associated constraints. To maintain focus and efficiency, completed operations can be pruned from the state, ensuring the agent always reasons over the most relevant part of the problem[3].\n2. **Memory mechanism**: 0ur memory mechanism remains robust, as the incidence matrices from schedules of different sizes can be aligned via simple padding or cropping before similarity comparison. \n3. **Action space**: Time-based constraints are easily handled. To respect arrival times, we simply filter out any action that would schedule a job's first operation before it is ready[5]. The problem's inherent precedence constraints, already encoded in our graph, automatically handle the sequencing for all subsequent operations.\n\n**Handling unexpected machine breakdowns**:\n1. **Graph representation**: Machine status is a feature in our graph representation, allowing the breakdown to be modeled by updating the node. The agent, trained to minimize makespan, will naturally avoid assigning operations to unavailable machines or those with infinite processing time. Alternatively, Unavailable machines can be directly removed from the graph by pruning their corresponding entries in the state matrices.\n4. **Memory mechanism**: Machine breakdowns can be reflected by assigning a special value (e.g., –1) to unavailable columns in incidence matrices. Alternatively, memory entries can include labels (e.g., breakdown presence or broken machine count) for coarse-grained filtering, followed by fine-grained similarity matching.\n5. **Action space**: Operations on failed machines must be reassigned. Unavailable machines are masked out in the Nopt2 neighborhood to filter invalid actions $[O_m, O_n, M_k]$ involving broken machines.\n\nFinally, the size-agnostic nature of our GNN-based policy network[7] is a crucial enabler for these dynamic scenarios. Changes in job or machine quantities do not require scheduling from scratch; MIStar can perform re-optimization from any valid existing solution [6].\n\n**Comparisons with dynamic scheduling algorithms**\n\nWe appreciate the concern regarding the lack of comparisons with dynamic scheduling algorithms. To address this, we included results of two dynamic methods evaluated on static benchmarks. In future work, we consider to extend MIStar to dynamic scenarios and compare it with more dynamic approaches.\n\n**Table: Comparison with Dynamic Algorithms**\n||la(edata)|la(vdata)|\n|-|-|-|\n|GASAVNS[10]|1143.78|-|\n|HRL[11]|-|954.15|\n|MIStar-400|1099.18|921.85|\n## Reward curve analysis\nAs we are unable to submit figures, we provide a descriptive analysis of the reward curve observed during training. The training process includes 20,000 episodes, which are grouped into batches of 20 to form 1,000 epochs. We then track the average return per epoch throughout training to assess the model’s learning progress over time.\n\nThe curve shows frequent fluctuations in the initial phase (0–200 epochs), ranging approximately between 170 and 210. This high variability reflects the model's active exploration of the policy space. Since new training data is introduced every 20 epochs, the model must continuously adapt to different scheduling instances, which also contributes to these fluctuations. During the mid-phase (200–500 epochs), the curve becomes relatively more stable but still shows several noticeable drops in return, decreasing to around 150–180. This suggests potential local optima or instability in the training process. However, as the model gradually learns a more robust policy, it eventually escapes these suboptimal regions, with the reward converging to a stable range around 230 after approximately 600 epochs.\n\n## Ablation on embedding architecture\nTo accurately extract the key decision-making signals for the policy network—namely, the current scheduling state represented by operation and machine node embeddings—we construct a tailored representation module composed of multiple specialized graph encoders. We adopt GIN[8] to extract structural differences among operation nodes due to its strong discriminative power in graph structure learning. To model the distinct semantic constraints from neighboring nodes (i.e., job predecessors and machine predecessors), we employ a GAT[9] with $n_H$ attention heads, enabling the model to learn the varying importance of different types of neighbors[1][2]. Additionally, we use a HGAT[2] to learn machine embeddings that reflect machine workloads, which serve as critical heuristics for downstream policy decisions—such as guiding the agent to reassign operations from overloaded machines to less loaded ones to reduce makespan.\n\nWe conducted ablation studies on the embedding architecture using four size instances from the SD2. Results below further confirm that each of these components is essential for learning informative and discriminative state representations that support effective policy learning.\n|||10×5||20×5||15×10||20×10||\n|-|-|-|-|-|-|-|-|-|-|\n|**Model**|**Iter.**|**Obj.**|**Time**|**Obj.**|**Time**|**Obj.**  |**Time**|**Obj.**|**Time**|\n|**w/o GIN**|100|348.31|4.97s|616.71|10.72s|491.78|18.12s|548.61|24.80s|\n||200|347.06|10.78s|614.98|22.88s|484.36|37.58s|545.97|53.68s|\n||400|345.73|20.56s|613.98|45.9s|477.8|1.45m|544.31|1.91m|\n|**w/o GAT**|100|350.86|5.82s|618.67|11.34s|492.76|17.85s|548.0|22.63s|\n||200|349.89|9.46s|617.33|22.91s|486.74|36.97s|547.97|51.02s|\n||400|348.33|21.41s|615.99|46.79s|480.66|1.29m|547.87|1.78m|\n|**w/o HGAT**|100|350.49|5.44s|618.15|11.39s|491.97|17.95s|535.78|23.89s|\n||200|349.08|9.74s|616.56|23.01s|483.46|37.01s|532.83|52.47s|\n||400|347.17|20.1s|614.97|46.38s|473.83|1.29m|529.92|1.67m|\n|**MIStar**|100|345.05|5.27s|615.12|11.55s|488.22|18.09s|530.93|25.76s|\n||200|343.43|10.33s|613.75|23.50s|476.93|37.42s|528.92|53.25s|\n||400|342.50|21.39s|612.73|47.93s|465.71|1.31m|525.49|1.88m|\n## Robustness\nTo tackle your robustness concern, we conducted 10 independent runs for each instance in Table 2, and reported the corresponding standard deviation to demonstrate robustness. Due to time constraints, we were unable to include similar statistical measures for the synthetic data in Table 1, but we will incorporate them in the final version to better illustrate performance stability.\n#### Table: Robust Performance across benchmarks（mean ± std）\n|             | mk          | la(rdata)   | la(edata)    | la(vdata)   |\n|-------------|-------------|-------------|--------------|-------------|\n| MISTar-100  | 178.36±0.49 | 963.35±0.92 | 1102.89±2.27 | 925.34±0.25|\n| MISTar-200  | 178.28±0.47 | 961.83±1.07 | 1102.78±2.23 | 924.4±0.22|\n| MISTar-400  | 178.08±0.41 | 960.3±0.98  | 1102.76±2.23 | 923.6±0.24|\n##\nWe are grateful to reviewer for their valuable suggestions. Combined with the discussions and new experimental evidence, these will guide us in revising the final version to boost its clarity and presentation effectiveness.\n\n[1]Zhang C, Cao Z, Song W, et al. Deep reinforcement learning guided improvement heuristic for job shop scheduling[J]. arXiv preprint arXiv:2211.10936, 2022.  \n[2]Song W, Chen X, Li Q, et al. Flexible job-shop scheduling via graph neural network and deep reinforcement learning[J]. IEEE Transactions on Industrial Informatics, 2022, 19(2): 1600-1610.  \n[3]Wang R, Wang G, Sun J, et al. Flexible job shop scheduling via dual attention network-based reinforcement learning[J]. IEEE Transactions on Neural Networks and Learning Systems, 2023, 35(3): 3091-3102.  \n[4]Xie J, Gao L, Peng K, et al. Review on flexible job shop scheduling[J]. IET collaborative intelligent manufacturing, 2019, 1(3): 67-77.  \n[5]An Y, Chen X, Gao K, et al. Multiobjective flexible job-shop rescheduling with new job insertion and machine preventive maintenance[J]. IEEE Transactions on Cybernetics, 2022, 53(5): 3101-3113.  \n[6]Renke L, Piplani R, Toro C. A review of dynamic scheduling: context, techniques and prospects[J]. Implementing Industry 4.0: The Model Factory as the Key Enabler for the Future of Manufacturing, 2021: 229-258.  \n[7]Wu Z, Pan S, Chen F, et al. A comprehensive survey on graph neural networks[J]. IEEE transactions on neural networks and learning systems, 2020, 32(1): 4-24.  \n[8]Xu K, Hu W, Leskovec J, et al. How powerful are graph neural networks?[J]. arXiv preprint arXiv:1810.00826, 2018.  \n[9]Veličković P, Cucurull G, Casanova A, et al. Graph attention networks[J]. arXiv preprint arXiv:1710.10903, 2017.  \n[10]Fuladi S K, Kim C S. Dynamic events in the flexible job-shop scheduling problem: rescheduling with a hybrid metaheuristic algorithm[J]. Algorithms, 2024, 17(4): 142.  \n[11]Lei, Kun, et al. \"Large-scale dynamic scheduling for flexible job-shop with random arrivals of new jobs by hierarchical reinforcement learning.\" IEEE Transactions on Industrial Informatics 20.1 (2023): 1007-1018."}, {"review_id": "9jSlWz8AMl", "reviewer": "Reviewer_wFrm", "summary": "This paper proposes MIStar, a Deep Reinforcement Learning (DRL) framework for the Flexible Job Shop Scheduling Problem (FJSP). The key idea is to move away from constructive DRL methods, which build a schedule from scratch, and instead focus on improvement-based methods that iteratively refine a complete solution. To this end, the authors formulate the problem as a Markov Decision Process (MDP) where the state is a complete schedule and actions correspond to local moves in the Nopt2 neighborhood. \nThe main contributions of the paper are:\n1. A directed heterogeneous disjunctive graph representation for FJSP solutions, which explicitly includes machine nodes and their processing sequences using hyper-arcs.\n2. A Memory-enhanced Heterogeneous Graph Neural Network (MHGNN) that encodes the graph state and leverages a memory of previously visited solutions to enhance decision-making and avoid local optima.\n3. A parallel greedy search strategy that evaluates multiple candidate actions at each step to improve search efficiency.", "questions": "Questions for the Authors:\n\nThe state similarity for the memory module is based on the operation-machine incidence matrix, which ignores the processing order on each machine. Could you please justify this design choice? Have you considered or experimented with more expressive representations for historical states that also encode sequence information, and if so, how did they perform?\n\nRegarding the experimental runtimes reported in Table 1 and Table 2: Are the reported times for the baseline methods (GD, FI, BI) the aggregate time for running searches from 100 different initial solutions? Is the reported time for MIStar for a single search trajectory, or is it also an aggregate? Please clarify how the \"search effort\" is normalized between MIStar and the rule-based baselines to ensure a fair comparison of both solution quality and runtime.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 1, "strengths_and_weaknesses": "Strengths\n\nThe paper tackles the FJSP, a well-known NP-hard problem with significant industrial relevance. The framing of the problem as an improvement task learned via DRL is a promising direction. The authors correctly identify that most recent DRL work has focused on constructive methods, which often struggle to find high-quality solutions. Shifting the focus to learning improvement heuristics is a valuable contribution to the field of neural combinatorial optimization.\n- Well-Motivated Methodological Components: Each component of the proposed MIStar framework is well-motivated by a specific challenge in applying improvement methods to FJSP.\n\nWeaknesses\n\n- Ablation Study Missing: There is no evidence or ablation study provided to isolate the benefit of the memory-enhanced heterogeneous graph neural network (MHGNN) compared to standard GNNs without memory. It is unclear how much the memory module contributes to overall performance. The memory module is a core contribution, but its design raises questions. The state similarity is calculated using the Frobenius inner product of the operation-machine incidence matrix (Lt​). This matrix only captures which machine an operation is assigned to, but not the processing sequence on that machine. It is therefore possible for two schedules with very different makespans (e.g., a good sequence vs. a poor sequence on the same machine) to be considered identical or highly similar by this metric. This seems like a significant oversimplification that could lead to misleading historical information. The paper needs to provide a much stronger justification for why this simplified representation is sufficient.\n- The paper employs parallel greedy exploration runs, but it is not clear whether the computational budget is held constant across all compared models. If MIStar is allowed to explore more solutions in parallel, it may have an unfair advantage in solution quality.\n- The term \"agent\" (e.g., \"agent selects an action...\") is introduced without prior definition, which may reduce clarity for readers unfamiliar with the terminology.\n-The descriptions accompanying Table 2 are brief, and the tables themselves are dense and potentially overwhelming. The paper would benefit from additional visualizations to better communicate model comparisons and results.\n- The paper does not provide code for reproducing the results, limiting the ability of the community to validate and build upon this work.\nLimited Choice of \"Hand-crafted\" Baselines: While the inclusion of GD, BI, and FI is a good start, they are relatively basic local search algorithms. The field of metaheuristics for FJSP is mature, with highly effective algorithms like Tabu Search (e.g., the original Brandimarte paper ) and Genetic Algorithms. \nIncremental Novelty of Graph Representation: The paper introduces a \"novel directed heterogeneous disjunctive graph\". However, it is explicitly \"inspired by the heterogeneous disjunctive graph H [8]\", which is the graph representation used by the HGNN baseline.", "was_revised": true, "final_justification": "The rebuttal answers the weaknesses I pointed in my initial review.", "rebuttal": "We thank the reviewer for their valuable suggestions and comments and address the main concerns below:\n## On the Memory Mechanism: Ablation Study and Design Justification\n### 1. ablation study\n\nWe would like to clarify that an ablation study on the memory module was indeed conducted and is presented in Appendix I (Table 5). To directly answer the reviewer's concern, **this study demonstrates that MIStar consistently outperforms its variant without the memory module, with performance gains ranging from 0.41% to 4.36% across different problem scales.** This confirms the significant and positive contribution of our memory-enhanced design.\n\n### 2. design of the state similarity metric\nWe appreciate the reviewer's sharp observation, which gives us an opportunity to clarify a subtle but crucial detail of our design. We commit to adding more details of $L_t$ to the revised version. The reviewer correctly notes that ignoring sequence information would be a major flaw. However, our operation-machine incidence matrix, $L_t$, **does encode sequence information**. Its elements are not merely binary indicators (0/1) of machine assignment, but rather represent the *processing order index* of each operation on its assigned machine.\n\nThis design ensures that two schedules with identical machine assignments but different sequences (e.g., a good sequence vs. a poor one) are correctly distinguished. For instance, a good sequence `[1, 2, 3, 4, 5]` and a poor, reversed sequence `[5, 4, 3, 2, 1]` on the same machine will be recognized as maximally dissimilar by the Frobenius inner product. The mathematical foundation for this lies in the **Rearrangement Inequality**, which guarantees that the inner product is maximized for similarly ordered sequences and minimized for oppositely ordered ones. This allows our similarity metric to be both computationally efficient and highly sensitive to the quality of the operation sequence.\n\n**Theorem**: *The Rearrangement Inequality states that, for two sequences*\n$a_1 \\le a_2 \\le \\dots \\le a_n$ *and* $b_1 \\le b_2 \\le \\dots \\le b_n$, *the inequalities*\n\n$$\na_1 b_1 + a_2 b_2 + \\dots + a_n b_n \\ge a_1 b_{\\pi(1)} + a_2 b_{\\pi(2)} + \\dots + a_n b_{\\pi(n)} \\ge a_n b_1 + a_{n-1} b_2 + \\dots + a_1 b_n\n$$\n\n*hold, where* $\\pi(1), \\pi(2), \\dots, \\pi(n)$ *is any permutation of* $1, 2, \\dots, n$.\n\n### 3. alternative designs\nWe have considered and tested other expressive representations for the historical states that explicitly encode sequence information. For example:\n1. The adjacency matrix $A_t^{M}$ of operations on machines clearly encodes the processing order between operations, while the binary operation-machine incidence matrix $L_t^{B}$ indicates machine assignment. The state similarity is then calculated by computing the inner products of both matrices separately and summing the results, expressed as:\n\n$$\n\\begin{align*}\n\\omega_{t,t'} = \\langle L_t^{B}, L_{t'}^{B} \\rangle_F + \\langle A_t^{M}, A_{t'}^{M} \\rangle_F\n\\end{align*}\n$$\n\n2. For the operation-machine incidence matrices that store processing order indices, we compute the element-wise difference between two schedules, $L_t$ and $L_{t'}$, to obtain a difference matrix, and then use the reciprocal of its Frobenius norm to measure similarity, formulated as:\n\n$$\n\\omega\\_{t,t'} = \\frac{1}{\\| L\\_t - L\\_{t'} \\|\\_F + \\epsilon} = \\frac{1}{\\sqrt{\\sum\\_{i=1}^{\\mathcal{O}} \\sum\\_{j=1}^{\\mathcal{M}} |(L\\_{t})\\_{ij} - (L\\_{t'})\\_{ij})|^2} + \\epsilon} $$\n\nHowever, these alternatives introduced higher storage and computational overhead without yielding significant performance gains. Our chosen representation thus strikes a deliberate and effective balance between representational power and efficiency.\n\n## Fairness of Parallel Exploration\n\nMIStar circumvents exhaustive neighborhood evaluation and its overall computational budget is notably smaller than that of the baselines.\n\nTypically, the policy network samples an action from the neighborhood to generate a new schedule. The *parallel greedy exploration* refers to the process where, at each step, the policy network samples P(e.g., 50) actions and evaluates the resulting 50 candidate solutions in parallel, selecting the one with the best improvement for further refinement. However, the baseline methods (GD, FI, BI) evaluate the entire neighborhood at each step and select the “optimal” (e.g., FI selects the first improved solution while BI selects the best one) for the next iteration[1]. In this sense, these baselines can also be considered as performing \"parallel\" evaluations on a larger scale, since P in their case equals the full neighborhood size. \n\nFor example, in a 15×10 SD2 instance with an Nopt2 neighborhood size of 240, MIStar evaluates only 50 candidates per step, whereas the baselines evaluate all 240. Thus, our overall computational cost is significantly lower.\n\n## Runtime Clarity \nFor each instance, we generate 100 initial solutions using a sampling strategy, which together form a batch for parallel improvement. The final result for the instance is selected as the best solution within this batch. The reported runtime is the average time per instance after the iterative process finishes, obtained by dividing the total (aggregate) time by the batch size. The runtimes reported in Table 1 and Table 2 for both MIStar and the rule-based baselines (GD, FI, BI) follow this same setting to ensure consistency.\n\nTo ensure a fair comparison, we define the “search effort” as the number of iterations. That is, at a fixed number of iteration steps (e.g., at step 100), we record the corresponding solution quality and runtime for both MIStar and the baselines.\n\n## Improving Readability\nThanks for your careful proofreading. We will gladly revise the manuscript to include a definition of the \"agent,\" add clarifying annotations and visualizations for our tables.\n\n* To improve clarity, we will add a brief definition of *“agent”* in Section 4.1, such as: *“agent, the decision-maker based on a given policy, selects an action…”*.\n\n* To address the concern regarding the brief descriptions of Table 2, we will add clarifying footnotes to explain key notations, as follows:\n  1. “-100”, “-200”, and “-400” denote different iteration budgets;\n  2. “Gap” refers to the average gap to the best-known solutions;\n  3. “Time(s)” denotes the average time for solving a single instance in seconds.\n* We will revise the table layout in the final version and include box plots to better visualize model comparisons and results.\n\n## On the Choice of Baselines\n\nWe thank the reviewer for this suggestion. We agree that classic metaheuristics like Tabu Search and Genetic Algorithms are powerful and highly effective solvers for the FJSP.\n\nOur work, however, is situated within the specific and growing research paradigm of **learning-based improvement heuristics**. The primary goal of this paradigm is not to outperform a highly-tuned, problem-specific metaheuristic, but rather to **learn a generalizable policy** that can discover effective improvement strategies automatically and adapt to different problem instances without manual redesign.\n\nTherefore, we chose to focus our main comparison on two classes of baselines: (1) other state-of-the-art **learning-based methods**[1,2,4], which represent the most direct competitors within our research area, and (2) fundamental local search heuristics (GD, FI, BI), which serve to clearly isolate and demonstrate the value added by our learned policy. We believe this comparison provides the clearest picture of our contribution to the field of *neural combinatorial optimization*. We consider a deep comparison with highly-tuned traditional metaheuristics an exciting avenue for future work.\n## Code\nWe are fully committed to releasing our code upon the acceptance of the paper to support reproducibility and facilitate future research.\n\n## Novelty of graph representation\nWe acknowledge the inspiration from HGNN[2]. However, HGNN is designed for *construction* methods, and its structure provides limited advantages (Appendix B) for *improvement* approaches where complete solutions contain fixed machine assignments[1]. Most importantly, the undirected edges in HGNN hinder the clear encoding of machine processing sequences, which is crucial for distinguishing between different schedules and identifying the critical path when constructing the action space[3].\n\nInstead, our directed heterogeneous graph, tailored for complete schedules, overcomes this limitation by encoding machine processing sequences through directed hyper-edges. These effectively represent the ordering of operations across different solutions without significantly increasing graph density. It adopts a unified structure with fully directed arrows, avoiding the complexity of mixed edge types.\n\n##\nWe deeply thank reviewer’s constructive feedback on strengthening our theoretical foundation. Leveraging these inputs, as well as the additional discussions and analyses, we will refine the final version to improve clarity and ensure a more robust presentation.\n\n[1]Zhang C, Cao Z, Song W, et al. Deep reinforcement learning guided improvement heuristic for job shop scheduling[J]. arXiv preprint arXiv:2211.10936, 2022.  \n[2]Song W, Chen X, Li Q, et al. Flexible job-shop scheduling via graph neural network and deep reinforcement learning[J]. IEEE Transactions on Industrial Informatics, 2022, 19(2): 1600-1610.  \n[3]Mastrolilli M, Gambardella L M. Effective neighbourhood functions for the flexible job shop problem[J]. Journal of scheduling, 2000, 3(1): 3-20.  \n[4]Zhang X, Zhu G Y. A literature review of reinforcement learning methods applied to job-shop scheduling problems[J]. Computers & Operations Research, 2025, 175: 106929."}, {"review_id": "Bngcdf3WGR", "reviewer": "Reviewer_W83L", "summary": "This paper proposes a Deep Reinforcement Learning (DRL)-based improvement heuristic framework named MIStar to solve FJSP problems. The model is presented to address (1) complex state representation by a novel heterogeneous disjunctive graph, (2) effective policy learning by the proposed heterogeneous graph representation learning, and (3) efficient search strategies by a parallel greedy search strategy.", "questions": "Please refer to the above weaknesses.", "limitations": "Please refer to the above weaknesses.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The integration of memory mechanisms with heterogeneous graph neural networks is innovative and well-suited for FJSP.\n2. The proposed method outperforms the traditional heuristics and DRL-based constructive methods across both synthetic and real-world benchmarks.\n\nWeakness:\n1. The analysis of embedding is not presented, even the authors claim that the embeddings are significant for memorizing historical data and extracting state features. \n2. It is unclear whether the GIN and GAT are de facto significant and effective for topological information encoding and semantic information enhancing respectively, referring to many advanced GNN models. More analysis related to the module selection in operation node embedding should be provided.\n3. It is very common to witness changes in the functionality of devices (some devices are capable of doing two kinds of actions), alterations in the quantity of equipment, and sudden shifts in the priority of the job-shops in real smart factories. Although this is a technical work for solving FJSP only, I would cordially encourage the authors to discuss if MIStar can address those challenges or if the authors will consider these in the future works. \n4. Although the answer to open access was No, I would encourage the authors to open source the code or provide detailed instructions for dataset generation and modeling.", "was_revised": true, "final_justification": "The author’s motivation seems more like improving the original technique in order to refresh the baseline metrics, but ignoring the needs in practical applications. \n\nThe author showed the model’s robustness through comprehensive evaluation metrics, but did not initially consider the “From and Back” problem. FJSP is a task driven by industrial needs, yet I have doubts about whether this work can, in turn, be applied back to industrial applications. Accordingly, I provided my concerns and suggestions towards this.\nI appreciate the author’s descriptive answers to several of my questions, but based on my practical experience, I still keep my concerns on the feasibility of the algorithm in industrial applications, particularly regarding whether the model can correctly understand the attributes such as machine functions, changes in quantity, and disable period. This should be proven by more experiments, which do not have any large dataset support to date. Therefore, based on the author’s experimental results and analysis, I have retained my Rating of 4.", "rebuttal": "We appreciate the reviewer for their valuable feedback and address the main concerns below:\n## Analysis of embedding\nIn our framework, the policy network makes decisions based on both the current scheduling state (operation and machine embeddings) and historical information (historical action embedding). Specifically，\n\n- **Operation embeddings** capture the current solution state. Since different scheduling solutions correspond to different graph structures[1]—i.e., different adjacency relations among operation nodes—we extract the topological structure of the graph and the contextual dependencies[1] among operations as the operation embeddings.\n- **Machine embeddings** reflect the machine load by aggregating the features of neighboring operation nodes, and serve as critical heuristics for the policy to reassign operations from overloaded machines to less loaded ones[2], thereby reducing the makespan.\n- **Historical action embeddings** represent actions taken under similar historical states. They serve as a reference to encourage diverse action selection and enhance exploration[3], when combined with the similarity penalty in the reward function.\n\n## Module selection in operation \nTopological information and the semantic information of constraints are key to distinguishing different operation embeddings[1]. \n- **For topological information**, which distinguishes different schedule structures, we chose **GIN**[4]. Its proven strength, equivalent to the Weisfeiler-Lehman test, is essential for capturing the subtle but critical structural differences between operation nodes in varying solutions[1].\n- **For semantic information**, we recognized that an operation's neighbors—job predecessors and machine predecessors—carry different semantic meanings[1, 2]. To handle this, we employed the **GAT**[6]. Its attention mechanism is perfectly suited to learn the varying semantic roles and importance of these different neighbor types, assigning weights accordingly and thus enriching the node representations.\n\nOur module selection is not only theoretically motivated by the structural characteristics of FJSP graphs, but also aligned with mainstream practices[1, 2, 5, 7]. We conducted ablation studies by removing each component. Results below confirm that each of them is essential for learning informative and discriminative state representations that support effective policy learning.\n|||10×5||20×5||15×10||20×10||\n|-|-|-|-|-|-|-|-|-|-|\n|**Model**|**Iter.**|**Obj.**|**Time**|**Obj.**|**Time**|**Obj.**  |**Time**|**Obj.**|**Time**|\n|**w/o GIN**|100|348.31|4.97s|616.71|10.72s|491.78|18.12s|548.61|24.80s|\n||200|347.06|10.78s|614.98|22.88s|484.36|37.58s|545.97|53.68s|\n||400|345.73|20.56s|613.98|45.9s|477.8|1.45m|544.31|1.91m|\n|**w/o GAT**|100|350.86|5.82s|618.67|11.34s|492.76|17.85s|548.0|22.63s|\n||200|349.89|9.46s|617.33|22.91s|486.74|36.97s|547.97|51.02s|\n||400|348.33|21.41s|615.99|46.79s|480.66|1.29m|547.87|1.78m|\n|**w/o HGAT**|100|350.49|5.44s|618.15|11.39s|491.97|17.95s|535.78|23.89s|\n||200|349.08|9.74s|616.56|23.01s|483.46|37.01s|532.83|52.47s|\n||400|347.17|20.1s|614.97|46.38s|473.83|1.29m|529.92|1.67m|\n|**MIStar**|100|345.05|5.27s|615.12|11.55s|488.22|18.09s|530.93|25.76s|\n||200|343.43|10.33s|613.75|23.50s|476.93|37.42s|528.92|53.25s|\n||400|342.50|21.39s|612.73|47.93s|465.71|1.31m|525.49|1.88m|\n\nWhile more advanced GNNs exist, our aim was to establish a strong, well-justified, and interpretable baseline. We believe this study provides a clear and robust validation of our architectural choices.\n## Dynamic change challenges\n\nWe are grateful for the reviewer's encouragement to discuss MIStar's broader applicability. Although our current work focuses on the standard FJSP, we designed MIStar with future dynamic adaptations in mind. We believe its core architectural strengths—a flexible graph representation, a size-agnostic GNN policy, and an adaptable reward function—make it well-suited to address the challenges mentioned.\n### 1. Multi-capability Devices\nThe scenario where machines are capable of performing multiple types of actions naturally aligns with the modeling paradigm of FJSP. The various operations within a job typically correspond to different stages of processing, each representing a specific type of task[10]. In contrast to JSP, where each operation must be processed by a fixed machine[9](i.e., each machine performs only one type of action), FJSP allows each operation to be processed by multiple candidate machines[10]. This implies that machines can handle multiple processing stages within a job, thereby exhibiting multi-processing capabilities. Therefore, MIStar, as a method for solving FJSP, inherently supports the modeling and optimization of device functionality variability.\n### 2. Machine quantity changes\nAlthough changes in machine quantity may alter the graph structure, the size-agnostic nature of our GNN-based policy network enables MIStar to dynamically re-optimize[12] from any valid existing solution, without restarting the scheduling process from scratch. Furthermore, our memory mechanism remains robust, as the incidence matrices from schedules of varying sizes can be aligned via simple padding or cropping before similarity comparison. In addition, the reward function should not only focus on minimizing makespan but also incorporate schedule stability in re-scheduling scenarios. To this end, we can introduce a stability term[11] into the reward to minimize the differences in operation start times between the original and revised schedules $\\sum_{j=1}^{|J|} \\sum_{i=1}^{n_j} \\left| st_t - st_{t-1} \\right|$, thus encouraging minimal disruption to the former schedule[11,13].\n\nTo further handle different types of equipment changes, we introduce more specific strategies:\n\n**Machine Addition:**\n- New jobs can be integrated by expanding the state matrix and enriching feature vectors with arrival times. Their feature vectors should also be enriched with the arrival time.\n- To avoid interference from irrelevant information, operations completed before the arrival of the new machine will not be recorded in the state. This helps reduce noise and ensures a compact state representation during re-scheduling with a large number of added machines.\n\n**Machine Reduction:**\n- Unavailable machines can be removed by pruning their corresponding entries in the state matrices. Alternatively, the original graph structure can be retained by setting the processing time on failed machines to infinity. In this case, the agent, which aims to minimize the makespan, will naturally avoid assigning operations to a machine marked as unavailable or having an infinite processing time. \n- All operations currently assigned to failed machine must be re-assigned. Broken machines are masked out when generating candidate actions based on the Nopt2 neighborhood structure. As a result, invalid actions $[O_m, O_n, M_k]$ involving broken machines in the third dimension are effectively filtered out.\n### 3. Shifts in priority\n\nJob priorities may shift due to changes in customer demand, resulting in urgent jobs requiring higher priority[8]. This can be elegantly addressed through the **reward function**. Jobs can be grouped by urgency of customer orders—i.e., normal jobs and urgent jobs. The objective function for this scheduling problem can be augmented as the weighted sum of the makespan for normal jobs and the total tardiness for urgent jobs[8], which is to be minimized. Moreover, it is possible to divide jobs into more than two groups based on finer-grained urgency levels. The weights assigned to each group can be dynamically adjusted according to their priority. To adapt to real-time shifts in job priorities, the grouping and weighting can be periodically updated at fixed iteration intervals during the scheduling process.\n\n## On Open-Sourcing the code\nWe are fully committed to making our code and models publicly available upon acceptance of the paper to facilitate reproducibility and future research in the community.\n##\nWe extend our heartfelt thanks to the reviewer for their detailed and thoughtful observations during the rebuttal process. Integrating these insights with the new experimental data and our discussions, we will enhance the final version of the paper to improve its clarity and presentation.\n\n[1]Deep reinforcement learning guided improvement heuristic for job shop scheduling, 2022.  \n[2]Flexible job-shop scheduling via graph neural network and deep reinforcement learning, 2022.  \n[3]Marco: A memory-augmented reinforcement framework for combinatorial optimization, 2024.  \n[4]How powerful are graph neural networks?, 2018.  \n[5]A multi-action deep reinforcement learning framework for flexible Job-shop scheduling problem, 2022.  \n[6]Graph attention networks, 2017.  \n[7]Graph neural networks for job shop scheduling problems: A survey, 2025.  \n[8]Metaheuristics for a flow shop scheduling problem with urgent jobs and limited waiting times, 2021.  \n[9]Deterministic job-shop scheduling: Past, present and future, 1999.  \n[10]Routing and scheduling in a flexible job shop by tabu search, 1993.  \n[11]Dynamic scheduling in flexible job shop systems by considering simultaneously efficiency and stability, 2010.  \n[12]A review of dynamic scheduling: context, techniques and prospects, 2021.  \n[13]Multiobjective flexible job-shop rescheduling with new job insertion and machine preventive maintenance, 2022."}]

Author rebuttal:

Meta-review: This paper introduces MIStar, a Memory-enhanced Improvement Search framework designed to tackle the Flexible Job Shop Scheduling Problem (FJSP). Based on comments from reviewers, the merits of this paper include: (1) The integration of memory mechanisms with heterogeneous graph neural networks is innovative and well-suited for FJSP. Particularly, bring memory-enhanced GNNs into DRL-based improvement heuristics for FJSP, addressing challenges that existing methods often overlook.(2) The proposed method outperforms the traditional heuristics and DRL-based constructive methods across both synthetic and real-world benchmarks. (3) Each component of the proposed MIStar framework is well-motivated by a specific challenge in applying improvement methods to FJSP.

One reviewer raised a concern regarding the practical applicability of the approach in industrial settings. However, this concern is relatively minor given that FJSP is a widely recognized and longstanding benchmark in job shop scheduling research.

Following the rebuttal, the paper received one Accept and no negative scores. Given the strengths in both methodological innovation and empirical results, I recommend acceptance of this paper.
Decision: Accept (poster)