2385. Effective Large Neighborhood Search for Flexible Job Scheduling via Neural Deconstruction
Invited abstract in session WE-12: AI in Optimization Heuristics, stream Artificial Intelligence, Machine Learning and Optimization.
Wednesday, 16:30-18:00Room: H10
Authors (first author is the speaker)
| 1. | Davide Zago
|
| Computer Science, University of Turin | |
| 2. | André Hottung
|
| Decision and Operation Technologies, Bielefeld University | |
| 3. | Fynn Martin Gilbert
|
| Decision and Operation Technologies, Bielefeld University | |
| 4. | Rossella Cancelliere
|
| University of Turin | |
| 5. | Kevin Tierney
|
| Business Decisions and Analytics, University of Vienna |
Abstract
End-to-end machine learning has provided impressive results on several combinatorial problems, consistently shrinking the gap with traditional approaches used in operations research, and showing potential applicability in the industrial world. Meanwhile, there has been an increasing number of learning metaheuristics with successful applications to different domains. In particular, neural deconstruction in large neighborhood search recently came out as the first machine learning approach to surpass traditional methods on routing problems. In this work, we apply the rationale behind this technique to two largely addressed scheduling tasks, i.e. standard and flexible job-shop problems. To account for alternative assignments of operations to machines, we propose a novel extension of the well-known disjunctive graph representation. Our trained models outperform end-to-end and search-based methods and closely match traditional approaches, needing limited domain-specific knowledge. Our results enforce the effectiveness of neural deconstruction search, and demonstrate its potential to a wider range of combinatorial problems.
Keywords
- Combinatorial Optimization
- Machine Learning
- Scheduling
Status: accepted
Back to the list of papers