Towards Generalizable Multi-Policy Optimization with Self-Evolution for Job Scheduling
Authors: Inguk Choi
Woo-Jin Shin
Sanghyun Cho
Hyun-Jung Kim
Venue: NeurIPS 2025 poster ()
Keywords: Neural Combinatorial Optimization
Job Scheduling Problems
Multi-Policy Optimization
Primary area: optimization
TL;DR: We introduce a novel multi-policy optimization framework with adaptive self-imitation learning for job scheduling problems.

Abstract: Reinforcement Learning (RL) has shown promising results in solving Job Scheduling Problems (JSPs), automatically deriving powerful dispatching rules from data without relying on expert knowledge. However, most RL-based methods train only a single decision-maker, which limits exploration capability and leaves significant room for performance improvement. Moreover, designing reward functions for different JSP variants remains a challenging and labor-intensive task. To address these limitations, we introduce a novel and generic learning framework that optimizes multiple policies sharing a common objective and a single neural network, while enabling each policy to learn specialized and diverse strategies. The model optimization process is fully guided by a self-labeling manner, eliminating the need for reward functions. In addition, we develop a training scheme that adaptively controls the imitation intensity to reflect the quality of self-labels. Experimental results show that our method effectively addresses the aforementioned challenges and significantly outperforms state-of-the-art RL methods across six JSP variants. Furthermore, our approach also demonstrates strong performance on other combinatorial optimization problems, highlighting its versatility beyond JSPs.

