EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3043. Self-Labeling the Job Shop Scheduling Problem

Invited abstract in session WB-60: Job shop scheduling, stream Project Management and Scheduling.

Wednesday, 10:30-12:00
Room: S09 (building: 101)

Authors (first author is the speaker)

1. Andrea Corsini
Department of Science and Methods for Engineering, University of Modena and Reggio Emilia
2. Mauro Dell'Amico
DISMI, Università degli Studi di Modena e Reggio Emilia

Abstract

The Job Shop Problem (JSP) involves scheduling sequences of operations (jobs) on machines by minimizing the makespan [1]. Our novel approach tackles the JSP as a sequence of decisions, nicely represented by a branch-decision tree. At each decision node, we explore all the job selections for scheduling the next operation.
We use an encoder-decoder architecture [2], where the Graph encoder creates embeddings for operations from the disjunctive graph of JSP instances, and the decoder generates solutions by producing at each decision node a probability of picking each job from these embeddings. Given the high cost and expertise needed for applying Supervised and Reinforcement Learning, we propose a simpler Self-Labeling training strategy, which constructs multiple solutions and uses the best one as a self-generated label to refine the model.
Our model outperforms Constructive Heuristics [1] and Reinforcement Learning approaches [3], with up to 20% reduction in optimality gaps, and also surpasses a disjunctive Mathematical Programming model on benchmark instances.

[1] M. Pinedo, Scheduling: Theory, Algorithms, and Systems, New York Springer, 2016.
[2] O. Vinyals et al. Pointer Networks, Advances in neural information processing systems, 2015.
[3] P. Tassel et al An End-to-End Reinforcement Learning Approach for Job-Shop Scheduling Problems Based

Keywords

Status: accepted

Back to the list of papers