Research map / Label-efficient and robust learning / Self-supervised and contrastive

Self-Labeling the Job Shop Scheduling Problem

NeurIPS 2024 · Label-efficient and robust learning › Self-supervised and contrastive · approach: Self-supervision in supervised pipelines · 4 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes SLIM, a self-supervised self-labeling method that trains a Pointer-Network-style generative graph model for job shop scheduling by using the best of multiple sampled solutions (min makespan) as a pseudo-label, and shows it also works for TSP.

Problem

Training neural constructive solvers for combinatorial problems like the Job Shop Scheduling Problem without costly optimal target solutions from exact solvers or the RL reward formulation.

Approach

Sample multiple solutions from a generative autoregressive model, take the best one according to the problem objective (minimum makespan) as a pseudo-label, and train with cross-entropy on it, iterating to improve generation without any optimality information or MDP formulation.

Key results

• On Taillard's benchmark, the SLIM-trained model with 512 sampled solutions achieves an average PG of 7.8% versus 10.5% for CL and 14.5% for the best randomized PDR (MOR), and beats MIP (8.4%) on the Taillard benchmark average.
• On Demirkol's benchmark, the 512-sample model achieves average PG 13.1% versus 19.0% for CL (greedy-comparable setting; Demirkol results for CL are reported only as greedy and randomized partial values).
• On very large instances (200x20 to 500x40), the model with 512 samples produces lower average makespan than CP-Sat with 3600 s on 4 shapes while taking 31-343 s.

Measured effects reported in the paper

Surprising findings

• Training with SLIM and sampled solutions gives results competitive with or better than PPO-trained training under the same hyper-parameters, with faster convergence.
• The model trained with SLIM produces a TSP model comparable to POMO20 after just one epoch.

Limitations

• Only one sampled solution per training instance updates the model, which may be sample-inefficient.
• Sampling many solutions requires substantial memory, limiting batch size.
• As a constructive approach it still lags behind state-of-the-art CP solvers and metaheuristics on the benchmarks.

Experimental setup

Datasets: randomly generated JSP instances (30,000) Taillard benchmark Demirkol benchmark Lawrence benchmark TSPLIB random TSP-20 instances

Benchmarks: Taillard Demirkol Lawrence TSPLIB very large JSP instances (200x20 to 500x40)

Metrics: percentage gap execution time average makespan

Baselines: L2D CL INSA SPT MWR MOR SBH NLS_A L2S Gurobi MIP CP-Sat PPO

Builds on: Pointer Network Graph Attention Network Cross-Entropy Method POMO Attention Model

Closest papers by meaning

• Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · similarity 0.86)
• Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction (ICML 2025 · similarity 0.85)
• Neural Combinatorial Optimization for Stochastic Flexible Job Shop Scheduling Problems (AAAI 2025 · similarity 0.84)
• BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization (ICML 2025 · similarity 0.84)
• GOAL: A Generalist Combinatorial Optimization Agent Learner (ICLR 2025 · similarity 0.83)
• Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.83)