Towards Generalizable Multi-Policy Optimization with Self-Evolution for Job Scheduling
Inguk Choi, Woo-Jin Shin, Sang-Hyun Cho, Hyun-Jung Kim*
Manufacturing and Service Systems Lab Dept. of Industrial and Systems Engineering
Korea Advanced Institute of Science and Technology (KAIST)
(inguk0826, wjshin, ie02002, hyunjungkiinHkkiist..
Abstract
Reinforcement Learning (RL) has shown promising results in solving Job Schedul- ing Problems (JSPs), automatically deriving powerful dispatching rules from data without relying on expert knowledge. However, most RL-based methods train only single decision-maker, which limits exploration capability and leaves significant room for performance improvement. Moreover, designing reward functions for different JSP variants remains challenging and labor-intensive task. To address these limitations, we introduce novel and generic learning framework that opti- mizes multiple policies sharing a common objective and single neural network, while enabling each policy to learn specialized and diverse strategies. The model optimization process is fully guided by lebe-labeling manner, eliminating the need for reward functions. In addition, we develop a training scheme that adaptively controls the imitation intensity to reflect quality of self-labels. Experimental results show that our method effectively addresses the aforementioned challenges and significantly outperforms state-of-the-art RI, methods across six JSP vari- ants. Furthermore, our approach also demonstrates strong performance other combinatorial optimization problems, highlighting its versatility beyond JSPs.
Introduction
Job Scheduling Problems (JSPs) are fundamental Combinatorial Optimization Problems (COPs) with significant practical importance across various industries such manufacturing [1], logistics [2], and data centers [3]. Solving a ISP involves assigning jobs to machines (e.g., limited resources) and sequencing them each machine. The goal is find schedule from combinatorial solution space that minimizes (or maximizes) the objective function under problem-specific constraints. Traditionally, ISPs have been solved using exact methods handcrafted heuristic algorithms. However, exact methods are computationally intractable for large-size problems [4], and designing effective heuristics for each JSP variant requires deep domain knowledge and significant manual effort [5].
Beyond expert-designed heuristics, Neural Combinatorial Optimization (NCO) methods, as variants of Hyper- Heuristies (HH) [6]. have recently emerged to automate the heuristic design process [7, 8]. In particular, neural constructive heuristics, which sequentially build solutions from scratch using Deep Neural Networks (DNNs), have attracted significant attention due to their simplicity and flexibility [9, 10, 11, 12]. These methods leverage DNNs to model decision-making policies (traditionally represented by Priority Dispatching Rules (PDRs)) and learn state-to-action mappings from data via Supervised Learning (SL) or Reinforcement Learning (RL). However, due to the NP-hardness of most JSPs, SL approaches struggle to obtain sufficiently high-quality solutions for
*Corresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

labeled data. Accordingly, RL-based policy gradient methods. which optimize policies using reward signals, have gained popularity and shown promising results [13].
However, despite its strengths, applying RL to JSPs still faces two key challenges. (1) Exploration:
Due the exponentially large search space of JSPs [14] and the trial-and-error nature of RI, effective exploration in both training and inference phases is essential for finding high-quality solutions. Nevertheless, most RL-based methods train only a single policy, which often suffers from insufficient exploration due to mode collapse, where the policy distribution converges toward a unimodal distribution during RL training [15, 16]. For Vehicle Routing Problems (VRPs), another well- well-known class of COPs, NCO methods effectively enhance search capabilities by leveraging optimality symmetries (solution symmetry [10] and problem symmetry [17, 18]). However, JSPs lack universally definable beneficial symmetries, making it difficult to enforce effective exploration. (2) Reward shaping: JSPs have numerous variants based on machine environments, constraints, and objective functions [19]. Thus, designing bespoke reward functions for each variant remains a complex and challenging task [20]. Although the objective value can be directly used as a true reward for policy optimization using the REINFORCE algorithm [21], this approach suffers from reward sparsity and non-trivial credit assignment problems [22], which add to the training complexity.
Contributions. In this paper, we propose novel and generic learning framework to address the aforementioned challenges. Rather than training a single policy, our framework aims to learn multiple policies that share the same objective and model parameters, but solve the problem using distinct strategies. To this end, we introduce the MP-ASIL (Multi-Policy Optimization with Adaptive Self-Imitation Learning). designed guide each policy to learn diverse and complementary problem- solving strategies in a fully self-evolutionary manner. MP-ASIL addresses the limitations of RL-based methods in the following ways. Firstly, multiple specialized policies can express a multimodal action distribution, alleviating the mode collapse problem in single policy approaches and improving solution quality as a natural hyproduct of enhanced search capability. Secondly, MP-ASIL autonomously generates training labels to guide model optimization, eliminating the need for problem-specific Markov Decision Process (MDP) formulations. Beyond addressing the RL limitations, we also develop training scheme that adaptively controls imitation intensity based on the quality of the self-teacher, mitigating fundamental drawbacks of existing Self-Imitation Learning (SIL)-based methods. Finally, MP-ASIL is a task- and model-agnostic learning framework, enabling easy plug-in to diverse neural solvers across various problem domains.
To validate the effectiveness of MP-ASIL, we evaluate it on six widely studied JSPs: Single Machine Scheduling Problem (SMSP), Unrelated Parallel Machine Scheduling Problem (UPMSP), Permu- tation Flow Shop scheduling Problem (PFSP), Flexible Flow Shop scheduling Problem (FFSP), Job Shop Scheduling Problem (ISSP), and Flexible Job Shop Scheduling Problem (FISSP). The experimental results demonstrate that ASIL successfully unlocks the potential of models for sig- nificantly improved exploration capabilities and overall performance, providing new state-of-the-ar results on various synthetic and benchmark datasets. Furthermore, MP-ASIL also demonstrates strong performance on other COPs, underscoring its broad applicability beyond JSPs.
2 Related Work
Neural Constructive Heuristics for JSPs. Recent advances in artificial intelligence have opened new avenues for solving JSPs with Machine Learning (ML) [23]. Various learning-based approaches have been studied, including neural improvement heuristics that iteratively refine complete solutions via neural-guided local search [24, 25, 26] and hybrid methods that integrate ML into classical heuristics [27, 16, 28J. Nonetheless, most learning-based methods have primarily focused on neural constructive heuristics. L2D [11], a seminal work in this area, introduces a Graph Neural Network (GNN)-based policy for solving JSSP. It sequentially assigns operations to machines using the topological information of partial solutions represented as disjunctive graphs, outperforming tradi- tional dispatching rules. Building on this success, several methods have been proposed for diverse ISP variants, differing in how the networks are designed (e.g., GNN-based policies [29, 30, 31] or Transformer [32]-based policies [12, 33]) and how the networks are trained (e.g., actor-critic methods [34, 35. 36, 37J, REINFORCE algorithms [38, 39,44, 40, 41], or SL [42, 43, 44]). Despite these advancements, most existing approaches only train a single policy, limiting exploration capability and

---

leaving substantial room for performance improvement. Furthermore, they often require specialized MDP formulations or expert knowledge for training, thus limiting their generalizability to other JSPs.
Recently, to eliminate the need for reward function design and labeled data, SII.-based methods have emerged as self-labeling approaches for solving JSPs. In this paradigm, a policy generates multiple candidate solutions and selects the best one as the expert trajectory for SL. SLIM [20] generates candidate solutions via vanilla stochastic sampling from a single policy, which produces many duplicate candidates, thereby leaving less space for potentially better solutions. To improve the sampling process, SI GD [45] proposes a method based on drawing trajectories in multiple steps using stochastic beam search. However, this approach demands extensive search effort for each instance and careful hyperparameter tuning. Existing SIL-based methods also disregard the quality of their self-labels and exhibit low sample efficiency as they rely solely on the best solution and discard the rest. In contrast, our work addresses these limitations via the simple yet powerful MS-A and demonstrates its effectiveness across various JSPs.
Improving Solution Diversity in NCO. Many recent NCO methods for VRPs follow the POMO approach [10], improving exploration by generating multiple solutions from different starting points. However, in JSPs, initial actions often significantly impact solution quality, limiting the applicability of the POMO method to JSPs. Although LCP [46] proposes a general methodology that encour- ages sampling diverse solutions via entropy regularization, computing the entropy over the entire trajectory remains computationally intractable, Recently, Generative Flow Networks (GFlowNets) [47] have gained attention due to their powerful exploration capabilities [48, 49, 16, 50]; however, substantial post-search efforts are still required to achieve competitive results. For JSPs, some studies improve solution quality through beam search [51], active search [52], or look-ahead search [53], yet approaches specifically aimed at promoting solution diversity remain limited.
A promising research direction in NCO involves training multiple policies to learn different solution patterns. MDAM [15] proposes an Attention Model (AM) [9] with multiple decoders to train diverse policies for VRPs. It maximizes the Bellback-Leebber divergence between initial action distributions to encourage distinct solution patterns. Poppy [54] introduces "Winner-takes-all" strategy as a REINFORCE variant for multi-decoder training, in which only the best-performing policy is updated at each iteration. Despite their effectiveness, multi-decoder models require a separate decoder for each policy, resulting in substantial computational overhead and limiting scalability the number of policies increases. Similar to our work, COMPASS [55] and PolyNet [56] use continuous or discrete latent spaces to represent multiple policies within single model. However, both methods train the model using a variant of REINFOR [54], where gradients are computed from complete trajectories. As result, the training process suffers from high variance and instability.
3 Preliminaries
Job Scheduling Problems. In this work, we focus on standard and static JSPs. A standard JSP
instance of size [J] x [M] consists of a set of jobs J. set of machines M, and set of operations
O. Each job j E I comprises my operations {0₂) ) C O that must be processed in a predefined
order O₁ operation Ojt can be processed on exactly one machine from its set of eligible machines M₁ S M with processing time Pjck E Rs0 on machine k E MMji. Based on this formulation, each JSP is uniquely characterized by its specific machine environment, constraints, and objective functions [57] (see Appendix A for details). Given JSP instance s ~ D, where D is an instance distribution, our goal is to find a solution 7 E Ω, where Ω is a finite solution space that satisfies all constraints while minimizing (or maximizing) a predefined objective function f (T. - R. f need not be injective; due to the multimodality of the objective function in JSPs [14], distinct solutions can have the same objective value. In this paper, without loss of generality, we consider minimization problems.
Oşi + - O jmy, where Oje denotes the äth operation of job j. Each
Constructing Solutions Using a Parameterized Policy, A JSP solution T can be autoregressively constructed by sequentially assigning each operation to a compatible machine according to the policy and appending it to the end of that machine's 's operation sequence. At this point, we define (Ti..... Tt.... (To) as a sequence of decisions, with the policy no modeled as a DNN parameterized by As illustrated Figure 1, at each decision step I, the parameterized policy computes conditional action distribution Te( Tx)) over the next operation T,, where T<t
3

---

Operations
Machines
Eligibility
Partial Sol.
Partial Sol.
Solution t
Pollcy
Policy
Problem Instance
00o0
Action T₁
Action F2
Figure 1: Illustrative example of sequential decision-making process using neural constructive heuristics to build a solution T.
represents the partial solution until step guiding the sequential decision Decision-making process until all operations are scheduled. Consequently, the overall policy To s) for generating a solution т given instance is factorized as:
10
(T
8)
(T sT))
(I)
Methods
In this section, introduce MP-ASIL, novel and generic learning framework to address several challenges in solving JSPs with RL. An overview of MP-ASIL is illustrated in Figure 2.
4.1 Multi-Policy Representation: Latent Conditioned Policies
As discussed in Section 1, enforcing effective exploration in JSPs is challenging, and single policy approaches struggle to balance exploration and exploitation. To address these issues, we aim to learn multiple policies (a set of neural heuristics) that share the same objective and model parameters but can represent diverse and complementary solution patterns. this work, we model this population by conditioning a single neural network on different latent variables, referred to latent conditioned policies [58, 55, 56]. Formally, the latent conditioned policy is described as oT(- 18 8, conditioned on an instance s and the latent variable z E Rdd, By sampling multiple latent variables 21 ,.... z from a fixed latent distribution 2, we can obtain a policy set II as follows:
II = [TO( s,,') 2'~2, 1,2,.... .)..
Each latent variable defines distinet policy, enabling single DNN to represent multiple decision- makers. These latent conditioned policies can be implemented regardless of the underlying architec- ture. Appendix provides deeper motivation for using latent variables to represent the population, as well as the implementation details and the distribution for sampling the latent variables.
4.2 MP-ASIL: Multi-Policy Optimization with Adaptive Self-Imitation Learning
Motivation. Given our motivation for using multiple policies, the following question naturally arises: How can we guide these policies to learn diverse and complementary croblem-solving strategies? This question emerges because merely representing multiple policies does not ensure that they can generate diverse solutions. To answer this, we introduce MP-ASIL designed to guide each policy to specialize into distinct yet powerful schedule generator. Our method is based on three principles: (1) we aim not merely for diversity (e.g., random policies as extreme case), but for useful diversity that effectively helps to find better solutions [59]; (2) unnecessary for every policy in II to show strong performance on a given instance as inference requires selecting only the best solution among candidates; (3) the following population-level inference objective, defined as:
( min( 8). ... -(T*; s)}:
should be reflected during training. However, RI--based methods suffer from sparse learning signals, as feedback emphasizing the population objective is provided only after generating complete

---

Latent variables
O :Updated embeddings
Lateet conditioned policies
A: Sample k Solutions
B: Best Solution Selection
Self-Teacher
Single ONN
Best solution
( M
M
Rollout
Candidate
2
Update function
solutions
Solution ranking
Problem Instance
...
Labal quality indicator
Pseudo labef
TAMIA M
C: MP-ASIL
Conditioning
Train best conditioned policy
Update
using MP-ASIL
Latent variables
policies
Exp
lup (
Figure 2: An overview of MP-ASIL. Step A (Section 4.1): We generate h distinct policies by conditioning a single DNN on latent variables, and sample solutions from these policies. Step (Section 4.2): Among these l solutions, the one with the lowest objective value is selected as the pseudo-label T*. Step C (Section 4.2): The model trained to imitate T using MP-ASIL.
decision trajectory. Moreover, designing dense surrogate reward functions is complex and non- trivial task. To overcome these challenges, we reformulate the problem learning heuristics from return-mant netur-mmxxiiizttion task to classification task, in which the model autonomously generates and imitates pseudo-labels corresponding the best current action at each constructive step.
Training Procedure. Specifically, for each training instance (Step A:) we draw & latent variables from Z and generate & policies by conditioning the policy network on the sampled variables. (Step B:) From these policies, we roll out & candidate solutions simultaneously and select the one with the lowest objective value the pseudo-label T* arg min,' (T''.....T" f(r²,
(r7,,s) s), obtained from the best-performing policy oo(-|s, 2*). (Step C:) The model is then optimized to imitate the best decision T' {-í..... ..... TOr) each step in SL manner (maximizing the conditional log-likelihood), However, pseudo-labels are not guaranteed to be globally optimal, and their quality can vary according to the sampled policies. Therefore, to adaptively control imitation intensity based on pscudo-label quality, we modify the loss function (cross-entropy loss) as follows:
(I((T) s) mean [) std(s)
LMP-ASIL =
log ( | (,,T)
where mean (8) = Ete f(T", 8) is the average objective value across k candidate solutions and std(s) / E (f(Ti, - mean(s) s)} is the standard deviation. Equation (4), we use the normalized advantage value [f(r".s) meen(s)) as pseudo-label quality indicator that enables adaptive and(
SIL, where superior lacudo-labels are strongly imitated and less informative pseudo-labels are weakly imitated.
Rationale of MP-ASIL and Summary. Our learning framework establishes self-evolutionary loop via an iterative optimization process by generating and imitating progressively stronger self-teachers. Notably, to reflect the population-level objective in Equation (3) during training, our method updates the model based solely on the performant policy, incentivizing higher probabilities for specific actions conditioned on x* and s. This training procedure naturally encourages the latent space to be diverse (guided by latent variables) and specialized (optimized for distinct instance sub-distributions). As result, trained latent conditioned policies can represent a multimodal trajectory distribution without requiring diversity-enfor enforcing mechanisms (e.g., entropy bonus), mitigating the relatively deterministic action distribution problem in single policy approaches. Our approach also resolves the sparse feedback problem RL by removing the need for reward functions.
Beyond overcoming RI limitations, MP-ASIL improves upon existing SIL-bbseed methods by leverag- ing information from all sampled solutions, improving sample efficiency and facilitating adaptive imitation intensity control to avoid over-exploitation of suboptimal solutions.
5

---

Algorithm 1 MMP-ASIL training
1: Input: Model parameters 0, instance distribution D, latent variable distribution 2, number of epochs E, number of training steps batch size B, and number of policies
2: Initialize model parameters 0.
3: for epoch
E do
4: for step 1 to I" do
5:
8; f- SampleInstance(D)
Vi (I....... B}
6:
II, = [ 8, 2) + SamplePolicy(2), E .L.....,))
7:
[T] [T]..... ................................ 7 t SampleRollout(II) Vi (1.... B}
8:
Ti arg min r/ :....) f(T Wi {1, B) Select the best solution.
MMP- = B Ei=1 (((r)s))) me)n
E log Tae (Ti 8/1 =i, 2f)
9:
std(ac)
10:
+ Ad,m(0, VoLMP.ASH.)
Update solely based on the performant policy.
11: end for
12:
end for
13:
Output: Trained model parameters
Last but not least, MP-ASIL can be directly applied existing neural constructive solvers (detailed in Appendix B.1) and JSPs without any algorithmic modifications, since our method leverages the fundamental property of JSPs that solutions generated for the same instance can be discriminated by their objective values. Therefore, we can easily obtain the MP-ASIL recipe ingredients (latent conditioned policies, pseudo-label, and label-quality indicator) for any setting. The mini-batch training of MP-ASIL is summarized in Algorithm 1.
5 Experiments
We evaluate MP-ASIL on six representative JSP variants: SMSP, UPMSP, PFSP, FFSP, JSSP, and FISSP. These problems cover wide range of JSP scenarios. Detailed definitions of each problem are provided in Appendix C. We first describe the experimental settings of MP- -SIL (Section 5.1) and then present the experimental results and detailed analysis (Section 5.2). All experiments are conducted on 24-core Intel(R) i9-1 19-1490KKS CPU and a single NVIDIA GeForce RTX 4090.
5.1 Experimental Settings
Model Training. We implement MP-ASIL on top of the problem-specie backbone models for each task, for two reasons. First, neural solvers for JSPs have developed with specialized network architectures tailored to each problem. Second, this experimental design highlights MP-ASIL as generic learning framework that is agnostic to the problem type and underlying model architecture. We use training hyperparameters of the backbone models from original papers whenever applicable. Detailed model architectures and training settings are presented in Appendices C and F. Additionally, Appendix D.I provides validation scores during the training process.
Baseline Methods. We compare AS-A with various -ftt----t----ttttt classic heuristics and NCO methods for each problem. Details of the baselines for each problem are described in Appendix C.
Test Datasets & Inference. We evaluate MP-ASIL on benchmark and synthetic datasets widely used in the NCO and the operations research communities (Appendix C). At inference time, we select the best solution from & candidates generated by the II. To ensure fair comparison, we match the sample size reported in prior studies using the same architecture; otherwise, we set k = 128.
Performance Metrics. We use three metrics for evaluation: average objective value (Obj.), average performance gap (Gap), and total inference time (Time). The performance gap for each method on an instance s calculated as 100 x (J²: ft)/ff. where f the objective value obtained by each method, and fg is the best-known objective value for s. Note that reported Time may not be directly comparable across methods due differences in hardware and other experimental settings. Therefore, for clarity, results obtained from the original papers are marked with an asterisk (*).

---

Table 1: Experiment results on SMSP, UPMSP, and FFSP. t: Methods using the same model as MP-ASIL. Exact: Exact solver. Heuristics: Handcrafted heuristics. NCH: Neural constructive heuristies. Hybrid: Hybrid methods. Gray: : Our (MP-ASII, results. S: Sampling size. J: Lower
better. Bold: Best Obj. and Gap among the NCO methods except for Large. : Instance sizes unseen during AP-A training. Time units: (seconds), m (minutes), and h (hours).
SMSP 50
SMSP 100
SMSP 500
Method
Type
Obj.
Gap
Time
Obj 4
Gap
Time
Obj. L
Gup
Time
EDD
Heuristies Heuristies
0.3268
49.84%
(0s)
0.3950
66.24%
(0s)
0.7287
91.70%
(Is)
ACO [27]
0.7787
>100%
(1.1m)
6,9138
>100%
(2.4m)
646.81
>100%
(28.9m)
DeepACO [27]
Hybrid
0.2296
5.27%
(1.1m)
0,2551
7.36%
(2.6m)
0.5944
61.30%
(29m)
GFACS [16]
Hybrid
0.4202
92.64%
(1.5m)
1,2153
>100%
(3m)
14.612
>100%
(33.7m)
KP-ASIL (k=
NCH
0.2181
0.00%
(56)
0.2376
0.00%
(17s)
0.3691
0.16%
(14.5m)
MP-ASIL (Large)
NCH
0.2181
0.00%
(1m)
0.2376
0.00%
(2.3m)
0.3685
0.00%
(53.5m)
Method
Type
UPMSP 50x3
UPMSP 50x6
UPMSP 100x6
Obj.
Gup
Time
Obj. 1
Gap
Time
Obj. L
Gap
Time
EDD
Heuristics
2836.8
>100%
(1s)
778.5
>100%
(1s)
2472.1
>100%
(2s)
AICSR_Rm Rm [60]
Heuristies
877.0
22.91%
(6.6m)
294.5
14.40%
(6.9m)
735.6
75.94%
(10.0m)
et (S=6) I [41]
NCH
784.4
9.94%
(1.8m)
294.2
14.29%
(2.4m)
502.4
20.16/%
(10.6m)
MP-ASIL (R=6)
NCH NCH
751.9
5.37%
(1.8m)
275.7
7.09%
(2.4m)
458.1
9.57%
(10.7m)
NP-ASIL (Large)
713.5
0.00%
1m.
257.4
0.00%
(24.6m)
418.1
0.00%
(1h)
FFSP 20x 12
PPSP 50x 12
FFSP 100x
Method
Type
Obj.
Gapl
Time
Obj 4
Gapl.
Time
Obj. 4
Gap.
Time
CPLEX (Im)* [6]]
Exact
46.4
81. 11.00%
(17h) (167h)
CPLEX (10m)" [61]
Exact
36.6
42.80%
SPT* [12]
Heuristies
31.3
22.12%
(40s)
57.0
14.22%
(Im)
99.3
10.71%
(2m)
GA [62]
Heuristics
30.6
19. 19.39%
(7h)
56.4
13.03%
(16h)
98.7
10.04%
(29h)
PSO* [63]
Heuristies
29.1
13.54%
(13h)
10.42%
(26h)
97.3
8.48%
(48h)
MaiNet (S=24) [12]
NCH
27.3
6.51%.
(8s)
51.5
3.21%
(13s)
91.5
2.02%
(26c)
PolyNet (k=24) 1 [56]
NCH
26.9
5.11%
(8s)
51.2
2.56%
(13s)
91.1
1.59%
(27s)
NP-ASIL (l:24)
NCH
26.9
4.88% %
(8s)
51.1
2.40%
(13s)
90.9
1.32%
(27s)
MP ASIL (Large)
NCH
25.6
0.00%
(26s)
49.9
0.00%
(1.1m)
89.7
0.00%
(3.2m)
Table 2: Experiment results on PFSP using the TA benchmark. G: Greedy action selection. The Time metric is reported in Appendix D.2.
20x5
20x 10 Gap
50x5 + Gap
50x Gap-1
100x5 Gap 1
100x
200x10 Gap
Avg. Gap J
Method
Type
Gap L
Gap
ILS [64]
Heuristics
6.81%
9.45%
4.14%
11.69%
3.44%
9.57%
6.63%
7.39%
IGA [65]
Heuristics
3.36%
10.56%
1.97%
7.53%
1.03%
5.73%
3.43%
4.80%
NEH [66]
Hcuristics
2,40%
4.45%
0.66%
4.69%
0.41%
2.04%
1.28%
2.28%
(L [42]
NCH
18.20%
26.96%
12.30%
26.76%
10.13%
19.03%
15.25%
18.38%
PFSPNet (Gy* [38]
NCH
14.78%
11.95%
8.21%
11.65%
Q-L.earnin (8=5)* [37]
NCH
9.90%
13.41% 9%
6.24%
15.43%
4.87%
11.64%
8.74%
10.03%
NP-ASIL (k=128)
NCH
0.37%
3.32%
0.22%
4.05%
0.16%
2.15%
1.51%
1.68%
5.2 Experimental Results
Benchmark Results. We first evaluate the performance of MP-ASIL on synthetic datasets for SMSP, UPMSP, and FFSP. The test datasets contain 100, 500, and 1,000 instances per problem size for SMSP, UPMSP, and FFSP, respectively. Additionally, we report results for MP-ASIL (Large). which generates & 16 policies, serving as an anchor for computing the Gap. As shown in Table 1, MSIL significantly outperforms all baselines, achieving state-of-the-an results across all problem types and problem sizes. Specifically, for SMSP, DeepACO [27] and GFACS [16] retrain models for each problem size. In contrast, MP-ASIL trains solely on small-size instances ([]|=50) yet demonstrates remarkable cross-size generalization, achieving 0.00% Gap for SMSP 50 and SMSP 100, and 16% Gap for SMSP 500. For UPMSP, we use the same network architecture (except for the multi-polic implementation) and training settings as Cho et al. [41], differing only in the policy optimization manner (REINFORCE algorithm with shared baseline [3, 17] vs. MP-ASIL). Table 1 shows that MP-ASIL strongly outperforms Cho et al. with the advantage of -PIL becoming more pronounced as problem sizes increase. Note that the ATCSR Rm [60] results are obtained through greedy
7

---

Table Experiment results on JSSP using the TA benchmark. NIH: Neural improvement heuristics.
The Time metric is reported in Appendix D.2.
Method
Type
15x15
10x
20
30x15
30x20
50x15
50x
100x20 .
Avg.
Gap
Gap 4
Cap 4
Gap 4
Cap 4
Gap
Gap
Gap 4
Gap
Gurobi (3600s) [20]
Exact
0.1%
3.2%
2.9%
10.7%
13.2%
12.2%
13.6%
11.0%
8.4%
OR Tools (3600s) [67]
Exact
0.1%
0.2%
0.7%
2.1%
2.8%
3.0%
2.8%
3.9%
2,0%
L.D (Gy) [11]
NCH
26.0%
30.0%
31.6%
33.0%
33.6%%
22.4%
26.5%
13.6%
27.1%
1,20 (S=128)* [1]]
NCH
17.1%
23.7%
22.6%%
24.4%
28.4%
17.1%
20.4%
10.7%
20.5%
SN (G)" [29]
NCH
15.3%
19.4%
17.2%
19.1%
23.7%
13.9%
13.5%
6.7%
16.1%
RASCL (G)" [36]
NCH
14.3%
16.5%
17.3%
18.5%
21.5%
12.2%
13.2%
5.9%
14.9%
RS (G)* [39]
NCH
14.8%
16.5%
16.9%
14.4%
17.7%
6.7%
10.0%
2.6%
12.5%
SI GD (G)" [45]
NCH
9.6%
9.9%
11.1%
9.5%
13.8%
2.7%
6.7%
1.7%
8.4%
SLIM (S=512)" [20)
NCH
6.5%
8.8%
9.0%
10.6%
12.7% %
4.9%
7.6%
2.1%
7.8%
L2S-500 [25]
9.3%
11.6%
12.4%
14.7%
17.5%
11.0%
13.0%
7.9%
12.2%
TBGAT 500* [26]
NIH
8.0%
9.9%
10.0%
13.3%
16.4%
9.6%
11.9%
6.4%
10.7%
NP-ASIL (A=512)
NCH
6.8%
8.5%
8.7%
10.4%
12.8%
4.2%
7.0%
1.0%
7.4%
search over 146 heuristic parameter configurations for each instance, following the original paper. More detailed results for UPMSP are provided in Appendix D.3. For FFSP, we implement MP-ASIL on top of the trained MatNet [12] and show remarkably better performance than all baselines.
Table compares MP-ASIL with baseline methods on PFSP using the well-known Taillard (TA) benchmark [68].2 We apply MP-ASIL to the MatNet-based model. From the table, we observe that previous NCO methods cannot beat classical heuristics; however, MP-ASIL considerably surpasses all neural solvers and even exceeds traditional approaches in terms of average Gap and Time. Although direct comparisons are limited by the lack of reported inference times from some neural solvers, MP-ASIL solves all instances for each problem size within one second (see Appendix D.2). Appendix D.4 provides experiment results on synthetic PFSP datasets. Table 3 compares MP -SIL with other methods on JSSP using the TA benchmark. As shown in the table, SLIM [20], which differs from MP-ASIL in learning strategy but uses the same backbone model, already outperforms all learning- based methods in terms of Time and average Gap. Nevertheless, MP-ASIL achieves a relative performance improvement of about 5. 1% in average Gap. Experimental results additional JSSP benchmarks are provided in Appendices D.5 and D.6. Due to space limitations, experimental results on deterministic and stochastic FJSSP can be found in Appendix D.7.
Ablation Studies. Recall that MP-ASIL consists of three key components: (1) multiple policies represented by latent variables, (2) SIL to optimize multiple policies, and (3) an advantage weight to control imitation intensity. To validate the contribution of each component to enhanced performance, we conduct ablation studies by progressively removing individual components. Table 4 clearly shows that our full version consistently surpasses all ablation versions by a large margin, highlighting the critical role of each component. We provide ablation results on all test instances in Appendix D.8.
Table 4: Result of ablation studies. AdvW: Advantage weight. MP: Multiple policies. 1: Performance drop relative to ASILSIL. In the MP-ablation version, latent conditioned policies are replaced by a single policy. In the SIL-ablation version, SIL is substituted with RL approaches: the REINFORCE algorithm with shared baseline [3, 17] for a single policy or Poppy method [54] for multiple policies.
IX X / is equivalent to the SLIM [20].
AdvW
MP
SIL SMSP 100
UPMSP 100x6
PFSP 100x10
FFSP 100x
JSSP 100x20
0.00%
9,57%
2.15%
1.32%
0.96%
X
V
0.67% (0.67% f)
10.30% (0.73% f)
3.56% (1.41% f)
1.37% (0.05% 1)
1.75% (0.79% f)
X
X
3.37% (3.37% 1)
14.33% (4.76% f)
3.57% (1.45% T)
1.40% (0.08% 1)
2.10% (1.14% T)
X
35.77% (35.77% f)
13.50% (3.93% 1)
2.16% (0.01% 1)
1.59% (0.27%
1)
2.47%
(1.51% f)
x
X
6.69% (6.69%
20.16% (10.59%
3.78% (1.63% T)
2.02%
(0.70% 1)
3.96% (3.00% f)
The Effeec of k. We analyze the effect of k on model performance during training and infer- ence. We train our model using different values of k, with A E (32, 64, 128) for PFSP and k E [64, 128, 256) for ISSP. We then evaluate the trained models across various inference set- tings with & E {32, 64, 128, 256, 512}. Figure 3 presents the analysis results on the TA benchmark.
"The best-know results for PFSP and JSSP obtained from http: http::/misttc hew. vd. ch/taillard/.
8

---

PFSP 20x5
PFSP 50x5
PFSP 100x5
ning k-32
Training k-32
Training k-32
0.8
Training 6=
Training k=
Training 6=
Gap (%)
Trai Training k-128
0.4
Training k-128
0.30
Training k-128
0.6
0.3
0.20
0.2
0.10
32
64
128
256
512
32
64
128
256
512
32
64
128
256
512
JSSP
15x15
JSSP 20x15
JSSP 20x20
Training k-64
Training k-64
Training 1-128
10.5
Training k=
Gap (%)
Training 2m2
10.0
Training 2-256
9.5
10
Training k=64
9.0
7
8.5
Training k-128
Training k-256
9
64
128
256
512
32
64
128
256
512
32
64
128
256
512
Inference time k
Inference time k
Inference time
Figure 3: The effect of l on model performance. The results averaged over ten runs.
(a) SMSP 20
(b) PFSP 20x5
Paccontage of unlluue situtanne
2.00
Table 5: Experiment results TSP 100 and CVRP 100. Poppy uses 16 decoders for TSP 100
20-
40
and 32 decoders for CVRP 100. d: Days. Other
20-
50
symbols follow definitions provided in Table 1.
40-
40
Method
TSP 100
CVRP 100
Gap 4
Time
Gap 4
Time 4
32
128
256
512
1424
512 1004
LKH3*
0.000%
(8h)
0.00%
(6d)
Sampling siize
POMO #t
0.146%
(1m)
0.76%
(2m)
REINE
MP-ASIL
Sym-NCO *t
0.180%
(1m)
0.89%
(2m)
Figure 4: Average percentage of unique solutions. The 2-aaxis denotes the number of candidate solu- tions per instance.
Poppy*
0.07%
(1m)
0.51%
(5m)
MP-ASIL
0.000%
(1m)
0.28%
(2m)
From the figure, we can observe that (1) training with larger l generates stronger models, and (2) increasing & at inference time consistently enhances performance. These findings align with our hypothesis that larger & produces more specialized decision-maken. enabling more extensive solution space exploration and increasing the chance of finding better solutions, albeit with increased memory and computational requirements.
Exploration Capability. In this part, we validate the capability of MP-ASIL to generate diverse solutions. For evaluation, we use 1,000 instances for both SMSP 20 and PFSP 20x5. We intentionally choose small-size problems, which represent challenging scenario for generating diverse solutions [69]. The solution diversity is calculated as the average percentage of unique solutions among candidates generated per instance, which is widely used population-level diversity metric [69, 56). For comparison, we also report the solution diversity of representative single policy approaches, such as REINFORCE with shared baseline and SLIM. Figure 4 demonstrates that MP-ASIL achieves significantly higher average solution diversity than baselines across all scenarios. Notably, MP- ASIL shows diversity of 99.4% for SMSP 20 even at k=1024. emphasizing its remarkable ability to generate diverse solution patterns. Additionally, we can observe that REINFORCE generates many duplicate solutions at the sampling stage, pointed out in many recent studies [15, 45, 16).
Policy Specialization. We verify that each policy specializes in distinct instance sub-distributions by analyzing how the best-performing latent variable z varies across instances. Specifically, we randomly sample 16 policies, evaluate their performance on batches of instances, and count the

---

(a) SMSP 50
(b) UPMSP 50x3
(c) PFSP 20x5
(d) JSSP 10x10
80
Winning times
60
60
40
40
20
20
20
20
0
Latent conditioned policies
Figure 5: Number of instances where each policy performs best (winning times). 16 policies on the --axis are ordered arbitrarily.
number of instances each policy solves best. From Figure 5, we find that each policy achieves top performance across different instances. These results demonstrate that different policies specialize in producing high-quality solutions for distinct instance sub aub-distributions, leading to significantly improved overall performance and robustness. To aid better understanding, visualizations of the performance landscape in the policy latent space provided in Appendix D.9. Additionally, can search the policy latent space to find promising latent variables for each instance at test time. Details on this approach can be found in Appendix D.10.
Experiments with Routing. Finally, to demonstrate the versatility of MP-ASIL, we apply it to other COPs, specifically the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) with 100 nodes (denoted as TSP 100 and CVRP 100), which are extensively studied in the NCO literature. We implement MP-ASIL on top of POMO [10], training on n 100 node instances uniformly distributed in 00, 1J2. We follow the original POMO training hyperparameters (see Appendix F). We compare MP-ASIL with state-of-the-art neural solvers, including POMO, Sym-NCO [17] and Poppy [54], using synthetic datasets from [10]. At inference time, MP-ASIL, POMO, and Sym-NCO generate 8 x n2= k) solutions for each instance of size n nodes, where eight represents the instance augmentation proposed by [12]. Poppy samples d (number of decoders) xn solutions for each instance. Unlike baseline methods that enforee distinct initial actions, MP-ASIL does not impose different starting points during training and inference. This rollout strategy enables multiple behaviors freely explore the search space and universally applicable across all COPs.
Table 5 reports the Gap relative to LKH3 [70] and Time. From the table, we can see that MP-ASIL significantly outperforms neural methods both TSP 100 and CVRP 100. Surprisingly, MP-ASIL finds practically optimal solutions for TSP 100 in less than one minute. These results show that MP-ASIL can be effective across other COPs. Results for various out-o--distributiin VRP scenarios (cross-size, cross-distribution and cross-problem generalization) are presented in Appendix E.
6 Conclusion
In this work, we propose MP-ASIL, generic learning framework for job scheduling. MP-ASIL addresses several limitations in RL-based policy gradient methods by enabling multiple policies to autonomously learn diverse and specialized problem-solving strategies without external supervision. We also develop a training scheme to mitigate the suboptimality of self-teaching labels, a fundamental drawback of SIL, and enhance sample efficiency. Last but not least, MP -SSIL is agnostic to both network architectures and scheduling problems, allowing its benefits to be realized universally across various problem settings. Extensive experiments demonstrate that MP-ASIL achieves new ofate-of- art results on six scheduling problems and significantly outperforms previous neural solvers on routing tasks, highlighting its versatility and broadening the scope of current NCO methods.
Acknowledgments and Disclosure of Funding
This work was supported in part by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (RS-2024-0033417) RS- RRS-2025-022166400 and in part by the IITP (Institute of Information Communications Technology Planning Evaluation)-ITRC (Information Technology Research Center) grant funded by the Korea government (Ministry of Science and ICT) (ITP-2025- RS---S--222222 RRS2022-00033268)
10

---

References
[1] Jose M Framinan and Rubén Ruiz. Architecture of manufacturing scheduling systems: Literature review and integrated proposal. European Journal of Operational Research, 205(2):237-246, 2010.
[2] Matthew Veres and Medhat Moussa. Deep learning for intelligent transportation systems: A sur- vey of emerging trends. IEEE Transactions on Intelligent Transportation Systems, 21(8):1152-
3 3168, 2019.
[3] Hongzi Mao, Malte Schwarzkopf, Shaileshh Bojja Venkatakrishnan, Zili Meng, and Mohammad Alizadeh. Learning scheduling algorithms for data processing clusters. In Proceedings of the ACM Special Interest Group on Data Communication, pages 270-288, 2019.
[4] Wen- Wen-Yang Ku and J Christopher Beck. Mixed integer programming models for job shop scheduling: computational analysis. Computers & Operations Research, 73:165-173, 173, 2016.
[5] Teofilo F Gonzalez. Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall/CRC, 2007.
[6] Edmund K Burke, Michel Gendreau, Matthew Hyde, Graham Kendall, Gabriela Ochoa, Ender Özcan, and Rong Qu. Hyper-heuristic:: A survey of the state of the art. Journal of the Operational Research Society, 64(12): 2013.
[7] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in Neural Information Processing Systems, 28, 2015.
[8] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d' d'horizon. European Journal of Operational Research, 990(2):405-42)) 2021.
[9] Wouter Kool, Herke Van Hoof. and Max Welling. Attention, learn solve routing problems! arXiv preprint 1803 08475, 2018.
[10] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33, 2020.
[11] 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, 2020.
[12] Yao Kwon, Jinho Choo, Iljoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. Advances in Neural Informa- tion Processing Systems, 34, 2021.
[13] Behice Meltem Kayhan and Gokalp Yildiz. Reinforcement learning applications to machine scheduling problems: comprehensive literature review. Journal of Intelligent Manufacturing, 34(3):905-4 929, 2023.
[14] Anant Singh Jain and Sheik Meeran. Deterministic job-shop scheduling: Past, present and future. European Journal of Operational Research, 113(2)3900-334, 1999.
[15] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 12042-12049, 2021.
[16] Minsu Kim, Sanghyeok Choi, Hyconah Kim, Jiwoo Son, Jinkyoo Park, and Yoshua Ben- gio. Ant colony sampling with gflownets for combinatorial optimization. arXiv preprint arXiv:2403.07041 2024.
[17] Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-nco: Leveraging symmetricity for neural combinatorial optimization. Advances in Neural Information Processing Systems, 35, 2022.

---

[18] Yan Jin, Yuandong Ding, Xuanhao Pan, Kun He, Li Zhao, Tao Qin, Lei Song, and Jiang Bian. Pointerformer: Deep reinforeed multi- multi-pointer transformer for the traveling salesman problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 8132-8140, 2023.
[19] Michael L. Pinedo. Scheduling: Theory, Algorithms, and Systems. Springer, New York, NY, USA, 4th edition, 2012.
[20] Andrea Corsini, Angelo Porrello, Simone Calderara, and Mauro Dell' Amico. Self-labeling the job shop scheduling problem. Advances in Neural Information Processing Systems, 37:105528- 105551, 2024.
[21] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning, Machine Learning. 8:229-256, 1992.
[22] Marvin Minsky. Steps toward artificial intelligence. Proceedings of the IRE, 89(())8-33) 1961.
[23] Alican Dogan and Derya Birant. Machine learning and data mining in manufacturing. Expert Systems with Applications, 166:1 14060, 2021.
[24] 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.
[25] Cong Zhang, Zhiguang Cao, Wen Song. Yaoxin Wu, and Jie Zhang. Deep reinforcement learning guided improvement heuristic for job shop scheduling. arXiv preprint arXiv:2211.1093 2022.
[26] 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. arXiv preprint arXiv:2402. 7606,, 2024.
[27] Haoran Ye, Jiarui Wang, Zhiguang Cao, Helan Liang, and Yong Li. Deepaco: Neural- ceural-enhanced ant systems for combinatorial optimization. Advances Neural Information Processing Systems, 36, 2023.
[28] Hyeonah Kim, Sanghyeok Choi, Jiwoo Son, Jinkyoo Park, and Changhyun Kwon. Neural genetic search in discrete spaces. arXiv preprint arXiv:2502.10433, 2025.
[29] Junyoung Park, Sanjar Bakhtiyar, and Jinkyoo Park. Schedulenet: Learn solve multi-agent scheduling problems with reinforcement learning, arXiv preprint Stti:2200.03055.0 2021.
[30] Jun-Ho Lee and Hyun-Jung Kim. Reinforcement learning for robotic flow shop scheduling with processing time variations. International Journal of Production Research, (366)2234--236, 2022.
[31] Runqing Wang, Gang Wang, Jian Sun, Fang Deng, and Jie Chen. Flexible job shop scheduling via dual attention network- based reinforcement learning. IEEE Transactions on Neural Networks and Learning Systems, 35(3):309133102, 2023.
[32] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 30, 2017.
[33] 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, 19(2):1322-133) 2022.
[34] Ruyuan Pan, Xingye Dong, and Sheng Han. Solving permutation flowshop problem with deep reinforcement learning. In 2020 Prognostics and Health Management Conference (PHM- Besançon), pages 349-353. IEEE, 2020.
[35] Junyoung Park, Jachyeong Chun, Sang Hun Kim, Youngkook Kim, and Jinkyoo Park. Learning to schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning. International Journal of Production Research, (9(1))111))))))) (116:333603337,
2021.
12

---

[36] Zangir Iklassov, Dmitrii Medvedev, Ruben Solozabal Ochoa De Retana, and Martin Takac. On the study of curriculum learning for inferring dispatching policies on the job shop scheduling. International Joint Conference Artificial Intelligence, 2023.
[37] Daqiang Guo, Sichao Liu, Shiquan Ling, Mingxing Li, Yishuo Jiang, Ming Li, and George Q Huang. The marriage of operations research and reinforcement learning: Integration of neh into q-learning algorithm for the permutation flowshop scheduling problem. Expert Systems with Applications, 255: 124779, 2024.
[38] Zixiao Pan, Ling Wang, Jingjing Wang. and Jiawen Lu. Deep reinforcement learning based optimization algorithm for permutation flow-shop scheduling. IEEE Transactions Emerging Topics in Computational Intelligence, 7(4):983-999 2021.
[39] Kuo-Hao Ho, Jui-Yu Cheng, Ji-Han Wu, Fan Chiang, Yen-Chi Chen, Yuan- Yu Wu, and I- Chen Wu. Residual scheduling: A new reinforcement learning approach solving job shop scheduling problem. IEEE Access, 12:14703-14718, 2024.
[40] Sang-Hyun Cho, Woo-Jin Shin, Jeongsun Ahn, Sanghyun Joo, and Hyun-Jung Kim. Dy- namic crane scheduling with reinforcement learning for a steel coil warchouse. In 2024 IEEE International Conference on Robotics and Automation (ICRA), pages 16545-16555 IEEE, 2024.
[41] Sang-Hyun Cho, Hyun-Jung Kim, and Lars Mönch. Reinforcement learning for unrelated parallel machine scheduling with release dates, setup times, and machine eligibility. In 2024 Winter Simulation Conference (WSC), pages 1773-1784. IEEE, 2024.
[42] Longkang Li, Siyuan Liang, Zihao Zhu, Chris Ding. Hongyuan Zha, and Baoyuan Wu. Learning to optimize permutation flow shop scheduling via graph-based imitation learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 20185-20193, 2024.
[43] Woo-Jin Shin, Sang- Sang-Wook Lee, Jun-Ho Lee, Min-Ho Song, and Hyun-Jung Kim. Scheduling of stellmaking-continuuur casting process by integrating deep neural networks with mixed integer programming. International Journal of Production Research, pages 1-22, 2024.
[44] Je-Hun Lee and Hyun-Jung Kim. Graph-based imitation learning for real-time job shop dispatcher. IEEE Transactions on Automation Science and Engineering, 2024.
[45] Jonathan Pirnay and Dominik G Grimm. Self-improvement for neural combinatorial opti- mization: Sample without replacement, but improvement. arXiv preprint arXiv:2403.15180 2024.
[46] Minsu Kim, Jinkyoo Park, et al. Learning collaborative policies to solve np-hard routing problems. Advances in Neural Information Processing Systems, 34, 2021.
[47] Dinghuai Zhang, Nikolay Malkin, Zhen Liu, Alexandra Volokhova, Aaron Courville, and Yoshua Bengio. Generative flow networks for discrete probabilistic modeling. In International Conference Machine Learning, pages 26412-26428. PMLR, 2022.
[48] Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron C Courville, Yoshua Bengio, and Ling Pan. Let the flows tell: Solving graph combinatorial problems with gflownets. Advances in Neural Information Processing Systems, 36, 2023.
[49] Hyeonah Kim, Minsu Kim, Sanghyeok Choi, and Jinkyoo Park. Genetic-guided gflownets for sample efficient molecular optimization. arXiv preprint arXiv:2402.05961 2024.
[50] Ni Zhang, Jingfeng Yang, Zhiguang Cao, and Xu Chi. Adversarial generative flow network for solving vehicle routing problems. arXiv preprint urXiv:2503.01931, 2025.
[51] Jinho Choo, Yeong-Dae Kwon, Jihoon Kim, Jeongwoo Jae, André Hottung, Kevin Tierney, and Youngjune Gwon, Simulation-guidee guided beam search for neural combinatorial optimization. Advances in Neural Information Processing Systems, 35, 2022.
[52] André Hottung, Yeong-Dae Kwon, and Kevin Tierney. Efficient active search for combinatorial optimization problems. arXiv preprint 21X5v:2006..5126, 2021.
13

---

[53] Hyun-Jung Kim and Jun-Ho Lee. Deep reinforcement learning with a look-ahead search for robotic cell scheduling. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 54(1):622-633) 633, 2023.
[54] Nathan Grinsztajn, Daniel Furelos-Blange Shikha Surana, Clément Bonnet, and Tom Barrett. Winner takes all: Training performant rl populations for combinatorial optimization. Advances in Neural Information Processing Systems, 36, 2023.
[55] Felix Chalumeau, Shikha Surana, Clément Bonnet, Nathan Grinsztajn, Arnu Pretorius, Alexan- dre Laterre, and Tom Barrett. Combinatorial optimization with policy adaptation using latent space search. Advances in Neural Information Processing Systems, 36, 2023.
[56] André Hottung, Mridul Mahajan, and Kevin Tiemne. Polynet: Learning diverse solution strategies for neural combinatorial optimization. arXiv preprint arXiv:2402. 0004402224444 /4048, 2024.
[57] Ronald Lewis Graham, Eugene Leighton Lawler, Jan Karel Lenstra, and AHG Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: survey. In Annals of Discrete Mathematics, volume 5, pages 287-326. Elsevier, 1979.
[58] Saurabh Kumar, Aviral Kumar, Sergey Levine, and Chelsea Finn. One solution not all you need: Few-shot extrapolation via structured maxent rl. Advances in Neural Information Processing Systems, 33, 2020.
[59] Samir W Mahfoud. Niching methods for genetic algorithms. University of Illinois at Urbana- Champaign, 1995.
[60] Yang-Kuei I Lin and Feng- Yu Hsieh. Unrelated parallel machine scheduling with setup times and ready times. International Journal of Production Research, 1204411200-1214, 2014.
[61] IBM Corp. IBM ILOG CPLEX Optimization Studio. V20.1: User's Manual for CPLEX, 2020.
[62] Cengiz Kahraman, Orhan Engin, Ihsan Kaya, and Mustafa Kerim Yilmaz. An application of effective genetic algorithms for solving hybrid flow shop scheduling problems. International Journal of Computational Intelligence Systems, 1())134-147, 2008
[63] Manas Ranjan Singh and SS Mahapatra. A swarm optimization approach for flexible flow shop scheduling with multiprocessor tasks. The International Journal of Advanced Manufacturing Technology, 62:267-277, 2012.
[64] Helena Ramalhinho Lourenço, Olivier C Martin, and Thomas Stützle. Iterated local search: Framework and applications. Handbook of Metaheuristics, pages 129-168, 2019.
[65] Rubén Ruiz, Quan-Ke Pan, and Bahman Naderi. Iterated greedy methods for the distributed permutation flowshop scheduling problem. Omega, 83:213-222, 2019.
[66] Meenakshi Sharma, Manisha Sharma, and Sameer Sharma. An improved neh heuristic to minmmize makespan for flow shop scheduling problems. Decision Science Letters, 10(3):311- 322, 2021.
[67] Laurent Perron and Vincent Furnon. Or-tools. URL: htt.::ttttp:///eealpprrr...ogg/ com/ optimization.
[68] Eric Taillard. Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2):278-285, 1993.
[69] Kensen Shi, David Bieber, and Charles Sutton. Incremental sampling without replacement for sequence models. In International Conference Machine Learning, pages 8785-8795. PMLR, 2020.
[70] Keld Helsgaun. An extension of the lin lin-krmighannhellgann tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12:966-980, 2017.
[71] Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. Advances in Neural Information Processing Systems, 36, 2023.
14

