This paper introduces a novel self-supervised training strategy, called Self-Labeling Improvement Method (SLIM), designed for combinatorial problems, particularly the Job Shop Scheduling (JSP) problem. SLIM leverages generative models to train without the need for costly target solutions, which are often produced by exact solvers. The method uses multiple solutions generated by the model and selects the best one based on the problem objective as a pseudo-label. This iterative process improves the model's generation capability, eliminating the need for optimality information. The effectiveness of SLIM is demonstrated on the JSP, where it outperforms both constructive heuristics and state-of-the-art learning approaches. The generative model used is based on the Pointer Network, and experiments on popular benchmarks show that SLIM is robust and effective across various training regimes. Additionally, SLIM is applied to the Traveling Salesman Problem (TSP) to demonstrate its broader applicability. The key contributions of this work include the introduction of SLIM and an efficient encoder-decoder architecture for generating parallel solutions in the JSP.This paper introduces a novel self-supervised training strategy, called Self-Labeling Improvement Method (SLIM), designed for combinatorial problems, particularly the Job Shop Scheduling (JSP) problem. SLIM leverages generative models to train without the need for costly target solutions, which are often produced by exact solvers. The method uses multiple solutions generated by the model and selects the best one based on the problem objective as a pseudo-label. This iterative process improves the model's generation capability, eliminating the need for optimality information. The effectiveness of SLIM is demonstrated on the JSP, where it outperforms both constructive heuristics and state-of-the-art learning approaches. The generative model used is based on the Pointer Network, and experiments on popular benchmarks show that SLIM is robust and effective across various training regimes. Additionally, SLIM is applied to the Traveling Salesman Problem (TSP) to demonstrate its broader applicability. The key contributions of this work include the introduction of SLIM and an efficient encoder-decoder architecture for generating parallel solutions in the JSP.