Bridging Reinforcement Learning and Planning to Solve Combinatorial Optimization Problems with Nested Sub-Tasks

• DOI: 10.26599/air.2023.9150025
• Publication Date: 2024-01-05T06:05:02Z
• Authors: Xiaohan Shan; Pengjiu Wang; Mingda Wan; Dong Yan; Jialian Li; Jun Zhu
• Keywords: reinforcement learning; Electronic computers. Computer science; job-shop scheduling problem; 0211 other engineering and technologies; 0202 electrical engineering, electronic engineering, information engineering; combinatorial optimization; QA75.5-76.95

Combinatorial Optimization (CO) problems have been intensively studied for decades with a wide range of applications. For some classic CO problems, e.g., the Traveling Salesman Problem (TSP), both traditional planning algorithms and emerging reinforcement learning made solid progress in recent years. However, nested sub-tasks, neither end-to-end nor evolutionary methods can obtain satisfactory strategies within limited time computational resources. In this paper, we propose an algorithmic framework solving which be combined modular way. We validate our Job-Shop Scheduling (JSSP), experimental results show that algorithm has good performance solution qualities model generalizations.