---

[72] Darko Drakulic, Sofia Michel, Florian Mai. Arnaud Sors, and Jean-Mare Andreoli. Bq-nco: Bisimulation quotienting for efficient neural combinatorial optimization. Advances in Neural Information Processing Systems, 36, 2024.
[73] 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): (9(2):1600-661 2022.
[74] Dailin Huang, Hong Zhao, Jie Cao. Kangping Chen, and Lijun Zhang. Optimizing the flexible job shop scheduling problem via deep reinforcement learning with mean multichannel graph attention. Applied Soft Computing, page 113128, 2025.
[75] S Lawrence. Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques. GSIA, Carnegie Mellon University, 1984.
[76] Paolo Brandimarte. Routing and scheduling in flexible job shop by tabu search, Annals of Operations Research, 41() 153-13,,, 1993.
[77] Johann Hurink, Bernd Jurisch, and Monika Thole. Tabu search for the job-shop scheduling 15(4):205-21) 1994.
problem with multi purptse machines. Operations-Reseanie
[78] Roland Braune, Frank Benda, Karl F Doerner, and Richard F Hart. A genetic program- ming learning approach to generate dispatching rules for flexible shop scheduling problems. International Journal of Production Economics, 243: 108310 2022.
[79] Igor G Smit, Yaoxin Wu, Pavel Troubil, Yingqian Zhang, and Wim PM Nuijten. Neural combinatorial optimization for stochastic flexible job shop scheduling problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages (66678-2668) 2025.
[80] Nikolaus Hansen and Andreas Ostermeier. Completely derandomized self-adaptation in evolu- tion strategies. Evolutionary Computation, 9(2):159-13)) 2001.
[81] Han Fang, Zhihao Song. Paul Weng, and Yutong Ban. Invit: A generalizable routing problem solver with invariant nested view transformer. arXiv preprint 2xX 2024.
[82] Jianan Zhou, Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Towards omni-generalizabbe neural methods for vehicle routing problems. In International Conference Machine Learning, pages 42769-42789, PMLR, 2023.
[83] Chengrui Gao. Haopu Shang, Ke Xue, Dong Li, and Chao Qian. Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy. arXiv preprint arXiv:23008 /4/04, 2023.
[84] Fei Liu, Xi Lin, Zhenkun Wang, Qingfu Zhang, Tong Xialiang, and Mingxuan Yuan. Multi-task learning for routing problem with cross poosseproblem zero-shot generalization. In Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 1898 1908.1908. 2024.
[85] Thibaut Vidal. Hybrid genetic search for the evrp: Open-source implementation and swap* neighborhood. Computers Operations Research, 140:105643. 2022.
[86] Marcel Blöcher, Nils Nedderhut, Pavel Chuprikov, Ramin Khalili, Patrick Eugster, and Lin Wang. Train once apply anywhere: Effective scheduling for network function chains running on fumes. In JEEE INFOCOM 2024-IEES Conference on Computer Communications, pages 661-670. IEEE, 2024.
15

---

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:
The abstract and introduction clearly state our main contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of our work in Appendix G.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in 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 the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
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: [NA].
16

---

Justification:
The paper does not include theoretical results.
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 be 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 provide all implementation details in Appendices C and 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 a 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) If 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 reproducibility. 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?
17

---

Answer: [NA]
Justification:
This paper uses public datasets and benchmarks.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" 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 run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //nips.cc/ppp wttpccccppppcccaeeccccccccccccct gwwp//uwi/////gge//ee /Coeee///mmemmmiiaa wwwiiissinooooooooooooo
for more details.
The authors should provide instructions on data access and preparation, including how 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. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information 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:
We provide all details regarding experiments in Appendices C and 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
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: We mainly provide average values.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
18

---

It 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 enrors 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 error 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 in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide details computational resources.
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, or 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 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 https http://urrpss..pppppiiicoo/////e
Answer: [Yes]
Justification:
We have checked the paper according to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration 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:
We discuss the broader impact of this work in Appendix H.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or 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.
The conference expects that many papers will be foundational research and not tied to 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 improvement in the quality of generative models could be used to
19

---

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 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 is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The 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. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We clearly state the source and license of original code, data, and models used in this work.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.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, paperswithcode wwwccoo//////oo datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
20

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We use well-known public datasets. We will make our project code using pytorch publicly available.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing 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 as details about compensation (if any)?
Answer: [NA]
Justification: This work does not involve crowdsourcing experiments and human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Including this information 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This work does not involve crowdsourcing experiments and human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on 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 the NeurIPS 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
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact core methodology, scientific rigorousness, originality of the research, declaration is not required.
21

---

Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, and non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not
involve LLMs as any important, original, non non-standard components.
Please refer to our LLM policy (https: /ttp///eesppp/eeeee eeeeurpps.cc/Confeeeeecee. oc//onnferecccc//225//MM for what should or should not be described.
22

---

Appendix
Contents
A Job Scheduling Problems
24
A.1 Machine Environments a
24
A.2 Constraints 3
24
A.3 Objective Functions 7
25
B Multi-Policy Representation
25
B.1 Implementation of Latent Conditioned Policies
25
B.2 Why We Use Latent Variables to Represent Multiple Policies
27
B.3 The Effect of Latent Distributions
27
C Benchmark Problems
28
C.1 Single Machine Scheduling Problem
28
C.2 Unrelated Parallel Machine Scheduling Problem
28
C.3 Permutation Flow Shop Scheduling Problem
29
C.4 Flexible Flow Shop Scheduling Problem
29
C.5 Job Shop Scheduling Problem
30
C.6 Flexible Job Shop Scheduling Problem
30
D Additional Experiments
30
D.1 Validation curves
30
D.2 Computation Time for PFSP and JSSP
D.3 Detailed UPMSP Results
32
D.4 Experiment Results PESP Using Synthetic Datasets
34
D.5 Experiment Results on JSSP Using Lawrence's Benchmark
34
D.6 Experiment Results on JSSP Using Synthetic Datasets
35
D.7 Experiment Results on FISSP
35
D.8 Ablation Studies
37
D.9 Performance Landscape Visualization
39
D.10 Policy Latent Space Search Inference Time
39
E Vehicle Routing Problems...
40
E.1 Cross-size Generalization
40
E.2 Cross-distribution Generalization
40
E.3 Cross-problem Generalization
41
F Training Hyperparameters
44
G Limitation and Future Work
47
H Broader Impact
47
Licenses
47
23

---

A Job Scheduling Problems
JSP can be described by three-field notation a [57]. The a field specifies the machine environment, the 3 field represents constraints, and the field defines the objective function. Here, we provide representative examples of each field considered in our work. Figures 6, 7, and 8 provide illustrative examples of each field.
Job
Machine
Jobb-machine route
M1
DOO
DOO PODD
Single machine (1)
Parallel machine (Rm)
Flow shop (Fm)
Jop shop (/m)
Machine environments (a)
Figure Illustrative examples machine environments (ar).
A.1 Machine Environments
Single Machine (1). There is a single machine, representing the simplest case machine environ- ments. In this environment, each job j consists of single operation.
Parallel Machine (Pm) / Unrelated Parallel Machine (Rm). There are [M] parallel machines, and each job j is processed by exactly one of these machines. If the processing time job j varies across different machines, this environment is known as the Unrelated Parallel Machine (Rm). Each job j consists of a single operation.
Flow Shop (Fm). There |M| machines in series, and each job must be processed sequentially on all machines following the same fixed route from machine to machine [.M.. there are [Q] sequential stages, where Q is set of stages, each equipped with parallel machines, the resulting environment is known as the Flexible Flow Shop (FFc). In this case, jobs must sequentially pass through each stage, from stage 1 to stage 1Q), being processed by exactly machine per stage. Each processing step at a machine or stage represents an operation.
Job Shop (Jm). There are I machines, and each job j consists of sequence operations that must be processed in predefined, job-specific order. Each operation requires processing on one machine, and when an operation can processed on one of several alternative machines, the problem setting is referred to as the Flexible Job Shop Jc....
Jobs
Machines
Job-machine route
Not available
M1
t-12
M1
O
O
O
15
Py32
Precedence (prec)
Machine eligibility (M,)
Ready (r))
Setup (s,,)
Permutation (prmu)
Constraints (Ø)
Figure 7: Illustrative examples of constraints (3).
A.2 Constraints 3
Precedence (prec). The precedence constraints enforce that one or more operations (or jobs) must finish before another operation (or job) start.

---

Machine Eligibility (M,). Only subset of the machines M, S M can process job j.
Ready Time (ry). Each job j cannot start processing before its ready time ry-
Sequence Dependent Setup Time (8iz). Switching from job to job incurs setup time. If the setup time between jobs and depends on machine k, we denote as 8igk-
Permutation (prmu). The permutation constraint requires that the job processing order determined at the first machine remains unchanged throughout all machines flow shop environment.
Solution
Solution
M2
M1
M1
J3
S7
music 4,0)
Makespan: max G = 37
Total Tardiness: 2) T/ max(G) 0))
Objective functions (r)
Figure 8: Illustrative examples of objective funnctions (7).
A.3 Objective Functions (7)
Makespan (Cmaz). The makespan, defined as maxx(Ci,.... Cn), where Cj is the completion time of job j. denotes the completion time of the last job processed.
Total Tardiness TT), The total tardiness, defined as ΣT, = -T max(C; - dy, 0), denotes the sum of job completion delays relative to their due dates dj. When each job j has weight wj,, the objective function becomes Σ w.
B Multi-Policy Representation
B.1 Implementation Latent Conditioned Policies
Overview. Neural dispatcher architectures generally fall into two main categories: Heavy Encoder Light Decoder (HELD) [9, 10, 12], and Light Encoder Heavy Decoder (LEHD) [11, 71, 72]. HELD- based models employ a computationally expensive encoder once to generate static hidden embeddings, subsequently constructing solutions sequentially using a lightweight decoder. contrast, LEHD- based models dynamically recompute hidden embeddings at each decision step using multiple decoder layers.
Figure 9 illustrates how latent conditioned policies are applicable to the architectures above. Following previous work [55], HELD-based models concatenate the latent variables with the query, key, and value inputs of the Multi-Head Attention (MHA) layer. LEHD-basce models concatenate the latent variables with the final hidden embeddings before computing action probabilities through a Multi- Layer Perceptron (MLP). This means that, regardless of the underlying architecture, multiple policies can be easily implemented by conditioning the decision makinn layer's input embeddings on latent variables. The latent variables are sampled once at the start of the solution rollout and remain unchanged during the solution construction. Notably, within each policy, an identical latent variable is concatenated to all hidden embeddings. In this work, we use LEHDD-based models for SMSP, UPMSP, JSSP, and FISSP. In contrast, PFSP and FFSP utilize HEL.D-based models. the following sections, detail how latent conditioned policies are implemented within each architecture.
The encoder generates hidden embeddings for the input instance s. Initially, raw operation features {aı]ū E (1,..., (OI}) E RROO) xd, are projected into d, dimeensiona embeddings via a linear layer. These embeddings (0) (n (1...., |O}}} e R(0xx are iteratively
HELD.
updated L times by the update function F to generate set of final hidden embeddings H
25

---

Updated node embeddings 210004
MLP & Softmax
Single-Head Attention
A
X [O|
X |0|
Update Function
Muldi-Head Attention Layer
Update Function
Linear Projection
Linear projection
K
Linear Projection
FAI
AE
X E [
X, E R.
(a) HELD
(b)
Figure 9: Illustrations of applying the latent conditioned policies into (a) HELD and (b) LEHD.
(1 E (I,...,/01]) (01}) e Rlo]xxd, F can designed using any neural network model (e.g., GNN or Transformer).
The decoder sequentially constructs solution by leveraging the final hidden embeddings, which are the output of the encoder. At each decoding step f, the decoder receives hidden embeddings H, (h14)) A.) R.AA| xdd, where A represents the set of feasible operations at step I, alongside a context vector Iy indicating the current state. To integrate hidden embedding information into the context vector, HELD employs MHA to update the context vector. In this process, latent variables are concatenated with the query, key, and value inputs of the MHA module. The context vector is updated follows:
9: W, W,Coonct(hf,22))
K, WyCoonca(Hee 2),
Vi W. WoCoonct(HHe,)) 2),
(5)
4 MHA (4t, Kr, Vt).
(6)
where Wg, Wa W, E g(4,+d))xo are learnable model weights. At the final stage, single-head attention computes a conditional action distribution at step t. The action probability n, for operation i Ad is computed by:
:. Softmax (C- tanh
(ne') ( K. Vdh
));
where the clipping parameter and tanh is the hyperbolic tangent function.
LEHD. The LEHD-based models recompute hidden embeddings at every step i, effectively cap- turing dynamic relationships. At step t, the raw operation features X, = {z,li E Ar) E Ild, projected into da di-dimensional hidden embeddings via a linear layer. These embeddings H! = (h1") i A.) E |RAx/xds are iteratively updated times by the update function F to generate set of final hidden embeddings (1.
At step f, conditional action distribution computed via an MLP using the final hidden embeddings (2) In this process, the latent variables are concatenated to the final node embeddings. The action probability n, for operation A, is computed by:
R; Softmax (MLP/ConcCCCC( ,2)))
(8)
26

