Adaptive Bias Generalized Rollout Policy Adaptation on the Flexible Job-Shop Scheduling Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908371917996032 |
|---|---|
| author | Kobrosly, Lotfi Graviers, Marc-Emmanuel Coupvent des Guettier, Christophe Cazenave, Tristan |
| author_facet | Kobrosly, Lotfi Graviers, Marc-Emmanuel Coupvent des Guettier, Christophe Cazenave, Tristan |
| contents | The Flexible Job-Shop Scheduling Problem (FJSSP) is an NP-hard combinatorial optimization problem, with several application domains, especially for manufacturing purposes. The objective is to efficiently schedule multiple operations on dissimilar machines. These operations are gathered into jobs, and operations pertaining to the same job need to be scheduled sequentially. Different methods have been previously tested to solve this problem, such as Constraint Solving, Tabu Search, Genetic Algorithms, or Monte Carlo Tree Search (MCTS). We propose a novel algorithm derived from the Generalized Nested Rollout Policy Adaptation, developed to solve the FJSSP. We report encouraging experimental results, as our algorithm performs better than other MCTS-based approaches, even if makespans obtained on large instances are still far from known upper bounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_08451 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Adaptive Bias Generalized Rollout Policy Adaptation on the Flexible Job-Shop Scheduling Problem Kobrosly, Lotfi Graviers, Marc-Emmanuel Coupvent des Guettier, Christophe Cazenave, Tristan Artificial Intelligence The Flexible Job-Shop Scheduling Problem (FJSSP) is an NP-hard combinatorial optimization problem, with several application domains, especially for manufacturing purposes. The objective is to efficiently schedule multiple operations on dissimilar machines. These operations are gathered into jobs, and operations pertaining to the same job need to be scheduled sequentially. Different methods have been previously tested to solve this problem, such as Constraint Solving, Tabu Search, Genetic Algorithms, or Monte Carlo Tree Search (MCTS). We propose a novel algorithm derived from the Generalized Nested Rollout Policy Adaptation, developed to solve the FJSSP. We report encouraging experimental results, as our algorithm performs better than other MCTS-based approaches, even if makespans obtained on large instances are still far from known upper bounds. |
| title | Adaptive Bias Generalized Rollout Policy Adaptation on the Flexible Job-Shop Scheduling Problem |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2505.08451 |