ACTION SPACE REDUCTION IN REINFORCEMENT LEARNING USING THE MAXIMUM WIDTH OF THE OPERATION GRAPH FOR FLEXIBLE SCHEDULING PROBLEMS

Abstract

The paper addresses approach of action space reduction in reinforcement learning for flexible scheduling. The relevance of the study is determined by the large number of operation-machine alternatives in scheduling environments, where only a limited subset of actions is feasible at each decision step. This creates redundant action evaluation and increases inference computational cost. The objective of the paper is to evaluate whether feasibility-aware action processing can improve the quality and inference time trade-off of reinforcement learning policies for scheduling. Three variants are compared: a three-branch MLP baseline (BR), a branch-aware scheduling policy with candidate action scoring (BASP), and BASP Sparse with feasibility-aware reduced action-space evaluation. The experiments are conducted on Brandimarte and Behnke benchmark instances. Schedule quality is measured by relative makespan reduction with respect to BR, while inference efficiency is evaluated by inference-time ratios. The results show that BASP improves makespan but increases inference time compared with BR. BASP Sparse preserves most of the quality gain while significantly improving inference efficiency. On Brandimarte groups, BASP Sparse achieves up to 5.95% makespan reduction and up to 2.21 speedup relative to BASP. On the larger Behnke group, it achieves 28.21% makespan reduction and 3.18 speedup relative to BASP. The results indicate that proposed action space reduction approach becomes especially beneficial for larger scheduling instances.