---

(a) SMSP
(b) UPMSP
(c) PFSP
(d) FFSP
(a) JSSP
40-
3m
Single
Figure 10:
Number of parameters for each strategy. Here, Single denotes a single policy, LCP indicates latent conditioned policies, MD) represents multi-decoder architecture, and k denotes the number of policies.
B.2
Why We Use Latent Variables to Represent Multiple Policies
Early approaches for representing multiple policies often rely on multi-decoder models without parameter sharing [15, 54]. However, as illustrated in Figure 10, this design leads to substantial parameter growth with the number of policies, limiting scalability and flexibility. In contrast, latent conditioned policies add fixed number of parameters, regardless of the number of policies. This property enables efficient and scalable representation of multiple policies, which provides the rationale for our design choice.
B.3 The Effect of Latent Distributions
The latent variable 2, indexing different policies, can affect model performance based on its distribu- tion Z. To identify an effective prior, evaluate models trained under three latent distributions: (1) 21 =--1, 1)16; (2) Z2, a joint distribution combining (-11, 1) with an 8 3-dimensional categorical (one-hot) distribution: (3) Zz. joint distribution combining (1(-1, 1 with 12-dimensional cate- gorical (one-hot) distribution. We do not consider 16-dimensional categorical (one-hot) distribution because can only generate 16 policies.
Figure 11 compares performances across these prior distributions on the TA benchmarks. For reference, also include the results of SLIM and the REINFORCE with shared baseline as representative single policy approaches. From the figure, we can observe that Z3 shows robust and strong zero-shot performance. Therefore, we adopt Z3 as the default prior for all problems except UPMSP, which uses lower-dimensional hidden embedding (d, = 64). For UPMSP, we adopt a joint prior combining u1-1, 1)a with 6-dimensional categorical distribution. However, all prior distributions consistently outperform single policy approaches. This finding underscores the robustness and generalizability of our approach, with its effectiveness stemming from the fundamental model optimization mechanism rather than fine-tuning the latent space.
(a) PFSP
(b) JSSP
3.0
Average Gap (%
2.5
9.0
8.5
2.0
1.74
1.68
7.8
2.5
7.53
7.41
2.0
7.0
SUM REINFORCE
SUM REINFORCE
Methods
Methods
Figure 11: The effect of latent distributions.
27

---

C Benchmark Problems
In this section, we formally define six benchmark problems, following the notations introduced in Sections 3 and Appendix A. We also provide details the training and inference settings. As mentioned Section 5, learning-based methods for JSPs have evolved with specialized network architectures and algorithms tailored each problem variant. Therefore, due the current absence of foundation models, we implement MP-ASIL using different backbone models for each problem type. Naturally, comparisons conducted against distinct baselines specific to each problem.
C.1 Single Machine Scheduling Problem (I)E))
The Single Machine Scheduling Problem (SMSP) is one of the most fundamental scheduling problems in which a set of jobs I must be processed on single machine. Each job j E J has processing time Pj. due date dj. and weight wy. The optimization objective is to find schedule that minimizes the total weighted tardiness Ew,T,.
Definition.
Model Architecture. Due to the absence of existing neural constructive solvers, develop maanformer-based solver following the BQ-NCO architecture [72]. In our implementation, nodes represent jobs defined by three features: Pj. Wj, and remaining deadline slack (dj ee), where er the elapsed time at step I. The processes for updating hidden embeddings and making decisions follow the approach described in Appendix B.1.
Training Instances. Following previous work [27], we randomly generate training instances as follows: P5 ~ (0, 1), wi ~ (0, 1), and dj ~ (0, (J]. where represents a continuous uniform distribution. We train our model using instances with [T] 50.
Test Instances. For evaluation, we use 100 SMSP instances for each problem size | 50, 100, and 500 from [27]. The test instances follow the same distribution used for generating the training instances.
Baseline Algorithms. We compare MP-AST ASIL with (1) Handcrafted Heuristies: Earliest Due Date (EDD) and Ant Colony Optimization (ACO) [27]: (2) Hybrid Methods: DeepACO [27] and GFACS [16].
C.2 Unrelated Parallel Machine Scheduling Problem (Rm]sijk- Mj, Ty [u)TT;
Definition. The Unrelated Parallel Machine Scheduling Problem (UPMSP) a generalized parallel machine scheduling problem, requiring the assignment and sequencing of a set of jobs J onto set of machines M. Each job j E T must be processed on exactly one machine selected from its eligible machine set M, S .M with processing time Рソж machine k E Mý. Each job has weight w due date d,. and ready time ry. Additionally, each machine M requires setup time Sijk. The optimization objective is to find a schedule that minimizes the total weighted tardiness EmyT].
Model Architecture. We use the LEHD-based architecture introduced by Cho et al. [41]. We refer readers to the original paper for detailed architectural specifications and features.
Training Instances. Following previous work [41], we randomly generate training instances as Pıı [,, Uniform (1, 2,..., (9}), w/ (0, 1). Sisk ~ M
follows: |M,l Uniform (1,,,, [M[H).
Uniform( (0, 1,... 10}). and ry Uniform( (0, 1,..., .. [6/2]}), where [MP k=1 Σ ソ Pjk
and Uniform() denotes a discrete uniform distribution. Due dates are sampled as d, ~ ry + Uniform/ (f m0, (p - ry) (1 - R//2]]).... max(0, [ (5)
- T R/2) D))
using tightness 7 and range R parameters, which range from 0.2 to 1.0 in steps of 0.2. During training.
uniformly sample T and R. We train model using instances with [J] |M| 25 3.
Test Instances. For evaluation, we use 500 UPMSP instances for each problem size [J] M 50 x 3, 50 x 6, and 100 from [41]. The test instances follow the same distribution used for generating the training instances.
28

---

Baseline Algorithms. We compare MP-ASIL with (1) Handcrafted Heuristics: EDD and ATCSR RM [60]] (2) Neural Constructive Heuristic: Cho et al. [41].
C.3 Permutation Flow Shop Scheduling Problem (Empprmul Cmaa)
Definition. The Permutation Flow shop Scheduling Problem (PFSP) is a widely studied variant of the flow shop scheduling problem, where set of jobs J is processed sequence of machines. The processing order determined at the first machine remains unchanged across all subsequent machines. Each job j E I has processing time Pjk each machine & M.. The optimization objective is to find a schedule that minimizes the makespan Cmaz-
Model Architecture. We use the HELD-based architecture based on MatNet [12]. The model takes input a P P matrix, with each element representing processing time Pjk- In implementation, the context vector by at step & is defined as:
h W. Concat (hv-1, hh") ht)
where W. E 3d, Xdy is the learnable model weight, h4-1 represents the embedding of the last selected job, hy denotes the embedding of unselected jobs up step i, and hm is obtained by concatenating all machine embeddings and projecting to a dy-ddimeniional vector. At step = 1, we learnable start-token embedding h
Training Instances. We randomly sample Pys: from Uniform((1.. 21...rrm .9)).. We train separate models for two problem sizes: instances with [J] x [M] =0 and 10.
Test Instances. For evaluation, we use the TA benchmark [68]. Each problem size consists of 10 instances. The benchmark instances follow the same distribution used for generating the training instances. For problems with five machines, we employ the model trained on 20x5 instances, while for problems with ten machines, we use the model trained on 20x 10 instances.
Beseline Algorithms. We compare MP-ASIL with (1) Handcrafted Heuristies: Iterated Local Search (ILS) [64], Iterated Greedy Algorithm (IGA) [65], and [66]; (2) Neural Constructive Heuristics: Q-Learning [37], IL [42], and PFSPNet [38].
Ham (NEH) algorithm
C.4 Flexible Flow Shop Scheduling Problem (FFellCmaz)
The Flexible Flow shop Scheduling Problem (FFSP) involves scheduling a set of jobs J through multiple sequential stages Q. Each stage q E Q comprises unrelated parallel machines Mg CM, and each job must be processed by exactly one machine at every stage. Each job j E J has processing time Pigk machine & M, at stage q E Q. The optimization objective is find a schedule that minimizes the makespan Cmaz-
Definition.
Model Architecture. We use the HELD-based architecture introduced by PolyNet [56]. We refer readers the original paper for detailed architectural specifications and features.
[Q] 3, where each stage consists of [Myl = 4 machine. Processing times are sampled as Pjgk ~ Uniform {2, 3, ......,9))) We train
Training Instances. Following prior work [12],
separate models for three problem sizes: instances with [J x = 12, 50x 12, and 100x 12.
Test Instances. For evaluation, we use 1,000 FFSP instances for each problem size [ [M] 20x 12, 50x 12, and 100x 12 from [12]. The test instances follow the same distribution used for generating the training instances.
Baseline Algorithms. We compare -SIASIL with (1) Exact Solver: CPLEX [61]; (2) Hand-
crafted Heuristics: Shortest Processing Time (SPT), Genetic Algorithm (GA) [62], and Particle
Swarm Optimization (PSO) [63]; (3) Neural Constructive Heuristics: MatNer [12] and PolyNet
[56].
29

---

C.5 Job Shop Scheduling Problem (JmllCmaz)
Definition. The Job Shop Scheduling Problem (JSSP) is well-known JSP that has attracted considerable attention from the NCO community. A JSSP instance consists of set of jobs J and set of machines M. Each job j E I comprises my operations that must be processed in predefined order. Each operation O5: (1 S S m,) can only be processed on specific machine with processing time Pja- The optimization objective is to find a schedule that minimizes the makespan Cmar.
Model Architecture. We use the LEHD-based architecture introduced by SLIM [20]. We refer readers to the original paper for detailed architectural specifications and features.
Training Instances. Following [20], we use 5,000 problem instances for each problem size: [J] x M|=10x 10. 10x10, 15, x0 10, 20 15, and 20x20. Processing times are sampled as Pji
Test Instances. For evaluation, we use the TA benchmark [68]. Each problem size consists of 10 instances. The benchmark instances follow the same distribution used for generating the training instances.
Baseline Algorithms. We compare MP-ASIL with (1) Exact Solvers: Gurobi and OR-Tools; (2) Neural Constructive Heuristies: L2D [11], SN [29], RASCL [36], SI GD [45], and SLIM [45]; (3)
Neural Improvement Heuristics: L2S [25] and TBGAT [26].
C.6 Flexible Job Shop Scheduling Problem (FJcl(CCmzz)
Definition.
The Flexible Job Shop Scheduling Problem (FISSP) is generalized version of the
ISSP, where each operation can be processed on one the several compatible machines My S M with processing time Pjik machine k E MMj. The optimization objective is to find schedule that minimizes the makespan Cmaz-
Model Architecture. We use the LEHD- based architecture introduced by DANIEL [31]. We refer readers to the original paper for detailed architectural specifications and features.
Training Instances. Following [31], we randomly sample [Mjül from (1, [M) and Pj: from Uniform( (1,, 2,.... 20)). Pijk is sampled from Uniform( (maxx(1, [0.8 x
Pye 1y...... min(20, [1.2 x pys 1))))) Each job has m, Uniform 5, 6}) operations. We train our model using instances with [J] x [M| 10 x 5.
Test Instances. For evaluation, use 100 instances for each problem size |J] | 10x5, 20x5, 15x 10, 20x 10, 30x 10, and 40x 10 from [31].
Baseline Algorithms. We compare MP-ASIL with (1) Exact Solver: OR-Tools; (2) Handcrafted Heuristic: First First Out (FIFO), Most Operations Remaining (MOR), SPT, and MWKR; (3) Neural Constructive Heuristics: HGNN [73), MCGA [74], RS [39], and DANIEL [31].
D Additional Experiments
In this section, we present supplementary experimental results and analyses. Since MP ASIL can generate different results based on sampled policies, report the averaged results of three trials.
D.1 Validation Curves
Figure 12 shows the validation curves for MP-ASIL. For comparison, we also report validation results from state-of- tfe-the-art methods, including the REINFORCE with shared baseline [17], SLIM [20], and Poppy [54]. The validation sets consist 100 instances each for SMSP, UPMSP, PFSP, and FFSP, and 600 instances for JSSP, all sampled from the same distribution as the training instances. Validation is performed every epoch for ISSP and every 10 epochs for other problems. We publicly available MatNet [12]
train each model from scratch except for FFSP, for which
30

---

(a) SMSP 50
(b) UPMSP 25x3
(c) PFSP 20x5
(d) PFSP 20x10
Objective value
1250
0.2200-
16x
450
2.4x
250x
1610
10x
1245
5.5x
0.2175-
400
2.1x
200x
1600
2.1x
0.2150-
10x
8.7x
1240
1.6X
350
1590
50
100
500
1000
500
1000
500
1000
Objective value
(e) FFSP 20x12
51.6
( FFSP 50x12
91.6
g FFSP 100x12
(h) JSSP
27.4-
2610
91.4
27.2
51.4
2x6x
91.2
19k
2600
27.0-
51.2
91.0
3,2x
2.8
2590
26.8
90.8
50 Epochs
100
100
100 Epochs
200
10 Epochs
20
Epochs
Poppy
REINFORCE
SLIM
MP-ASIL
Figure 12: Validation curves.
checkpoints to initialize our policy network.' 3 From the figure, we can see that MP-ASIL achieves performance comparable all baselines using approximately 1.3x to 250x fewer epochs.
D.2
Computation Time for PFSP and JSSP
Due to space limitations, we report only the Gap in Tables 2 and 3. In this section, we additionally provide Time in Tables 6 and 7. Time results for PFSP reported only when available from the original papers or when the authors made code available.
Table 6: Inference time for PFSP. Symbols follow definitions provided in Table 1.
20x5
20x 10
50x5
50x 10
100x5
100x 10 .
200x 10
Method
Type
Time |
Time |
Time
Time |
Time
Time
Time J
IL. [64]
Hcuristics
(0.1s)
(0.2s)
(0.2s)
(0.4s)
(0.3s)
(0.9s)
(1.9s)
IGA [65]
Hcuristics
(0.6s)
(1.15)
(3.78)
(7.0s)
(14.9s)
(28.6s)
(1.9m)
NEH [66]
Heuristics
(0.1s)
(0.1s)
(0.6s)
(L.ls)
(4.4s)
(8.6s)
(1.1m)
IL (G) [42]
NCH
(0.3s)
(0.36)
(0.4s)
(0.4s)
(0.7s)
(0.7s)
(1.2s)
MP-ASIL (k=128)
NCH
(0.2s)
(0.2s)
(0.2s)
(0.2s)
(0.3s)
(0.3s)
(0.8s)
Table 7: Inference time for JSSP. Symbols follow definitions provided in Table
15x15
20x
20x20
15
30x20
50x
50x20
100x20
Method
Type
Time
Time
Time 1
Time
Time
Time
Time $
Time
Gurobi (3600s)* [20]
Exact
(10b)
(10b)
(10h)
(10h)
(10h)
(10h)
(10h)
(10h)
OR-Tools (3600s)* [67]
Exact
(77m)
(8h)
(10h)
(10h)
(10h)
(10h)
(10h)
(10h)
L2D (G)* [1]]
NCH
(46)
(68)
(7s)
(10s)
(14s)
(18s)
(30s)
(1.6m)
SN (G)* [29]
NCH
(35%)
(1.1m)
(1.8m)
(2.9m)
(4.7m)
(8.8m)
(16.0m)
(1.2h)
RASCL (G)* [36]
NCH
(8s)
(11s)
(148)
(15s)
(17s)
(28s)
(396)
(1.6m)
RS (G)* [39]
NCH
(5s)
(8s)
(96)
(19))
(22s)
(53s)
(1.2m)
(4.6m)
L2D (S=128)* [1]]
(6.8m)
(9.0m)
(13.1m)
(15.6m)
(26.3m)
(35.9m)
(1.0h)
(3.4h)
GD (G)* [45]
NCH
(10s)
(1
(11s)
(12s)
(15s)
(248)
(396)
(5.0m)
SLIM (S=512)*1 [20]
NCH
(3s)
(58)
(7s)
(9s)
(12s)
(22s)
(29s)
(1.5m)
L2S-500* [25]
NIH
(1.6m)
(1.7m)
(1.8m)
m2.
(2.3m)
(2.7m)
(3.8m)
(8.4m)
TBGAT-500 [26]
NIH
(2.1m)
(2.4m)
(2.9m)
(2.9m)
(3.2m)
(4.0m)
(4.1m)
(7.0m)
MP-ASIL (I=512)
NCH
(3s)
(5s)
(7s)
(9s)
(12s)
(22s)
(29s)
(1.5m)
31

---

D.3 Detailed UPMSP Results
As detailed in Appendix C.2, the distribution of d, in UPMSP instances depends on the parameters T' and R. While the main paper presents average results due to space limitations, here we report detailed results for each parameter combination, evaluating 20 instances per configuration.
32

---

Table 8: Experiment results UPMSP across all parameter combinations. Bold: Best Obj. Other
symbols follow definitions provided in Table 1.
3
M
T
R
||
EDD
ATCSR Rm [60]
Cho et al. (S=6) f [41]]
MP-ASIL (k=6)
0.3
0.2
03
02
917.72
856.02
37-35
12.92
117.92 05.
$4 76 26,82
0.3
0.8
0.6
672
917.8
19.85
16.
47 96
30.7 7.14
14
0.2
1.0
384.16
22.18
4.72
0.4
0.2
1233.29
228
254 75
186.66
0.4
044
1506.45
134,88
209.42
179.57
0.4
0.6
1489.27
194 54.58
157.2
110.32
0.4
0.8
1680,08
186.37
140,40
0.4
1283.9 1.0
164.41
160.6
137,93
2405
0.6
0.4
$28.3
491.25
0.6
0.6
3184 25
759
621 97
616.45
0.6
0.8
2963.1
608.87
560.29
$79.01
0.6
1.0
2502.97
$42.00
484.42
459.23
0.8
0.2
4078.04 04
1456.9
1434.37
1356.45
3750
179.15
101155
946.71
0.8
3381
1,26
985.23
875.89
842.48
50
1.0
0.2
SX71 35
2766.78
2600.2
2517.76
1.0
F0
$326 36
94
2047 97
2019.69
TK50
4893.06
19808T
1325.51
1338.26
Average
2836.80
876.97
784.43
751.89
[
IM]
T
R
EDD
ATCSR Rm [60]
Cho al. (S=6) f [41]
MP-ASIL (k=6)
0.2
0.2
96.49
0.63
9.44
3.65 1.33
0.2
0.3
56,34
0.69
8.3 14
0.6
104
L,08
2.15
0.8
26.89
0.82
1.65
0.2
1.0
13.61
2.90
5.43
5.66
0.4
0.2
207.71
23,08
45.72
34 29
0.4
0.4
244.54
17.03
14. 18
18.41
0.4
0.6
25
30.32
40 36
32
0.4
0.8
63
41.40
$2.60
31.29
0.4
1.0
133.83
58.33
69.83
69.59
0.6
0.4
25
[59
148.74
0.6
710.42
145.43
170.8
147.2
0.6
0.8
75
236.75
247.6 7.67
225.23
0.6
1.0
649.65
192.54
219.31
184.92
0.8
0.2
1358.99
507.04
474.49
462.67
1513.27
621.03
597.4 84
571.43
377.82
504
418.04
0047
326.61
320.17
297.40
50
1.0
0.2
1911 52
1175.66
1160.46
1118.15
0.4
18
912.1
930.03
888.82
0.6
1678.61
678
681.22
1455.71
602.00
558.4
451.87
Average
778.46
294.50
294.23
275.70
[
[M]
T
R
EDD
ATCSR_ Rm [60]
Cho al. (S=6) f [41]
MP-ASIL (k=6)
100
0.2
0.2
255 49
0.25
1.39 0.00
0.04
100
0.3
0.4
59.55
0.00
0.00
100
0.2
0.6
43.55
0.00
0.00
0,00
100
0.3
0.8
17.77
0.02
0.00
0,000
1.0
11.04
2.62
0.00
0.00
100
0.4
0.2
32.65
22.
10.17
100
0.4
044
48.43
15 K4
9.99
100
0.4
0.6
563.9
25.30
7.29
0.79
T00
0.4
0.8
$17 31
27.44
12.9
X.76
100
0.4
1.0
306 99
49.9
20.56
12.20
0.6
04
12
120 59
100
0.6
0.6
2163.50
167.17
138.09 09.
122.61
100
0.6
0.8
2733.12
34
71
272.11
100
0.6
1.0
1560.70
284.26
206.50
177.32
100
0.8
0.2
3880.05
1052,10
722,26
636.25
100
0.8
04
5125.11
1361.08
1002.46
915.62
0.5
0
3896
901
$30.94
0.8
2409 26
452.19
348.51
313.65
100
1.0
0.2
7073.31 31
3718.23
2655.25 76
2S17 50
100
1.0
04
6527.61
1200.26
2040 39
1941.05
100
1.0
0.6
5800.50
M189766
1377.45
8358.89
100
1.0
088
4949.04 04
1314.94
1057.
977.17
4716.41
1436.42
840.95
Average
2472.13
735.55
502.37
458.11
33

---

D.4 Experiment Results on PFSP Using Synthetic Datasets
In the PFSP benchmark results presented in Table 2, IL [42] is trained on a distribution different from that of the benchmark. Following the IL paper setting, we compare MP-ASIL with IL on synthetic datasets sampled from a Gamma distribution (a
= 2).
Setup. IL trained on instances with [J] x | 20 5 imitate solutions generated by NEH
[66]. a highly specialized PFSP solver. We also train MP-ASIL on small-size instances ( [J] x [M| 20x5) sampled from the Gamma distribution, using the same hyperparameters detailed in Table 23. For evaluation, we use 1,000 instances each for 20 50 and 100x5, and 100 instances each for 200x5, 500x5, and x x from [42]. We also include classical heuristics (Iterated Local Search (ILS) [64]. Iterated Greedy Algorithm (IGA) [65], and NEH [66]) as baselines.
Remark. IL does not directly provide datasets in its code repository but offers code for dataset generation." 4 Thus, we generate datasets and reproduce the evaluation results by rumning the trained IL model provided by the authors.
Results. Table shows that MP-AM -SIL achieves new state-of-the-ae results on these datasets. Surpris- ingly, MP-ASIL, trained exclusively on 20x5 instances, demonstrates strong cross cross-size generalization, outperforming NEH on all problem sizes except 100x5, while achieving computational speedups of 4x to 360x. This superior performance of MP-ASIL can be attributed to its self-evolutionary approach. While II. faces a performance ceiling due to imitating suboptimal solutions, MP-ASIL autonomously generates and learns from self-teaching labels. Thus, MP-ASIL can break the funda- mental limitation of classic SL methods, which strongly depend on the performance of their teacher algorithms.
Table 9: Experiment results on PFSP using synthetic datasets. Gap: Performance gap relative to NEH.
Other symbols follow definitions provided in Table 1.
PFSP 20x5
PFSP 50x5
PFSP 100x5
Method
Obj 4
Gap +
Time
Obj. 4
Gap 4
Time
Obj. 4
Gap
Time
ILS
29.96
2.74%
(9s)
65.33
4.38%
(18s)
121.49
3.63%
(36s)
IGA
29.05
-0.37%
(1m)
63.19
0.96%
(5m)
118.08
0.72%
(25m)
NEH
29.16
0.00%
(4s)
62.59
0.00%
(56s)
117.24
0.00%
(7m)
IL
31.93
9.50%
(0s)
68.05
8.72%
(1s)
125.34
6.91%
(2s)
ASIL
128)
28.43
-2.50%
(Is)
62.48
-0.18%
(2s)
117.37
0.11%
PFSP 200x
PFSP 500x5
PFSP 1000x5
Method
Obj. 4
Gap L
Time
Obj. 4
Gap 0
Time J
Obj. J
Gap
Time
ILS
230.12
2.92%
(7s)
551.77
2.36%
(19s)
1076.35
2.07%
(39s)
IGA
224.85
0.56%
(10m)
540.86
0.34%
(1h)
1056.55
0.19%
(4.2h)
NEH
223.60
0.00%
(9m)
539.06
0.00%
(1.5h)
1054.50
0.00%
(12h)
II
234.87
5.04%
(Is)
566.96
5.18%
(4s)
1115.22
5.76%
(21s)
MP-ASIL
128)
223.23
-0.15%
(3s)
537.31
-0.32%
(20s)
1049.17
-0.51
(2m)
D.5 Experiment Results on JSSP Using Lawrence's Benchmark
Setup. Lawrence's (LA) benchmark [75], widely used for evaluating generalization capability in JSSP research papers [26, 20], consists of five instances for each of the eight different problem sizes. To evaluate the generalization performance of MP-ASIL, we compare with the baseline methods listed in Table 3, excluding approaches that do not provide results on the LA benchmark.
Results. Table 10 demonstrates that MP-ASIL achieves the best average Gap (Avg.) among neural
constructive heuristics, finding optimal solutions for LA 15x5, LA 20x5, and LA 30x 10. Moreover, MP-ASIL solves all instances within one second per problem size, clearly outperforming L2S-500 and showing comparable performance to TBGAT-500, both known to require significantly longer
34

---

computation times as reported in [26] (e.g.. MP-ASIL requires 0.8 seconds for LA 15x instances, whereas L2S-500 and TBGAT-500 demand approximately one minute).
Table 10: Experiment results on JSSP using the LA benchmark. Symbols follow definitions provided
Table 1.
Method
LA 10x5
LA 10x10
LA 15x5
LA 15x10
LA 15x15
LA 20x5
LA 20x10
LA 30x10
Avg.
Gurobi (3600s)" [20)
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
OR-Tools (3600s) [67]
0.0%
0.0%
0.0%%
0.0%
0.0%
0.0%
0.0%
0.05$
0.0%
MWKR [20]
16.0%
12.2%
5.5%
17.8%
18.2%
5.2%
17.2%
8.6%
12.6%
1.20 (Gj* [1]]
23.7%
7.8%
23.1%
8.4%
17.4%
SN (G)* [29]
12.1%
11.9%
2.7%
14.6%
16.1%
3.6%
15.7%
3.1%
10.0%
1,20 (S=128)" [1T]
8.8%
10:45
2.8%
16.2%
17.45
3.1%
18.3%
6.8%
10.6%
SIIM (S-512)*f [20)
1.1%
2.5%
0.0%
5.0%
5.6%
0.0%
5.6%
0.0%
2.5%
L22-5000 [25]
2.1%
4.4%
0.0%
6.19%
7.3%
0.0%
7,0%
0.2%
3.4%
TBGAT-500* [26]
2.1%
18%
0.0%
3.6%
5.5%
0.0%
5.0%
0.0%
2.3%
MP-A8IL 512)
11
1.3%
2,1%
5.5%
0.0%
0.0%
D.6
Experiment Results on JSSP Using Synthetic Datasets
For JSSP, we also compare MP-ASIL with search-based NCO methods using synthetic JSSP datasets commonly used in the NCO literature.
Setup. Our test uses three sets of 100 instances each for 10x 10, 15x15, and 20 15 from [52].
Baseline methods include L.2D [11], Poppy [54], EAS [52], COMPASS [55], and TBGAT-500 [26]. L.2D and Poppy use naive stochastic sampling, whereas EAS fine-tunes its policy individually for each test instance. COMPASS improves solution quality through CMA-based policy space search
(detailed in Section D. D.1O), and TBGAT-500 employs GNN-based local search operator to iteratively update solutions for 500 iterations.
Results. Table 11 presents the average makespan (Obj.), Gap relative OR-Tools [67], and Time. From the table, we can find that MP-ASIL significantly outperforms all search- methods in solution quality and computational speed, with total inference times under one minute per test set. Notably, compared to COMPASS, which also learns latent conditioned policies but conducts extensive inference time search, MP-ASIL reduces the Gap using one-shot inference alone, from 4.7% 2.7 % on JSSP 10x 10, from 8.0% to 6.1 % on ISSP 15x 15, and from 10.4% to 8.2% % on JSSP 20x 15.
Table 11: Experiment results on JSSP using synthetic datasets. d denotes the number of decoders. Other symbols follow definitions provided in Table
JSSP 10x 10
JSSP 15x 15
JSSP 20x 15
Method
Obj. J
Gap | Time J
Obj. 4
Gap J
Time J
Obj
Gap
Time +
OR-Tools
807.6
0.0%
(37s)
1188.0
0.0%
(3h)
1345.5
0.0%
(80h)
L2D*
871.7
8.0%
(8h)
1378.3
16.0%
(25h)
1624.6
20.8%
(40h)
Poppy (d = 16)*
849.7
5.2%
(3h)
1290.4
8.6%
(5h)
1495.7
11.2%
(8h)
EAS+
858.4
6.3%
(5h)
1295.2
9.0%
(9h)
1498.0
11.3%
(11h)
COMPASS*
845.5
4.7%
(3h)
1282.8
8.0%
(5h)
1485.6
10.4%
(8h)
TBGAT-500
2.7%
(16m)
6.7%
(21m)
9.3%
(23m)
-SIL (k=512)
829.7
2.7%
(12s)
1260.9
6.1 %
(28s)
1456.6
8.2%
(40s)
D.7 Experiment results on FJSSP
Deterministic FJSSP. For FISSP, one of the most complex scheduling problems, we apply MPIASIL on top of DANIEL [31], tfate-of-the-rr neural FISSP solver. For comparison, we also include (1) Exact Solver: OR-Tools (1 (1800s); (2) Handcrafted Heuristic: First in First Out (FIFO), Most Operations Remaining (MOR), SPT, and MWKR; (3) Neural Constructive Heuristies: HGNN [73], MCGA [74], RS [39], and DANIEL [31] as baselines. Table 12 reports the Gap relative to OR-Tools (1800s) and Time. From the table, we can see that MP-ASIL significantly enhances the performance of DANIEL and outperforms all other methods. Remarkably, on large-scale instances unseen during
35

---

training (20x 10, 30x 10, and 40x 10), MP-ASIL even surpasses OR-Tools (1800s) while requiring x9 to 291 shorter computation times.
Table 12: Experiment results on FJSSP. Symbols follow the definitions provided in Table 1.
Method
Type
Cap-
10x5
Time
Cup.
20xx5
Time
Cap
15x10
Time
Gap
20x
I
Time
Clop
30x
10
Time:
Clop I
40x 10
Time |
OK Tools (1800s)"
Etect
0.009
(20h)
0.00%
1200)
0.00%
(200)
0.00%
(50h)
0.00%
(50h)
0.00%
(20h)
FIFO
Hemrisnes
24,0695
(166)
14,87%
(324)
28.65%
(516)
19.225
(1.2m)
19.50%
(1.8m)
16.6%%
(2.5m)
MOR
Houristies
19,87%
(166)
13.85%
(326)
20.685
(514)
12.30%
(1.2m)
15.57%
(1.8m)
15.13%
(2.5m)
Hemiisties
34.766%
50.25%
MWKR
Heuristics
17.58%
(166)
11.51%
19:41%
10.30%
(1.2m)
(1.8m)
13.37%
(2.5m)
(S=100)*
NCH]
(1.9m)
(3.9m)
12.13%
(6.5m)
9.64%
(10.7m)
(21.3m)
(40.9m)
MCGA 100g
NCHI
9.01%
3.36%
11.77%
7.70%
12.44%
22.00%
RS (S-1007)
NCH
7.2098
7.22%
9.39%
6.00%
11.34%
11 11.29%
DANIFI (5-100y"1
NCH
5.579
(1.2m)
2.46%
(3.lm)
6.79%
(6 5m))
-1,088%
(10.200 (m)
4.4%%
(70.6m)
3.77%
(37 6m)
WP-A311 (k=100))
NCH
3,00%
(1. (1.2m)
0.67%
(3. (3/lm)
4.61%
(6 5ml)
-3.00%
(10. 3m)
-8.15%
(70, 7m)
+0.59%
(37. 8m)
Additionally, we evaluate our approach on well-known FISSP benchmarks, including Brandimarte [76] and Hurink [77] datasets. The Hurink benchmark consists of edata, rdata, and vdata instances, with operations assignable to 1-2 machines, 1-3 machines, and I-|M]] machines, respectively. We also include Genetic Programming (GP) [78], representative HH, bascline. GP is a widely used methodology among dispatching rule generation HH, evolving populations of individual tree structures to automatically discover effective problem-solving strategies. This approach shares the same spirit as our method from the perspective of heuristics to generate heuristics. As shown in Table 13, MP-ASIL substantially surpasses all baselines, demonstrating robust and superior performance in out-of-distribution scenarios.
Table 13: Experiment results on FISSP using four benchmark datasets. provided in Table 1.
Symbols follow the definitions
Brandimarte Gap 1
Hurink (edata)
Hurink (vdata)
Hurink (rdata)
Method
Type
Gap
Gap
Gap 4
MWKR
Heuristies
28.91%
18.60%
4.25%
13.86%
GP
HH
12.13%
HGNN (S=100)*
NCH
18.56%
8.71%
1.32%
5.57%
MCGA (S=100)*
NCH
18.67%
8.38%
1,40%
5.71%
RS (0=100)*
NCH
15.40%
7.90%
0.70%
4.72%
DANIEL (0=100)*
NCH
9.53%
9.08%
0.69%
4.95%
-P-ASIL (k- 100)
NCH
7.32%
7.24%
0.50 %
4.66%
Stochastic FJSSP. MP-ASIL is also applicable stochastic scheduling problems. For stochastic problems, we can evaluate solution quality through expected makespan ((Cmaaz) or Value-at-Riss VaRa (Cmaz) metries by applying the model's decisions identically to multiple scenarios sampled from probability distributions. Thus, MP-ASIL can evaluate each policy's 's decisions through scenario sets, enabling easy application in the same way as deterministic problems. To validate this approach, we perform experiments on the stochastic FISSP, where processing times are random variables. We apply MP-ASIL to the Scenario Processing Module (SPM)-DAN [79], which introduces an attention- based SPM to solve stochastic FJSSP. Specifically, we implement latent conditioned policies by concatenating latent variables to the dccision-making layer (MLP) input as detailed in Appendix B. We employ the identical MP-ASIL training procedure described in the main text. Our training objective is to minimize V VaR, (Cmaz). Training hyperparameters and experimental settings follow the original paper, with training conducted on only 10x5 5 instances. Baseline methods include four dispatching rules (FIFO, MOR, SPT, and MWKR) and SPM-DAN.
Tables 14 and 15 present experiment results on various stochastic FJSSP datasets. Each problem size comprises 100 instances from SPM-DAN. From Table 14, we observe that MP-ASIL demonstrates clear performance improvement over SPM-DAN and significantly outperforms all dispatching rules, but requires slightly more computation time. Moreover, for different objective functions E E(Cmar)) shown in Table 15, MP-ASIL consistently achieves the best performance without retraining.
36

---

Through these experimental results, we verify that MP-ASIL can be effective for stochastic scheduling problems.
Table 14: Experiment results on stochastic FJSSP. The objective function is VaRa VaRa(C (Cmaz). We set
95%, following the original paper. Symbols follow the definitions provided in Table 1.
Method
10x5
20x5
15x10
20x10
Obj.
Gap
Time
Obj.
Gap L
Time
Obj. 1
Gap
Time
Obj.
Gap 1
Time J
FIFO
757.19
13.00%
(40s)
1308
6.98%
(1.3m)
1215.23
14.46%
(2.2m)
1448.87
11.41%
(2.8m)
MOR
753.22
12.41%
(40s)
1326.69
8.43%
(1.3ml
1182.71
11.40%
(2.2m)
1435.38
10.37%
(2.8m)
SPT
820.38
22.43%
(40s)
1427.94
16.71%
(1.3m)
1309.28
23.32%
(2.2m)
1485.49
14.27%
(2.8m)
MWKR
741.49
10.66%
(40s)
1317.16
7.66%
(1.3m)
1155.4
8.82%
(2.2m)
1419.13
9.12%
(2.7m)
SPM-DAN
670.08
0.00%
(1.8m)
1223.49
0.00%
(6.2m)
1061.71
0.00%
(14.7m)
1300.53
0.00%
(25,3m)
XP-AS11.
654.34
-2.8%
(1.8m)
1194.25
22.39%
(6.2m)
1026.87
-3.28%
(15m)
12300.7
-5.07%
(25.9m)
Table 15: Experiment results on stochastic FISSP. The objective function is BCCmarr). Symbols follow the definitions provided in Table 1.
10x5
20x5
15x10
20x10 *
Method
Obj. L
Gap -
Time
Ohj 4
Gap
Time
Obj
Gap J
Time
Ohj
Gap
Time
PIFO
643.35
10.18%
(406)
1171.82
4.98%
(1.3m)
1074.24
12.75%
(2.2m)
1301.00
9.16%
(2.7m)
MOR
641.50
9.52%
(40s)
1186.68
6.32%
(1.3m)
1044.47
9.63%
(2.2m)
1288.04
8.07%
(2.7m)
SPT
705.50
20.45%
(40s)
1280.55
12.76%
(1.3m)
1167.27
22.52%
(2.2m)
1485.49
14.27%
(2.7m)
MWKR
632.44
7.98%
(40s)
1179.92
5.71%
(1.3m)
1020.88
7.15%
(2.2m)
1275.73
7.04%
(2.7m)
SPM-DAN
585.74
0.005
(1.8m)
1116.19
0.00%
(6.3m)
952.73
0.00%
(14.7m)
1191.87
0.00%
(25.4m)
MP-A8T1
-2.60%
(1 (.8mm
1091.14
-2.24%
(6.3m)
-2.74%
(14.9m)
1139.56
(25.8m)
D.8 Ablation Studies
In this section, we present comprehensive ablation results for all problems evaluated in this study, using the ablation variants defined in Section 5.2. As shown in Figure 13, MP- ASII performs best in 22 out 24 benchmark datasets. Specifically, MP-ASIL significantly outperforms Poppy (AdvW, SIL ablation) across all benchmark problems, highlighting the effectiveness of MP-ASIL in optimizing multiple policies compared RL. Furthermore, MP-ASIL shows superior performance compared to SLIM (AdvW W. MP ablation), the offt-oftthe-rr SIL-based method, on all benchmark datasets except JSSP 15x 15 and JSSP 30.30. Additionally, removing Advantage Weight (AdvW ablation) substantially drops performance across all datasets, underscoring the importance of our proposed training scheme that dynamically adjusts imitation intensity for self-labels.
37

---

SMSP 50
SMSP 100
SMSP 500
UPMSP 50x3
2.4
35.77
100.00
9.04
Performance
20
0.81
6.49
0:41
16
20.87
0.2
3.37
6.8
0.20
0.02
0.15
Performanc gap (%)
14
15
24.25
20.35
3.
3.5
146
4.28
14
12-
12
3.54
0.24
1.-
36-
5.05
10.30
3.3
9.57
PFSP 50x5
PPSP 50x10
PFSP 100x5
PFSP 100x10
0.5
0.50
5.07
0.15
0.45
375
Performance gap
356
4.6
0.3
0.30
3.0
4:31
0.23
0.24
2.75
0.15
225
PFSP 200x10
FFSP 20x12
FFSP 50x12
FFSP 100x12
2.43
2.54
2.44
2.20
2.2
2.10
Performance
1.50
2.4
1.51
50
0.03
5.11
2.4
2:40
2.46
2.57
2.57
1:4
1.32
1.37
3.8
45
12
16
JSSP
JSSP
JSSP
JSSP
10.0
Performance gap (%)
3.25
7.60
9.27
325
12.35
22.0
2:29
52-
8.29
5.76
5.01
3.20
5.2
5,00
21 00
16-
3.52
8.62
20.60
6.6
JSSP 30x20
JSSP 50x15
JSSP 50x20
JSSP 100x20
Performance gap (96)
5.05
14.00
13.29
L825
2.47
5.50
13:29
12:78
12:92
12.66
6.90
7,412
7.60
15
1.25
4.54
10
7.03
0.95
Methods
Methods
Methods
Methods
MPASSIL (Ours)
AdvW ablation
AdvW, MP ablation
AdvW, SIL ablation
All ablation
Figure 13: Results of ablation studies. Gaps greater than 100% are truncated 100%.
38

---

Problem
Problem
Problem
Problem
1.50
1.00
1.0
1.00
0.75
3.73
0.7
5.75
0.50
0.50
3.50
0.2
0.25
.0.75
-1.00
-1.00
-100
-1.00
3.
0.0
6.5
1.
Problem 5
Problem
Problem
Problem 8
0.75
0.75
3.75
0.50
0.50
0.50
0.25
0.2
0.25
3.25
0.20
3.0
0.03
3.50
0.25
2.2
0.25
0.25
-150
-0.50
-3.75
-6.75
-2.75
10
-0.5
0.0
0.5
1.6
-1.0
-0.5
0.0
0.5
3.0
-3.0
-0.5
0.0
3.5
-0.5
0.0
0.5
1.
Figure 14: Policy latent space heat maps on problem instances. Red-colored regions correspond to low-performing latent regions, whereas blue-colored regions show high-performing areas.
D.9 Performance Landscape Visualization
In this section, we visualize the performance landscape of a two-dimensional policy latent space. To this end, we train the model with a two-dimensional latent space bounded in [-1, 1]. We then evaluate 32,000 randomly sampled latent vectors on eight TA PFSP instances of size 20 x 5 and report the results in Figure 14. From the figure, we observe that: 1) the performance landscape is instance- Destance-dependent and 2) high-performing regions differ across various instances. These findings confirm that different policy regions specialize in generating superior solutions for distinct instance subsets. These conclusions also motivate the application of search techniques to find high-performing latent space regions during inference, with the results presented in the subsequent section.
D.10 Policy Latent Space Search Inference Time
Randomly sampling latent variables at inference time does not guarantee that promising latent variables will be included (although increasing the number of samples can improve the likelihood). However, at inference time, we can apply principled search procedure to find high-performing latent variables. Recently, COMPASS [55] introduced a policy latent space search method using the Covariance Matrix Adaptation (CMA) [80] evolutionary algorithm. In this section, we use CMA at test time to search for promising latent areas on a per-instance basis.
Following the COMPASS paper, we em- ploy three independent CMA components in parallel with 1,600 search attempts and report the results in Table 16. For compar- ison, we present results that apply CMA to latent-conditioned policies trained via Poppy [54] instead of MPIASIL, which ex- actly matches the original COMPASS train- ing setup. Poppy is an RL-based method. In addition, we report sampling-base -ased results (MP-ASIL + SAM), where the number of samples is set equal to the number of search attempts.
Table 16: Performance evaluation results combined with CMA on the TA benchmark. J: Lower is better.
PFSP 20x 10
JSSP 20x Gap 4
Method
Gap 4
Poppy + CMA
2.27%
7.35%
MP-ASIL SAM
2.04%
6.98%
MP-ASIL + CMA
1.63
6.37 %
From the table, we can see that MP-ASIL- + SAM already outperforms Poppy CMA without the search method. Furthermore, MS-ASIL- + CMA achieves significant relative performance improve- ments of 25. 1% on PFSP 20x 10 and 9.6% on JSSP 20x 15 compared to MP-ASIL + SAM. These results highlight the effectiveness of MP-ASIL in optimizing multi-policy compared to the RL-based method and show that performance can be significantly improved through search procedures to identify promising regions in the latent space.
39

---

E
Vehicle Routing Problems
In this section, we present performance evaluation results for various out-of-distribttion scenarios in VRPs (cross-size, cross-distribution, and cross-problem generalization). These experiments aim to demonstrate that MP-ASIL can show good generalization capabilities across diverse COPs.
E.1 Cross-size Generalization
This part presents the cross-size generalization performance of MP-ASIL on TSP and CVRP.
three datasets of 1,000 instances each with 125, 150, and 200 from [52] and compare MP- with the baseline methods listed in Table All methods generate solutions following the procedure detailed in Section 5.2, employing models trained on instances with n 100. As before, MP-ASIL does not enforce distinct initial actions.
Setup. For evaluation,
Results. Table 17 summarizes the experimental results for TSP and CVRP instances of various sizes. From the table, we can observe that MP-ASIL significantly outperforms state-of-the-art NCO methods across all sizes, with the performance advantage increasing instance size grows for both problems. These results confirm that MP-ASIL demonstrates remarkable cross-size generalization capabilities across various COPs.
Table 17: Experiment results on TSP and CVRP. Symbols follow definitions provided in Table
n = 125
== 150
n = 200
Method
Obj.
Gap 4
Time J
Obj. J
Gap 4
Time
Obj. 4
Gapl
Time 4
LKH3*
8.583
0.000%
(73m)
9.346
0.000%
(99m)
10.687
0.000%
(3h)
POMO" [[10]
8.607
0.278%
(<lm)
9.397
0.542%
(<lm)
10.843
1.457%
(Im)
Sym-NCO i[17]
8.619
0.413%
(<lm)
9.402
0.599%
(<lm)
10.849
1.516%
(Im)
Poppy (d=16)* [54]
8,594
0.14%
(<lm)
9.372
0.27%
(<lm)
MP-ASIL
8,585
0.028%
(<lm)
9.359
0.143%
(<lm)
10.798
1.041
(1m)
LKH3*
17.50
0.00%
(19h)
19.22
0.00%
(20h)
22.00
0.00%
(25h)
CVRP
POMO* [0]
17.73
1.29%
(clm)
19.64
2.18%
(Im)
22.90
4.12%
(1m)
Sym-NCO]
17.72
1.23%
(<lm)
19.61
2.03%
(<lm)
22.78
3,54%
(Im)
Poppy (d=32)" [54]
17.63
0.74%
(1m)
19.50
1.46%
(Im)
MP-ASIL
17.62
0.70%
(<lm)
19.46
1.23%
(<lm)
22.57
2.58%
(1m)
Furthermore, to validate performance on larger-scale TSP datasets (TSP 100, TSP 200, TSP 500, and TSP 1000 from [45]), we implement MP-ASIL with BQ-NCO [72] and perform evaluations. Baseline methods include BQ-NCO trained via SI. and BQ-NCO trained through SI GD) [45], another SIL-based approach. The results are presented in Table 18. The table shows that MP MP-ASIL does not surpass the baseline approaches on TSP 100, TSP 200, and TSP 1000. However, MP-ASIL remains easy to implement, without requiring labeled data for SL or extensive search and hyperparameter tuning needed for SI GD (as mentioned in Section 2). To improve performance, a discussion on this topic is provided in the Limitations section (Appendix G).
Table 18: Experiment results on large-size TSP. beam: Beam search. Other symbols follow definitions provided in Table 1.
Method
n 100
n
200
n Gap
1000 Gap
Gap 4
Gap +
BQ-NCO beam (SL)*t
0.02
0.09 %
0.43%
0.91
BQ-NCO beaml6 (SI G
0.02%
0.10%
0.46%
1.01%
MP MP-ASIL (k: 16)
0.02%
0.14%
0.41 %
1.19%
E.2
Cross-distribution Generalization
This part discusses the cross-distribution generalizability of MP-ASIL on TSP.
40

---

Setup. For evaluation, we use four TSP 100 datasets with different distributions, including uniform, clustered, explosion, and implosion from INViT [81]. Each dataset contains 2,000 instances. As baseline methods, we include RL-bbased approaches (POMO [10], PointerFormer [18), Omni-TSI. [82], ELG [83], and INVIT [81]) and SL.-based methods (LEHD [71] and BQ-NCO [72], following the baseline methods used in INVIT. In our experiments, we employ the trained POMO models used
in Section 5.2. At test time, we use & = 100 policies for each instance to generate solutions and also apply data augmentation to enhance overall performance.
Results. Table shows the performance on TSP 100 datasets from four different distributions. The Gap is computed relative to Gurobi. The table demonstrates that MP-ASIL substantially surpasses all NCO methods across all distributions while maintaining efficient runtime. Particularly, while the second-best and third-best methods vary across datasets, MP-ASIL consistently maintains top performance. We attribute this robustness to MP-ASIL'S ability to learn multiple specialized behaviors. Even when some policies perform poorly specific distributions, others can achieve superior performance and provide complementary strengths, thereby demonstrating excellent and robust performance under distribution shift scenarios.
Table 19: Experiment results on four TSP 100 datasets. Symbols follow definitions provided in Table
1.
Uniform
Clustered
Explosion
Implosion
Method
Gap 4
Time +
Gap 4
Time +
Gap +
Time +
Gap +
Time +
Gurobi
0.00%
(23.8m)
0.00%
(34.4m)
0.00%
(28.3m)
0.00%
(28.7m)
POMO*
1.29%
(2.0m)
3.89%
(1.7m)
1.42%
(1.7m)
1.44%
(1.7m)
PointerFormer**
0.43%
(1.7m)
3,96%
(1.7m)
0.87%
(1.7m)
0.71%
(1.7m)
Omni-TSL=
2.55%
(2.0m)
3.62%
(2.0m)
3.21%
(2.0m)
2.67%
(2.0m)
ELG*
0.51%
(3.2m)
3.69%
(2.3m)
0,93%
(3.5m)
0.85%
(3.2m)
INViT-2V*
1.65%
(3.0m)
3.12%
(2.9m)
1.85%
(3.1m)
1.95%
(2.9m)
INViT-3V*
0.95%
(4.2m)
2.47%
(4.0m)
1.12%
(4.3m)
1.21% %
(4.0m)
LEHD
0.57%
(11.5m)
4.51%
(14,9m)
0.68%
(11.1m)
1.17%
(18.3m)
BQ-NCO*
5.90%
(16.6m)
8.86%
(17.4m)
6.41%
(18.0m)
6.40%
(16.8m)
XP-ASIL (k: = 100)
0.00%
(1.0m)
1.05%
(1.0m)
0.06 %
(1.0m)
0.21 %
(1.0m)
E.3
Cross-problem Generalization
In real-world industrial applications, cross-problem generalization is as important as cross-size and cross-distribution generalization since practical problems typically involve various attributes and constraints. this part, we verify the ability of MP-ASIL to address this critical requirement.
Setup. Figure 15 summarizes the attributes considered in our experiments. Each problem variant is derived by incorporating one or more additional attributes into the standard CVRP formulation (e.g.. CVRP Time Window (TW) = CVRPTW, CVRP + Open route (O) = OVRP, and CVRP + TW + + Backhaul (B) OVRPBTW).
Time Windows (TW): The vehicle must visit node within the time window from to 4, and each node has a service time 8; If the vehicle arrives at node before e,, must wait until e, to begin service.
Open Routes (0): The vehicle is not required to return to the depot after completing visits to all nodes.
Backhaul (B): The classical CVRP assumes that demand is positive (linchaul) for delivery. In practice, however, customers can have negative demand (backhaul) for pickup. The linchaul and backhaul customers may coexist the same route.
Duration Limit (L): The total length of each route must not exceed a predetermined threshold.
We build MP-ASIL upon POMO-MTL. [84], transformer-based multi-task VRP solver. Except for the policy optimization strategy (a single policy with POMO MP-ASIL) and the rollout strategy,
41

---

Vehicle route
Time
Linehaul
Backhaul
Depot
Time Window
Open Route (O)
Backhauls (B)
Duration limit (L)
Figure 15: Illustrations of various attributes of VRPs.
we follow the same training setup, evaluation procedure, and datasets in POMO-MTL. During both training and inference, we do not enforce distinct initial actions. This strategy is particularly critical in complex VRPs, where initial actions can significantly influence solution quality, rendering rollouts from every node less suitable; however, this aspect is frequently overlooked in current studies [56].
Results. Table 20 shows the performance evaluation results for five trained VRPs and five unseen VRPs. Performance gaps (Gap) are computed relative HGS [85]. a state-of-the handcrafted VRP solver. For trained VRPs, the table demonstrates that MP-ASIL significantly outperforms POMO- MTL across all VRP variants, reducing the Gap from 1.71% to 1.48 % on CVRP 100, from 3.81% to 3.70% on VRPTW 100, from 4.48% to 4.01 % on OVRP 100, from 3.58% to 2.80% % on VRPB 100, and from 1.66% to 1.23% on VRPL 100.
For unseen VRPs, ASIL shows remarkable cross-problem generalization, surpassing POMO-MTL across nearly all instances. Specifically, MP-ASIL achieves performance improvements by reducing the Gap from 4.50% to 3.77% % on VRPBL 100, from 3.05% to 3.01 % on VRPBTW 100, and from 1 11.50% 10.86 % on OVRPBLTW 100, while performing slightly worse only on OVRPL 100 (4.57% vs. ).90% These results strongly support the capability of MP-ASIL to effectively generalize across diverse out-of-distribution scenarios, underscoring its effectiveness both single-task and multi-task settings.
42

---

Table 20: Experiment results on ten VRP variants using synthetic datasets. Each problem includes
5,000 test instances. Symbols follow definitions provided in Table
(a) Trained VRPs
CVRP 100
VRPTW 100
OVRP 100
Method
Obj. +
Gap 4
Time 4
Obj. +
Gap +
Time
Obj. +
Gap 4
Time +
HGS*
15.54
0.00%
14h
26.14
0.00%
14h
9.71
0.00%
POMO-MTL
15.80
1.71%
35s
27.13
3.81%
35s
10.14
4.48%
35s
MP-ASIL
15.77
1.48
368
27.11
3.70% %
36s
10.10
4.01
VRPB 100
VRPI. 100
AVG.
Method
Obj.
Gap 4
Time 4
Ohj.
Gap
Time
Ohj. 4
Gap
Time +
HGS*
11.13
0.00%
(14h)
15.54
0.00%
(14h)
15.612
0.00%
(14h)
POMO-MTL**
11.53
3.58%
(35s)
15.80
1.66%
(35s)
16.27
3.05%
(35s)
MP-ASIL
11.44
2.80%
(36s)
15.73
1.23 %
(36s)
16.03
2.68 %
(36s)
(b) Unseen VRPs
VRPBL 100
OVRPL 100
VRPBTW 100
Method
Obj. L
Gap
Time
Obj.
Gap J
Time 1
Obj. 1
Gap 1
Time 1
HGS*
11.15
0.00%
(14h)
9.71
0.00%
(14h)
26.31
0.00%
(14h)
POMO-MTL
11.65
4.50%
(35s)
10.15
4.57 %
(35s)
27.11
3.05%
(35s)
MP-ASIL
11.57
3.77 %
(36s)
10.19
4.90%
(36s)
27.10
3.01 %
(36s)
OVRPLTW 100
OVRPBTW 100
AVG.
Method
Obj. 4
Gap
Time
Obj.
Gap 4
Time 4
Obj. 4
Gap 1
HGS*
17.35
0.00%
(14h)
17.31
0.00%
(14h)
16.36
0.00%
(14h)
POMO-MTL
19.34
11.50%
(35s)
19.32
11.61% %
(35s)
17.51
7.03%
(35s)
MP -SILL
19.23
10.86 %
(36s)
19.29
11.44 %
(36s)
17.47
6.78%
(36s)
43

---

The number of decoder layers Training Hyperparameters
In this section, we provide training hyperparameters. closely following the original papers. Our experimental results in this paper show that simply applying MP-ASIL without hyperparameter tuning achieves significantly improved performance while maintaining comparable training and inference time. This demonstrates the practical value and ease of adoption of our method, enabling practitioners to seamlessly replace policy gradient methods without requiring extensive hyperparameter calibration or algorithmic redesign.
SMSP.
Due the lack of neural constructive solver for SMSP, we develop the model based on BQ-NCO [72].
Table 21: Hyperparameter setting for SMSP, Hours.
SMSP
Learning Rate (LR)
le-4
Weight decay
1e-6
The number of encoder layers
The number of decoder layers The number of attention heads Hidden embedding dimension (dx)
5
128
Batch-size
Continuous latent variable dimension
4
Categorical latent variable dimension
The number of policies (Training)
128
Epochs
100
Optimizer
Adam
LR scheduler
MultiStepLR
LR milestones
[90,100]
LR gamma
0.1
Epoch size
1,000
Training time
~hh
UPMSP.
We follow the training settings from [41].
Table 22: Hyperparameter setting for UPMSP d: Days.
UPMSP
Learning Rate (LR)
5e-4
Weight decay
The number of encoder layers
3
The number of attention heads Hidden embedding dimension (dr)
64
Batch-size
Continuous latent variable dimension
2
Categorical latent variable dimension
The number of policies (Training)
32
Epochs
1,000
Optimizer
Adam
LR scheduler
Constant
Epoch size
256
Training time
~3
44

---

PFSP.
We follow the training settings from [12].
Table 23: Hyperparameter setting for PFSP.
PFSP
Learning Rate (LR)
le-4
Weight decay
le-6
The number of encoder layers
The number of decoder layers The number of attention heads Hidden embedding dimension (d))
128
Batch-size
200
Continuous latent variable dimension
4
Categorical latent variable dimension
The number of policies (Training)
128
Epochs
1,000
Optimizer
Adam
LR scheduler
MultiStepLR
LR milestones
[900, 950]
LR gamma
0.1
Epoch size
100,000
Training time
l..2
FFSP.
We follow the training settings from [12].
Table 24: Hyperparameter setting for FFSP 20x 12, 50x 12, and 100x 12.
FFSP 20x12
FFSP 50x12
FFSP 100x 12
Learning Rate (LR) Weight decay
le-5
1e-5
le-5
le-6
1e-6
le-6
The number of encoder layers
The number of decoder layers The number attention heads
1
16
16
Hidden embedding dimension (d,)
256
256
256
Batch-size
50
50
Continuous latent variable dimension
4
4
Categorical latent variable dimension
12
12
The number of policies (Training)
24
24
24
Epochs
100
150
200
Optimizer
Adam
Adam
Adam
LR scheduler
MultiStepL.R
MultiStepL. [130,140]
MultiStepLR
LR milestones
[80,90]
[170,190]
LR gamma
0.1
0.1
0.1
Epoch size
1,000
1,000
1,000
Training time
~2hh
~5h
ld
45

---

JSSP.
We follow the training settings from [20].
Table 25: Hyperparameter setting for JSSP.
JSSP
Learning Rate (LR)
le-4
Weight decay
The number encoder layers
The number of decoder layers The number of attention heads Hidden embedding dimension (d,)
2
128
Batch-size
Continuous latent variable dimension
4
Categorical latent variable dimension
12
The number of policies (Training)
256
Epochs
20
Optimizer
Adam
LR scheduler
Constant
Epoch size
30,000
Training time
~4d
FJSSP.
We follow the training settings from [31].
Table 26: Hyperparameter setting for FJSSP.
FJSSP
Learning Rate (LR)
3e-4
Weight decay
The number of encoder layers
The number of decoder layers The number of attention heads Hidden embedding dimension (di)
2
64
Batch-size
Continuous latent variable dimension
4
Categorical latent variable dimension
The number of policies (Training)
128
Epochs
40
Optimizer
Adam
LR scheduler
Constant
Epoch size
160
Training time
~5h
46

---

TSP and CVRP. We follow the training settings from [10].
Table 27: Hyperparameter setting for TSP and CVRP.
TSP
CVRP
Learning rate
le-4
Weight decay
le-6
The number encoder layers
The number of decoder layers The number of attention heads
Hidden embedding dimension (d,,)
128
Batch-size
Continuous latent variable dimension
4
Discrete latent variable dimension
The number of policies (Training)
100
Epochs
2,000 Adam MultiStepLR
8,000
Optimizer
Adam
LR scheduler
MultiStepLR
LR milestones
[I (1900,1950)
[7900, 7950]
LR gamma
0.1
0.1 10,000
Epoch size
100,000 ~12d
Training time
44
G Limitation and Future Work
Algorithm. Despite the demonstrated effectiveness of MP-ASIL, our approach has several potential limitations. First, MP-ASIL samples latent variables from a fixed prior distribution across all instances, potentially overlooking optimal instance-specific priors. Therefore, learning adaptive, instance-dependent distributions is promising future direction. Second, while increasing the number of policies (k) can make stronger models during training (detailed in Section 5.2), it also increases memory usage and training time. Therefore, an important avenue for future research is to design practical yet effective sampling framework that can generate stronger self-teachers from fewer samples drawn from promising policy subspaces.
Applications. In this work, primarily focus deterministic and static JSPs. For future rescarch, we plan to apply MP-ASIL to more realistic scenarios, including communication latency [86] and dynamic environments, well multi-objective JSPs. Additionally, we aim to demonstrate MP-ASIL's effectiveness across a broader range of COPs.
H Broader Impact
This paper introduces new learning paradigm for scheduling problems. MP-ASIL addresses diverse decision-making tasks in manufacturing and logistics via end-to-end learning, potentially reducing human reliance on effective heuristic algorithm design. However, unlike simple PDRs, deep learning lack interpretability, raising trust concerns for Al-driven decision-making systems. Therefore, advancing explainable Al methods to elucidate and justify decision-making processes remains critical avenue for future research.
I Licenses
The licenses for code repositories and datasets used in this work are summarized in Table 28.
47

---

Table 28: List of licenses for code repositories and datasets used in this work.
Resource
Type
Link
License
BQ-NCO
Code
https///gtttuub.cccam//rrrggggop
CC BY-NC-S 4.0
DeepACO
and
Code& dataset
MIT License
ACO
GFACS
Code
attp:///gttuub.conn/////ffffff
MIT License
POMO
Code
http:://gthhib..mmm//keeaooaoooo dataset
MIT License
MatNet
Code&
MIT License
IL. ILS, IGA, and
Code
https///gtttbb.coo//ola///s
Available online
NEH
SLIM
Code&
Available online
dataset
SelflaabelingJJbShhop
DANIEL
Code&
htsp:://gthtbb.oo//rrcccc////11
Available online
dataset
SPM-DAN
Code
https:///gtthbb.comm
Available online
ai-for-deeiisionnmmkiinnn--
RCD-for-Stocchattic-F999
Sym-NCO
Code
Available online
EAS
Dataset
http:://ggttibb.cc//hhhuuuuuu//
Available online
SI GD
Dataset
wtt..////ggg//////// gumbeldoree/treeenaii
http:://ggtcuub..oom/rrrmmm
Available online
INVIT
Dataset
Available online
INViT
POMO-MTL.
Code&
Available online
Dataset
48


Reviews:
[{"review_id": "5LJzkr0RCP", "reviewer": "Reviewer_SjhF", "summary": "This article proposes MP-ASIL, a multi-policy adaptive self-imitation learning framework for solving combinatorial optimization problems, with a focus on the job-shop scheduling problem (JSP). The method constructs an ensemble of policy networks trained through self-imitation learning (SIL), where the imitation intensity is modulated based on a learned diversity score. This adaptive mechanism aims to promote exploration while ensuring performance improvement. The framework is evaluated on several JSP benchmarks and demonstrates state-of-the-art performance compared to both classical heuristics and learning-based baselines. The authors argue for the generality, robustness, and efficiency of MP-ASIL and emphasize its potential as a scalable and adaptive approach to combinatorial scheduling.", "questions": "The self-imitation process only reinforces the best trajectory found so far. Does this not introduce the risk of overfitting or premature convergence? Have the authors considered mechanisms to maintain diversity over time, such as memory buffers of high-quality trajectories, entropy regularization, or stochastic selection?\n\nMP-ASIL’s inference time is compared against the total execution time of classical and hybrid solvers, but training time is not included. Furthermore, some runtime values are drawn from previous works using different hardware. How do the authors justify the fairness of this comparison? Would it be possible to provide normalized runtime metrics or at least clearly distinguish training and deployment costs?\n\nHow does MP-ASIL relate to the well-established literature on hyper-heuristics and automated algorithm design [1]? These approaches also aim to generalize across problem instances and domains, and may offer relevant baselines or complementary perspectives.\n\nWhile the paper includes examples of MP-ASIL applied to TSP and VRP in the appendix, these applications are limited in scale and not thoroughly evaluated. Could the authors elaborate on how MP-ASIL generalizes across different combinatorial problem classes? Are modifications to the architecture, policy representation, or diversity mechanism required when extending to problems with different structures and constraints?", "limitations": "The authors provide a dedicated discussion of limitations in Appendix G. Key points include the reliance on handcrafted rewards, the lack of theoretical guarantees, and scalability concerns. However, the comparison with classical methods still omits training cost, and the generalization beyond JSP is only briefly explored through small-scale TSP and VRP examples.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper addresses a well-established and practically important problem using a novel, learning-based formulation that builds on the strengths of policy ensembles and adaptive imitation.\n- MP-ASIL introduces a principled mechanism for adjusting imitation intensity based on trajectory diversity, which helps mitigate common SIL limitations such as overfitting to early successes or reduced exploration.\n- The method is clearly described and supported by comprehensive experiments on multiple JSP standard benchmarks, with strong empirical results in terms of solution quality and inference efficiency.\n- The evaluation includes comparisons to exact methods (CPLEX, Gurobi, OR-Tools), classical heuristics (e.g., ACO, ILS, IGA) and recent learning-based methods, showing consistent improvements and even some new state-of-the-art results.\n- The appendices provide useful implementation and training details, along with further ablation studies and case analyses supporting the method’s robustness and scalability.\n\nWeaknesses:\n- The paper does not consider other relevant literature like hyper-heuristics and automated algorithm design, which share the objective of instance-general learning and optimization. These paradigms could serve as additional baselines or conceptual anchors [1].\n- The description of the proposed adaptive imitation intensity control approach includes informal terms such as “unexpected or surprising”. More formal terms are expected.\n- The diversity metric used in the experiments is very simple. Why not relying on existing ones from the literature, such as in [2] which proposed a more robust population-level diversity measure.\n- While MP-ASIL achieves impressive inference-time results, the comparison with other methods does not always consider total compute effort. Specifically, MP-ASIL’s inference time is compared to the full execution time of classical or hybrid solvers, omitting training time and possibly relying on disparate hardware setups from prior works. This limits the fairness and interpretability of the runtime comparison.\n- The use of only the best trajectory for self-imitation introduces the risk of overfitting or premature convergence. It remains unclear whether the model retains any stochasticity or memory of alternative high-quality solutions to avoid narrow policy convergence.\n- The comparison of the different policies performance on batches of performance is not always very significant and lacks a more precise and quantified analysis.\n- Tables 2 and 3 present extensive results but suffer from readability issues due to dense formatting and small font sizes.\n\n[1] Burke, E. K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., & Qu, R. (2013). A survey of hyper-heuristics. ACM Computing Surveys (CSUR), 45(3), 1–35. https://doi.org/10.1145/2480741.2480752\n[2] Halim, A. H., Ismail, I., & Das, S. (2021). Performance assessment of the metaheuristic optimization algorithms: an exhaustive review. Artificial Intelligence Review, 54, 2323–2409. https://doi.org/10.1007/s10462-020-09906-6", "was_revised": true, "final_justification": "I have no further remarks or questions. While I will maintain the overall score based on the level of contribution, I have increased the clarity score to reflect the enhancements made during the rebuttal phase.", "rebuttal": "We thank the reviewer for their comments and positive feedback. Please find our responses to the main concerns and questions below:\n\n>**W1&Q3**: Hyper-Heuristics (HH) and automated algorithm design\n\nOur approach shares the same spirit as the primary objective of HH in automatically deriving heuristics. Also, Neural Combinatorial Optimization (NCO) can be regarded as a variant of HH, wherein neural architectures and solution pipelines define a heuristic space, and training algorithms search within it [1]. We will update the paper to include a discussion on HH. \n\n[**Revised**] Line 27: Beyond expert-designed heuristics, Neural Combinatorial Optimization (NCO) methods, as a variant of Hyper-Heuristics (HH) [2], have recently emerged to automate the heuristic design process\n\nAdditionally, we conducted further experiments on the Flexible Job Shop Scheduling Problem (FJSSP) as requested by another reviewer. We included Genetic Programming (GP) [3], a representative HH, as a baseline. From the Table1 (below), we can see that MP-ASIL significantly outperforms all baselines. Thank you once again for providing valuable insight!\n\nTable 1. Experiment results on FJSSP.\n\n| Method                 | Type        | Brandimarte |\n|------------------------|-------------|-------------|\n| MWKR                   | Heuristics  | 28.91%      |\n| GP (Single-tree)       | HH          | 12.71%      |\n| GP (multi-tree)        | HH          | 12.13%      |\n| HGNN (S=100)           | NCH         | 18.56%      |\n| RS (S=100)             | NCH         | 15.40%      |\n| MCGN-PPO (S=100)       | NCH         | 18.67%      |\n| DAN (S=100)            | NCH         | 9.53%       |\n| MP-ASIL (k=100)        | NCH         | **7.32%**      |\n\n>**W2**: Informal terms\n\nThank you for the helpful comment. We will remove informal terms from the manuscript.\n\n[**Removed**] Line 198: This weight measures how unexpected or surprising the best solution is relative to others.\n\n>**W3**: Diversity metric\n\nAs you pointed out, we could employ more robust population-level diversity measures such as distance-based metrics or Shannon entropy. However, our main purpose was to measure how many non-duplicate solutions our method generates. This is because sampling from single policy approaches often produces many duplicate samples due to the relatively deterministic probability distribution, as has been pointed out in the literature [4,5,6]. In this context, we aimed to verify how much our multi-policy approach reduces the generation of duplicate solutions compared to single policy approaches. Therefore, we used the percentage of unique solutions as our diversity measure. We believe that the percentage of unique solutions is a sufficient and intuitive metric to achieve our evaluation purpose. Additionally, recent works in NCO literature [4,7] have employed the same percentage of unique solutions as their diversity measure.\n\n> **W4&Q2**: Omitting training time and runtime comparison\n\n- **Training time**: Training time is indeed a critical metric, which we have reported in Table 6 of Appendix D. However, we would like to clarify the distinction between training time and inference time in our experiments. In our experimental tables, the Time metric specifically reports the inference time required to solve the test datasets, which is the standard metric commonly adopted across NCO literature. Learning-based methods, including MP-ASIL, once trained offline, enable real-time decision making for new problems without retraining. This represents a significant computational advantage of learning-based methods over classical or heuristic solvers, which must spend considerable computational effort to solve each new instance from scratch. This is precisely why recent NCO methods have garnered significant attention in the optimization community.\n\n- **Runtime**: We acknowledge that direct runtime comparisons can indeed vary significantly due to implementation and hardware, as you point out. We appreciate your comment and will update the paper to provide clearer context regarding the limitations of runtime comparisons.\n\n[**Added**] Line 223: Importantly, Time may not be directly comparable due to different hardware and other factors. So, for clarity, we mark * on the results reported from the original papers.\n\n>**W5&Q1**: Overfitting or premature convergence\n\n- Naive self-imitation learning only imitates the best solution using single policy, which can lead to the issues you mentioned. In contrast, our method mitigates these problems through a policy specialization process in which different policies learn different high-quality solutions, thereby promoting solution diversity across the population. This design enables multiple policies to learn diverse and complementary problem-solving strategies based on latent variables. We also demonstrate empirically that our model consistently improves validation performance during training in Figure 10 of Appendix E.3.\n\n- As you mentioned in Q1, several components can be considered in our framework. Actually, in our framework, each policy employs stochastic selection rather than greedy selection. Also, we could apply entropy bonus. However, computing the entropy over the entire trajectory remains computationally intractable [5,7]. Finally, memory buffers of high-quality solutions represent a promising avenue for reducing overfitting risks and enabling more stable training. We appreciate these constructive suggestions for future research directions. We would be happy to collaborate if there is the opportunity.\n\n>**W6**: The comparison of the different policies performance\n\nCould you please clarify whether you are referring to the results presented in Table 8, which evaluates the performance across different latent variable distributions?\nIf you meant a different result of our policy comparison analysis, we would appreciate your guidance to ensure we address your concern accurately.\n\n>**W7**: Readability\n\nWe sincerely apologize for readability issues. For improved readability, we will update the paper to move the Time from Tables 2 and 3 to a separate table in the appendix. This will allow us to increase the font size for each metric.\n\n>**Q4**: Generalizes across different CO classes\n\n- Our main contribution and focus are on scheduling problems. However, to demonstrate the broader applicability of our approach to other CO problems, we conducted evaluations on TSP and 10 CVRP variants, which are widely used benchmarks in the NCO literature. While we acknowledge that 200 node problems may be considered relatively small, we scaled to the same instance sizes as previous works for fair comparison [8,9]. Our experimental results demonstrate that our method consistently outperforms previous state-of-the-art methods on routing problems by a large margin. We recognize that evaluating the applicability to much larger-scale routing problems would require additional research and experimentation. However, since our primary focus is on scheduling, we did not pursue this direction in the current study.\n\n- Our method can be easily applied to other CO problems with minimal modifications\n    - **Architecture**: As described in Appendix B, multi-policy can be readily implemented by concatenating latent variables to the input of the decision-making layer, regardless of problem-specific architectures. This design choice ensures that our approach is model-agnostic and can be integrated with existing neural architectures for various CO problems.\n    - **Policy Representation**: As mentioned in the Architecture section, since we only need to condition on latent variables, there is no need to modify the policy representation.\n    - **Diversity Mechanism**: Since all CO problems allow for ranking candidate solutions generated for an instance based on their objective values, MP-ASIL can be applied without any modifications. Therefore, MP-ASIL specialization mechanism ensures that different policies can learn diverse problem-solving strategies, eliminating the need for additional diversity mechanisms.\n\n> **P**: Reference section\n\nWe appreciate your feedback! By consolidating some references without any ethical issues, we will add more content (e.g., HH) in the main text.\n\n\n[1] Ye, Haoran, et al. \"Reevo: Large language models as hyper-heuristics with reflective evolution.\" Advances in neural information processing systems 37 (2024): 43571-43608.\n\n[2] Burke, Edmund K., et al. \"A survey of hyper-heuristics.\" Computer Science Technical Report No. NOTTCS-TR-SUB-0906241418-2747, School of Computer Science and Information Technology, University of Nottingham (2009).\n\n[3] Braune, Roland, et al. \"A genetic programming learning approach to generate dispatching rules for flexible shop scheduling problems.\" International Journal of Production Economics 243 (2022): 108342.\n\n[4] Shi, Kensen, David Bieber, and Charles Sutton. \"Incremental sampling without replacement for sequence models.\" International Conference on Machine Learning. PMLR, 2020.\n\n[5] Xin, Liang, et al. \"Multi-decoder attention model with embedding glimpse for solving vehicle routing problems.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 13. 2021.\n\n[6] Pirnay, Jonathan, and Dominik G. Grimm. \"Self-improvement for neural combinatorial optimization: Sample without replacement, but improvement.\" arXiv preprint arXiv:2403.15180 (2024).\n\n[7] Hottung, André, Mridul Mahajan, and Kevin Tierney. \"PolyNet: Learning diverse solution strategies for neural combinatorial optimization.\" arXiv preprint arXiv:2402.14048 (2024).\n\n[8] Grinsztajn, Nathan, et al. \"Winner takes it all: Training performant rl populations for combinatorial optimization.\" Advances in Neural Information Processing Systems 36 (2023): 48485-48509.\n\n[9] Kwon, Yeong-Dae, et al. \"Pomo: Policy optimization with multiple optima for reinforcement learning.\" Advances in Neural Information Processing Systems 33 (2020): 21188-21198."}, {"review_id": "l52hX4ArdI", "reviewer": "Reviewer_aRja", "summary": "The paper studies the job scheduling problem, a classic optimization challenge in networking and machine learning, using reinforcement learning (RL). Unlike prior work that trains a single RL policy, this paper proposes an ensemble of RL policies that share the same optimization objective but capture diverse and complementary solution patterns. These policies are modeled by conditioning a single neural network on distinct latent variables, enabling the approach to explore a variety of solutions and select the best one for each problem instance. Experimental evaluation on different variants of the JSP, as well as the VRP, demonstrates the effectiveness of the proposed method.", "questions": "Please check the weaknesses section above.", "limitations": "No discussion is provided in the paper. For some suggestions, please check the weaknesses section.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- JSP is a classic optimization problem. While extensively studied, there remains significant room for improvement.\n\n- The paper is well written and easy to follow.\n\n- The idea of training multiple policies that encode diverse and complementary solution patterns using a single neural network is practically relevant.\n\n- The performance evaluation is rigorous, and including results on the VRP setting is a nice added bonus.\n\nWeaknesses:\n\n- The JSP problem formulation overlooks communication aspects. It considers only processing time, ignoring communication latency. Additionally, each machine serves only one job at a time (no resource sharing), processing times are fixed and known a priori, and there is no dynamicity in the environment—no link congestion, failures, or server capacity fluctuations. These assumptions make the formulation overly abstract and less practical (for a more realistic setting, please see [1]). Could you elaborate on why these assumptions were made, and how they affect the practical applicability of your solution? Specifically, have you considered modeling communication costs? What are the challenges?\n\n- Another concern is the use of a centralized solution for a problem that is inherently distributed (as servers/machines operate across different clusters). A distributed, multi-agent approach might be more appropriate, potentially addressing the same challenges—improving exploration, generalization, and scalability. (Again, [1] serves as an example of such a distributed solution). Could you elaborate why a centralized solution is used? Any thoughts on multi-agent alternatives?\n\n[1]. https://ieeexplore.ieee.org/abstract/document/10621125", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and positive feedback! Please find our responses to the main concerns and questions below:\n\n>**W1**: More realistic constraints \n\nAs you correctly pointed out, the problems addressed in this study often overlook realistic settings such as dynamicity and communication latency, which may limit their direct practical applicability in real-world scenarios. We acknowledge this limitation of our current work. However, our primary goal is to develop a foundational framework that can be universally applied across various Job Scheduling Problems (JSP). Therefore, we initially focused our research on standard static JSPs [1], which represent the most widely studied benchmark problems in the scheduling community and serve as fundamental building blocks for the field. In this work, we have developed a novel and generalizable learning algorithm and demonstrated its superior performance, significantly outperforming existing state-of-the-art methods across various benchmarks. We strongly believe that our work establishes a solid foundation that can serve as a stepping stone toward more complex, realistic scenarios. Our future work will indeed focus on extending our approach to JSPs under realistic assumptions, including machine breakdown, communication latency, stochastic processing times, and other practical constraints. We will update the limitation section to include this perspective. Thank you for your valuable comment!\n\n[**Added**] Line 930: Additionally, we acknowledge that in this work, we only consider standard and deterministic JSPs. We need to consider more realistic constraints and dynamicity in future work to improve real-world applicability.\n\n>**W2**: Centralized method\n\nWe chose centralized architecture for the following reasons:\nAs mentioned in our response to W1, we focus on standard and static JSPs. Therefore, we adopted the problem setting that is widely used in static scheduling research from an optimization perspective. Our goal is to retain the problem setting and solution framework of prior work while developing a stronger learning method. In this setting, we assume that the scheduler (agent) has full observability over the global state, including job/machine states, and system constraints. This allows a centralized agent to make globally informed decisions. Moreover, we do not account for communication latency; accordingly, we assume that the centralized agent can perceive changes and act instantaneously.\nFinally, because our setting does not involve partial observability or asynchronous machine updates, introducing multiple agents could complicate the learning process, as such systems often suffer from coordination and communication challenges.\nHowever, we fully agree with your observation that real-world environments are inherently distributed and that a centralized agent may be unable to make real‑time decisions due to communication latency. Consequently, our current problem setting may be challenging to maintain under such conditions. Extending our work to decentralized, multi‑agent systems is an important and promising future research direction that could significantly enhance the practical applicability of our approach. We will update the limitation section to include this perspective. Thank you for your valuable comment. We would be happy to collaborate if the opportunity arises.\n\n[**Added**] Line 930: Also, given that real-world environments are inherently distributed and a centralized agent may be unable to make real time decisions due to communication latency [2], extending our work to decentralized, multi-agent systems represent an important and promising future research direction.\n\n[1] Pinedo, Michael L. Scheduling. Vol. 29. New York: Springer, 2012.\n\n[2] Blöcher, Marcel, et al. \"Train Once Apply Anywhere: Effective Scheduling for Network Function Chains Running on FUMES.\" IEEE INFOCOM 2024-IEEE Conference on Computer Communications. IEEE, 2024."}, {"review_id": "NnfCNhOPOd", "reviewer": "Reviewer_NWcr", "summary": "The paper proposes MP-ASIL (Multi-Policy with Adaptive Self-Imitation Learning), a novel framework that addresses key challenges in combinatorial optimization. Instead of using a single policy, MP-ASIL employs multiple policies sharing the same objective but developing diverse solution strategies. The framework introduces Adaptive Self-Imitation Learning to guide these policies using self-generated teaching signals efficiently. MP-ASIL overcomes previous reinforcement learning limitations by: (1) using multiple specialized policies to better represent multimodal distributions, reducing mode collapse and enhancing exploration; (2) autonomously generating training labels without requiring MDP formulations; and (3) adaptively controlling imitation intensity based on label quality. The model-agnostic approach integrates easily with existing architectures. Extensive experiments across five job scheduling problems demonstrate that MP-ASIL enhances exploration capabilities and overall performance, achieving state-of-the-art results on various datasets and outperforming leading neural solvers on other combinatorial optimization problems.", "questions": "- Page 3, line 135, Why each decision is an index from 1 to the number of total operations?\n- How Eq. (5) compares to the loss function used in GRPO [1]?\n- How is the exploration-exploitation controlled during training?\n\n[1] DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models", "limitations": "No. The authors should introduce more ablation studies to evaluate the importance of each component and hyper-parameter, such as sampling size and sampling strategies of $z$.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengthen**\n\n- Introduces latent variables to improve solution diversity, potentially reducing mode collapse and enhancing exploration efficiency.\n- Proposes a self-imitation learning framework that relies on autonomously generated training labels.\n- Extensive experiments and ablation studies demonstrate the effectiveness of the approach.\n\n**Weakness**\n\n- Theoretically, in Algorithm 1, a set of latent variables is randomly sampled for each instance at each step. If an instance is sampled multiple times, it will encounter a different set of latent variables each time. During extensive training—where each instance is sampled and trained multiple times—the model will likely disregard the contribution of these latent variables since they essentially function as random noise. Conversely, if each instance is only trained for few steps, the latent variables would become significant and might cause decision-making to approach a random policy. It would be helpful if the authors could elaborate on this issue.\n- Experimentally, some key ablation studies are missed in my opinion, e.g., 1. It would be interesting to see individual contributions of training with latent variables and sampling, namely, MP-ASIL with few sampling v.s. random policy with the same number of sampling adopted in the experiment. 2. How its performance changes as the sampling times change from a small number to a larger one.  3. How different generation policies of $z$ affect the performance?", "was_revised": true, "final_justification": "The rebuttal addresses my main concern about inference, and I agree that the latent variable can capture various solutions across different spaces. During inference, search algorithms are typically used to find a suitable latent variable for a given instance. However, I remain concerned about the computational cost during both training and inference. Particularly challenging is developing efficient search algorithms for instances with stochasticity, despite the authors' promising results. Therefore, I believe a score of 4 is fair.", "rebuttal": "We thank the reviewer for their comments and positive feedback! Please find our responses to the main concerns and questions below:\n> **W1.1**: Random noise\n\nThank you for your valuable comment. We sincerely apologize for any confusion regarding our method. We clarify why latent variables are not acting as random noise.\nIn our training procedure, sampling different latent variables for the same instance across epochs is not a weakness but a key design choice. Because, MP-ASIL does not seek to find a single “optimal” latent variable for each instance. Instead, we aim to learn a multimodal latent space for diverse policies, since multiple regions of the latent space can generate high-quality solutions for the same instance. This is crucial because Combinatorial Optimization (CO) problems often have multiple distinct solution strategies that yield the same objective value. Therefore, sampling new latent variables each time is an essential algorithmic component for learning a general multimodal policy latent space. \nIn this learning process, policy specialization is achieved through MP-ASIL's distinctive model update mechanism. At each training step, \n- We sample $k$ latent variables and generate $k$ solutions for instance $s$\n- Only the best-performing policy $\\pi(·|s, z^*)$ receives gradient updates\n- This mechanism establishes a self-reinforcing dynamic in which successful pairings are strengthened.\n\nThis joint learning process ensures that latent variables become specialized experts for specific instance sub-distributions—the latent variables evolve from random perturbations into specialized decision-making factors. This conditioning mechanism has been empirically validated in recent work [1] to produce meaningful, structured policy latent spaces rather than noise. Additionally, our ablation studies (Table 4, MP ablation) demonstrate that the latent variables contribute meaningfully to performance improvements. Furthermore, beyond performance , when we tracked the loss during the training process of the version with latent variables removed, the multi-policy approach showed lower loss values.\nIn SIL, the loss can be interpreted as the model’s confidence in its best trajectories. If the latent variables were functioning as random noise, such results would be impossible to achieve.\n\n>**W1.2**: Conversely, if each instance is only trained for few steps…\n\nAs mentioned in our response for W1.1, MP-ASIL is designed to learn a general policy latent space. That is, even if each instance is only trained for a few steps, we are not learning a one-to-one mapping, so we can share general properties from the learning of instance distributions. Therefore, it is not problematic that specific instances are only trained for a few steps. What matters is that the learned latent space encodes diverse, high-quality strategies that generalize across the problem distribution. This capability stems from deep learning's inherent strength in capturing general mappings, much like how trained neural solvers can still perform well on test instances that were not experienced during the training process. While latent variables may act like random noise in the early stages of training, we assume the standard deep learning setting where the model is fully trained until convergence. Hence, the trained model is not a random policy.\n\n>**W2.1**: Ablation study 1\n\nCould you please elaborate on what you mean by \"random policy with the same number of sampling adopted in the experiment\"? Based on our understanding, you are suggesting that we conduct the same model training process, but generate candidate solutions for training using stochastic sampling from a separate random policy rather than from the MP-ASIL-trained model.\nDue to the limited rebuttal time, we apply this approach only to PFSP and confirmed that no performance improvement was achieved compared to MP-ASIL validation performance. If our understanding of your suggestion is incorrect, we would appreciate further clarification!\n\n>**W2.2**: Ablation study 2\n\nWe analyze the effect of the number of policies ($k$) on model performance during training. We train our model under varying choices of $k$, with $k$ ∈ {32, 64, 128} for PFSP and $k$ ∈ {64, 128, 256} for JSSP. Tables 1 and 2 (below) show the results of our analysis on the TA benchmark. From the tables, we can observe that training with larger $k$ generates stronger models. This result aligns with our expectation that a larger $k$ produces a greater number of specialized behavior policies, enabling more extensive exploration of the solution space and improving the chance of finding better solutions, albeit at the cost of increased memory usage.\n\nTable 1. The effect of $k$ on PFSP.\n\n|     | PFSP 20x5 | PFSP 50x5 | PFSP 100x5 |\n|-----|-----------|-----------|------------|\n| k=32 | 0.64\\% | 0.31\\% | 0.20\\% |\n| k=64 | 0.44\\% | 0.25\\% | 0.19\\% |\n| k=128 | 0.37\\% | 0.22\\% | 0.16\\% |\n\nTable 2. The effect of $k$ on JSSP.\n\n|     | JSSP 15x15 | JSSP 20x15 | JSSP 20x20 |\n|-----|------------|------------|------------|\n| k=64 | 7.25\\% | 9.01\\% | 8.96\\% |\n| k=128 | 6.89\\% | 8.95\\% | 8.73\\% |\n| k=256 | 6.76\\% | 8.50\\% | 8.65\\% |\n\n>**W2.3**: Ablation study 3\n\nIn Appendix E.2, we evaluated models trained under three different latent distributions. In summary, although we used the distribution that performed best on the TA benchmark, all distributions demonstrated superior performance compared to the single policy approach. This finding provides evidence for the robustness and generalizability of our approach. Our method's effectiveness is not dependent on fine-tuning the latent space configuration, but rather stems from the fundamental multi-policy optimization mechanism. Please let us know if you would like any other clarification. We would be happy to provide them.\n\n>**Q1**: Page 3, line 135\n\nThank you for your valuable comment. A solution of scheduling problem can be autoregressively constructed by sequentially assigning each operation to a compatible machine and appending it to the end of that machine's operation sequence. Since we build a solution by selecting one operation per decision step, the total number of decisions equals the number of operations. In single machine scheduling problems, each job consists of exactly one operation, and our task is to determine the sequence of these operations on the machine. Since we build this sequence by selecting one operation per decision step, the total number of decisions equals the number of operations. However, in parallel machine scheduling, our task includes assigning each operation to a machine. So, the total number of decisions equals the number of operations, but, as you correctly pointed out, the expression in line 135 is imprecise because the range from 1 to $ \\mathcal{|O|}$ does not include any machine assignments. We will remove this expression in the revised manuscript to improve clarity. Thank you for your valuable feedback! This revision will help eliminate potential confusion for readers and make our problem formulation more precise.\n\n[**Removed**] Line135: where $\\tau_t \\in \\{1, \\dots, \\mathcal{|O|}\\}$ and $\\tau_t \\neq \\tau_{t'}, \\forall t \\neq t'$.\n\n>**Q2**: Compared to GRPO loss function\n\nThank you for your insightful question. Both GRPO and MP-ASIL compute normalized advantage values similarly, using the average reward over multiple sampled outputs for each instance as the baseline. However, their loss functions differ in the following key aspects:\n- GRPO is an RL-based method (PPO variant), while our method is Self-Imitation Learning (SIL)-based method. Therefore, no reward function is required.\n- GRPO's loss function focuses on single policy optimization, while MP-ASIL focuses on multi-policy optimization.\n- GRPO updates the model for all trajectories generated for the same instance. However, MP-ASIL only update the model for the best trajectory, encouraging each policy to learn specialized problem-solving strategies.\n- While both methods calculate normalized advantage values similarly, GRPO's method represents a novel approach to computing advantage values for standard PPO loss functions, whereas MP-ASIL's advantage value is introduced to dynamically control imitation intensity for the best trajectory—a novel training mechanism not utilized in existing self-imitation learning for NCO.\n\n>**Q3**: Exploration-exploitation control \n\nThank you for your informative question. In SIL, we can characterize exploration and exploitation as follows:\n- Exploration (Sampling phase): generating diverse candidate solutions\n- Exploitation (Imitation phase): Imitating the best solution found during exploration\n\nMP-ASIL extends this SIL framework with multiple policies and adaptive mechanism.\n\n- Exploration phase: $k$ diverse policies with different latent variables explore different regions of the solution space. This multi-policy approach significantly enhances exploration beyond standard single policy approaches.\n- Exploitation phase: self-imitation on the best trajectory found during exploration, with adaptive imitation intensity control that prevents over-exploitation of marginally better solutions.\n\nIn this context, exploration is controlled by the number of policies sampled during the learning process, which involves a trade-off with training time. Additionally, exploitation control is achieved through dynamic control of imitation intensity based on the quality of pseudo-labels. While we don't employ explicit ε-greedy mechanisms or entropy bonuses, the MP-ASIL framework inherently provides an exploration-exploitation balance that is well-suited for self-imitation learning.\n\n[1] Chalumeau, Felix, et al. \"Combinatorial optimization with policy adaptation using latent space search.\" Advances in Neural Information Processing Systems 36 (2023): 7947-7959."}, {"review_id": "aO31Tq82Td", "reviewer": "Reviewer_9EdW", "summary": "This paper proposes a novel self-labeling approach for combinatorial optimization problems (COPs) aimed at enhancing solution diversity. The authors tackle the challenge that a limited set of solutions can lead to suboptimal training, either due to convergence to a suboptimal policy or poor sample efficiency. To address this, they introduce MP-ASIL, which employs a multi-policy framework by conditioning in the latent space, enabling the use of a single deep neural network (DNN) to represent multiple policies. Furthermore, the authors design a loss function that weights the quality of each label based on normalized advantage weighting. MP-ASIL is evaluated on five scheduling problems and two routing problems, demonstrating superior performance over existing baselines in most cases.", "questions": "1. Would your approach also work for more complex scheduling problems, like the flexible job scheduling problem?\n2. The latent space approach seems interesting. Are there any other benefits of using it, such as adapting to other COP problems more easily?\n3. In the paper, the authors also discuss more complex objectives; however, for JSP, using the current lower bound makespan of a partial solution seems to work quite well for RL. Could the authors give a detailed example of an objective that RL could not handle but self-labeling could?", "limitations": "Most limitations are discussed; however, I would have liked a discussion about the enormous training requirements of sometimes more than a week, and the different hyperparameters used for each problem", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The paper is well written and accessible to understand. \n- The introduced concepts, such as using the latent space for multiple policies and the weighted loss function, are, to my understanding, novel for a self-labeling approach. \n- The introduced method, MP-ASIL, is well tested on multiple scheduling and routing problems and outperforms the baselines it compares to.\n\nWeaknesses:\nA major weakness of the paper is the lack of mention and comparison to other self-labeling approaches, except for SLIM. Since SLIM, other approaches were proposed, such as (Pirnay & Grimm, 2024), which also tackle the issue of solution diversity. Moreover, (Pirnay & Grimm, 2024) achieves significantly better results on JSP compared to MP-ASIL. For TSP and CVRP, it seems that MP-ASIL achieves better results, but this was hard to compare due to the limited experimentation of the authors. The authors also experimented on quite a lot of scheduling problems; however, this limits the diversity of their experiments. In the paper, the authors mention broad applicability to other CO problems, but mainly test on scheduling problems and only include limited experiments for routing problems. I would rather have seen a more diverse set of CO problems being tested, instead of five scheduling problems. \nThe authors did not include essential literature in their work, which tackles similar issues and seems to outperform them significantly. I also find the experiments lack diversity. I strongly believe the paper would significantly improve with more diverse experiments on other CO problems. Lastly, the authors also claim their approach is more sample-efficient, but I cannot find any results that support this claim; rather, I see that their training time for JSP is almost identical to SLIM, with both taking around 4 days, which disproves this. Below, I have listed more specific issues I found with the paper, and which I hope can help the authors improve their paper:\n\n- On lines 36-38, it is stated that RL struggles with effective exploration due to the use of single policies. However, the authors’ claim is only supported by limited work. I am not convinced that this is really such a big issue for RL, given that we can include an entropy bonus. I would either remove this statement or add more relevant literature that explores this problem.\n- A similar issue is found for the reward shaping claim on lines 44-48, whereby the claim is only supported by severely outdated references from before the year 2000.\n- On lines 86-88, I read that supervised learning is used for CO problems, whereby they train on small-sized instances. However, the authors also state that generating these instances is challenging. I am not convinced by this statement, because for small-scale instances it can be trivial to generate optimal solutions, depending on the problem and the scale.\n- In Eq. 5, it seems that you take the absolute value. Would this also not reward worse examples? I am not sure if this is correct, but this seems to require more explaination.\n \n\nPirnay, J., & Grimm, D. G. (2024). Self-Improvement for Neural Combinatorial Optimization: Sample Without Replacement, but Improvement. Transactions on Machine Learning Research.", "was_revised": true, "final_justification": "The authors addressed all the issues raised in my previous comments and conducted the requested additional experiments. Accordingly, I have raised my score from 3 to 4.", "rebuttal": "We thank the reviewer for their comments and positive feedback! Please find our responses to the main concerns and questions below:\n\n>**W1**: Other self-labeling approaches\n\nWe sincerely apologize for the lack of mention and comparison to other self-labeling approaches, such as Pirnay&Grimm 2024 (SI GD) [1]. We will revise the manuscript to discuss and include this comparison. However, we respectfully disagree that SI GD achieves significantly better results on job shop scheduling problems compared to MP-ASIL. SI GD employs a deep transformer network, whereas we use a simpler neural network architecture [2], and this additional model complexity may contribute their improved solution quality, limiting direct comparison. Nevertheless, on the Taillard  benchmark, MP ASIL reduced the average performance gap from 8.1% to 7.4% compared to SI GD (greedy), while delivering twice the inference speed. Similarly, against SI GD (beam 16), MP ASIL closed the gap from 7.8% to 7.4% with roughly a 10× faster runtime. SI GD with more sophisticated search surpass our performance, it incurs over 59× the computational cost.\n\n>**W2**: Diversity of experiments\n\nWe acknowledge that our experiments are mainly focused on scheduling and routing problems. However, our main contribution centers on job scheduling problems (JSPs) and we show superior performance on five JSP variants. We also demonstrated broader applicability by evaluating the TSP and ten CVRP variants, which are standard benchmarks in Neural Combinatorial Optimization (NCO) literature. Compared to previous studies, we believe that we do not cover fewer CO problems at all.\n\nDespite our extensive experimental evaluation, we fully appreciate the reviewer’s concern regarding the applicability of our method to other CO problems. The strength of our method lies in its simplicity and universality. As described in Appendix B, given any existing architecture for CO problems, one can easily apply latent conditioning and MP-ASIL to improve performance. The model-agnostic nature of MP-ASIL makes it applicable to a wide range of CO problems. For future work, we plan to apply our approach to other CO problems such as the Knapsack problem to further validate its universal applicability.\n\n>**W3**: Sample efficiency\n\nSLIM faces the challenge of low sample efficiency, as all sampled solutions except the best one are discarded during training. However, MP-ASIL leverages information from all sampled solutions through adaptive imitation intensity control, significantly improving sample efficiency. Additionally, MP-ASIL achieves comparable—or even superior—validation performance to SLIM using only 1.2× to 10× fewer training epochs. (due to the NeurIPS 2025 policy, we cannot upload images during the rebuttal phase. Therefore, we will incorporate in our revised manuscript to provide validation performance of SLIM). These empirical results demonstrate that our approach is more sample-efficient.\n\n>**W4**: On lines 36-38\n\nThank you for your informative comment. Computing the entropy over the entire trajectory remains computationally intractable, which limits the practical applicability of entropy bonus methods. Also, there are many literature that have pointed out that single policy approaches struggle with sufficient exploration [3,4,5]. We will add relevant literature as references on line 39. \n\n>**W5**: On lines 44-48\n\nThank you for your valuable feedback. We will add [2] as reference on line 46, where they stated \"RL approaches require the careful definition of a meaningful reward function, which is often a complex and challenging task\".\n\n>**W6**: On lines 86-88\n\nWe sincerely apologize for any confusion. For clarity, we believe it would be better to remove that content.\n\n[**Removed**] Line 39: However, as mentioned earlier, obtaining expert annotations for imitation is challenging.\n\n>**W7**: Eq. 5\n\nWe assume that we solve a minimization problem. So $f(\\boldsymbol{\\tau^*}, s)-mean(s) \\leq 0$ always holds. To use this difference as a non‐negative weight, we take its absolute value. However, Equation 5 can be rewritten in alternative form as follows:\n\n- $$\\mathcal{L}_{ASIL}= \\left( \\frac{f(\\boldsymbol{\\tau}^*, s) - \\textit{mean}(s)}{\\textit{std}(s)} \\right)\\frac{1}{\\mathcal{|O|}}\\sum\\_{t=1}^{\\mathcal{|O|}}\\log\\pi\\_{\\theta}\\left(\\tau^\\*\\_t | s, \\boldsymbol{\\tau}^\\*\\_{\\<t}, z^\\* \\right)$$\n\n- $$\\mathcal{L}_{ASIL}= -\\left( \\frac{\\textit{mean}(s)-f(\\boldsymbol{\\tau}^*, s)}{\\textit{std}(s)} \\right)\\frac{1}{\\mathcal{|O|}}\\sum\\_{t=1}^{\\mathcal{|O|}}\\log\\pi\\_{\\theta}\\left(\\tau^\\*\\_t | s, \\boldsymbol{\\tau}^\\*\\_{\\<t}, z^\\* \\right)$$\n\nIf you think either of the two equations is clearer than Eq. 5, we would appreciate your recommendation.\n\n> **Q1**: Flexible job shop\n\nThank you for your valuable suggestion. We conduct additional experiments by applying MP-ASIL to the DANIEL [6], a state of the art Flexible Job Shop Scheduling Problem (FJSSP) architecture and report the results in Table 1 (below). From the table, we can observe that MP-ASIL significantly outperforms all neural solvers, including DANIEL. Furthermore, on large scale instances, MP-ASIL even surpasses OR-Tools. We believe these findings further demonstrate the universal applicability and robustness of MP-ASIL across diverse CO domains.\n\nTable 1. Experiment results on FJSSP\n\n| Method | Type | 10×5 |  | 20×5 |  | 15×10 |  | 20×10 |  | 30×5 |  | 40×10 |  |\n|--------|------|------|------|------|------|-------|------|-------|------|------|------|-------|------|\n|        |      | Gap ↓ | Time ↓ | Gap ↓ | Time ↓ | Gap ↓ | Time ↓ | Gap ↓ | Time ↓ | Gap ↓ | Time ↓ | Gap ↓ | Time ↓ |\n| OR-Tools | Exact | 0.00% | (50h) | 0.00% | (50h) | 0.00% | (50h) | 0.00% | (50h) | 0.00% | (50h) | 0.00% | (50h) |\n| HGNN (S=100) | NCH | 9.66% | (1.9m) | 10.31% | (3.9m) | 12.13% | (6.6m) | 9.64% | (10.7m) | 12.36% | (21.3m) | 12.26% | (40.9m) |\n| MCGN (S=100) | NCH | 9.01% | - | 8.36% | - | 11.77% | - | 7.70% | - | 12.44% | - | 12.50% | - |\n| RS (S=100) | NCH | 7.26% | - | 7.22% | - | 9.59% | - | 6.06% | - | 11.14% | - | 11.29% | - |\n| DANIEL (S=100) | NCH | 3.57% | (1.2m) | 2.46% | (3.1m) | 6.79% | (6.5m) | 1.59% | (10.2m) | 4.43% | (20.6m) | 3.77% | (37.6m) |\n| MP-ASIL (k=100) | NCH | **3.00%** | (1.2m) | **0.67%** | (3.1m) | **4.61%** | (6.5m) | **-3.00%** | (10.3m) | **-0.15%** | (20.7m) | **-0.59%** | (37.8m) |\n\n>**Q2**: Latent space approach\n\nWe appreciate your interest in our approach. Latent conditioned policies have the advantage of easily representing multiple policies with minimal model parameter increase. Specifically, as mentioned in Appendix B, when adapting to different CO problems, latent conditioned policies can be easily implemented by concatenating latent variables to the input (hidden embeddings) of the decision-making layer, regardless of problem-specific architectures. Additionally, as described in Appendix E.1, latent conditioned policies add a fixed number of model parameters, regardless of the number of policies. This property enables flexible, efficient, easy, and scalable multiple policy representation.\n\n> **Q3**: More complex objectives\n\nFor JSSP with makespan objective, the difference between the makespan lowerboud before and after making a decision as a reward is widely used. However, this reward function only considers the precedence relationships of operations to calculate the lower bound, leading to estimation error accumulation, which hinders accurate guidance for the scheduling process. Moreover, for problems without precedence relationships, it is impossible to estimate tight lower bound using this approach.\nWhen considering total total tardiness objectives, another popular performance measure, the influence of an early scheduling decision is delayed. Intuitively, one might set the immediate reward to be the negative tardiness of the job scheduled. However, even if that job has zero tardiness it is scheduled, we cannot account for how this choice will affect the tardiness of all subsequent jobs—yet the reward remains zero. This zero‐reward signal provides no differentiation between actions that will later incur large penalties and those that will not, making accurate credit assignment impossible.\n\n> **L**: Training requirements and the different hyperparameters\n\nFor each problem, we use the same training hyperparameters from the original papers. Our experimental results demonstrate that simply applying MP-ASIL without hyperparameter tuning achieves significantly improved performance with approximately the same training time, which we respectfully believe is a strength of our approach. This demonstrates the practical value and ease of adoption of our method - practitioners can integrate MP-ASIL into existing frameworks without extensive hyperparameter optimization or architectural modifications.\n\n[1] Pirnay, Jonathan, and Dominik G. Grimm. \"Self-improvement for neural combinatorial optimization: Sample without replacement, but improvement.\" arXiv preprint arXiv:2403.15180 (2024).\n\n[2] Corsini, Andrea, et al. \"Self-labeling the job shop scheduling problem.\" Advances in Neural Information Processing Systems 37 (2024): 105528-105551.\n\n[3] Grinsztajn, Nathan, et al. \"Winner takes it all: Training performant rl populations for combinatorial optimization.\" Advances in Neural Information Processing Systems 36 (2023): 48485-48509.\n\n[4] Chalumeau, Felix, et al. \"Combinatorial optimization with policy adaptation using latent space search.\" Advances in Neural Information Processing Systems 36 (2023): 7947-7959.\n\n[5] Hottung, André, Mridul Mahajan, and Kevin Tierney. \"PolyNet: Learning diverse solution strategies for neural combinatorial optimization.\" arXiv preprint arXiv:2402.14048 (2024).\n\n[6] Wang, Runqing, et al. \"Flexible job shop scheduling via dual attention network-based reinforcement learning.\" IEEE Transactions on Neural Networks and Learning Systems 35.3 (2023): 3091-3102."}]

Author rebuttal:

Meta-review: This paper introduces a multi-policy optimization method that that uses an adaptive self-imitation learning mechanism for job scheduling problems.

The reviewers generally found that the paper paper is well-written, addresses a practical problem, and presents an interesting approach to multi-policy optimization. They also appreciated the extensive experimental results. Although there were a few concerns regarding comparisons to other methods, the practicality of the problem formulation, and requests for further ablation studies and more diverse benchmarks. The authors addressed them with additional experiments during the rebuttal period, which includes adding a Genetic Programming baseline, evaluating their method on the complex stochastic and deterministic Flexible Job Shop Scheduling Problem, and providing new analysis on inference-time search strategies. As a result, all of the reviewers converged on a positive recommendation for the paper.  Thus, I recommend acceptance.
Decision: Accept (poster)