EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
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:00Room: 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
- Scheduling
- Artificial Intelligence
- Computer Science/Applications
Status: accepted
Back to the list of papers