Neural Combinatorial Optimization for Stochastic Flexible Job Shop Scheduling Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916531037798400 |
|---|---|
| author | Smit, Igor G. Wu, Yaoxin Troubil, Pavel Zhang, Yingqian Nuijten, Wim P. M. |
| author_facet | Smit, Igor G. Wu, Yaoxin Troubil, Pavel Zhang, Yingqian Nuijten, Wim P. M. |
| contents | Neural combinatorial optimization (NCO) has gained significant attention due to the potential of deep learning to efficiently solve combinatorial optimization problems. NCO has been widely applied to job shop scheduling problems (JSPs) with the current focus predominantly on deterministic problems. In this paper, we propose a novel attention-based scenario processing module (SPM) to extend NCO methods for solving stochastic JSPs. Our approach explicitly incorporates stochastic information by an attention mechanism that captures the embedding of sampled scenarios (i.e., an approximation of stochasticity). Fed with the embedding, the base neural network is intervened by the attended scenarios, which accordingly learns an effective policy under stochasticity. We also propose a training paradigm that works harmoniously with either the expected makespan or Value-at-Risk objective. Results demonstrate that our approach outperforms existing learning and non-learning methods for the flexible JSP problem with stochastic processing times on a variety of instances. In addition, our approach holds significant generalizability to varied numbers of scenarios and disparate distributions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_14052 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Neural Combinatorial Optimization for Stochastic Flexible Job Shop Scheduling Problems Smit, Igor G. Wu, Yaoxin Troubil, Pavel Zhang, Yingqian Nuijten, Wim P. M. Artificial Intelligence Machine Learning Optimization and Control Neural combinatorial optimization (NCO) has gained significant attention due to the potential of deep learning to efficiently solve combinatorial optimization problems. NCO has been widely applied to job shop scheduling problems (JSPs) with the current focus predominantly on deterministic problems. In this paper, we propose a novel attention-based scenario processing module (SPM) to extend NCO methods for solving stochastic JSPs. Our approach explicitly incorporates stochastic information by an attention mechanism that captures the embedding of sampled scenarios (i.e., an approximation of stochasticity). Fed with the embedding, the base neural network is intervened by the attended scenarios, which accordingly learns an effective policy under stochasticity. We also propose a training paradigm that works harmoniously with either the expected makespan or Value-at-Risk objective. Results demonstrate that our approach outperforms existing learning and non-learning methods for the flexible JSP problem with stochastic processing times on a variety of instances. In addition, our approach holds significant generalizability to varied numbers of scenarios and disparate distributions. |
| title | Neural Combinatorial Optimization for Stochastic Flexible Job Shop Scheduling Problems |
| topic | Artificial Intelligence Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2412.14052 |