A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems
There hardly exists a general solver that is efficient for scheduling problems due to their diversity and complexity. In this study, we develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together to efficiently deal with complex scheduling problems. The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively. This offers a novel and general paradigm that combines RL with OR approaches to solving scheduling problems, which leverages the respective strengths of RL and OR: The MDP narrows down the search space of the original problem through an RL method, while the mixed-integer programming process is settled by an OR algorithm. These two stages are performed iteratively and interactively until the termination criterion has been met. Under this idea, two implementation versions of the combination methods of RL and OR are put forward. The agile Earth observation satellite scheduling problem is selected as an example to demonstrate the effectiveness of the proposed scheduling framework and methods. The convergence and generalization capability of the methods are verified by the performance of training scenarios, while the efficiency and accuracy are tested in 50 untrained scenarios. The results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems. In addition, it can be found that RL-based optimization algorithms have stronger scalability than non-learning algorithms. This work reveals the advantage of combining reinforcement learning methods with heuristic methods or mathematical programming methods for solving complex combinatorial optimization problems.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationEarth Observationreinforcement-learningReinforcement Learning (RL)SchedulingSimilar Papers 제목 키워드 기반
RL-ABC: Reinforcement Learning for Accelerator Beamline Control
Particle accelerator beamline optimization is a high-dimensional control problem traditionally requiring significant expert intervention. We present RLABC (Reinforcement Learning for Accelerator Beamline Control), an ope…
Reinforcement LearningUnlearning Works Better Than You Think: Local Reinforcement-Based Selection of Auxiliary Objectives
We introduce Local Reinforcement-Based Selection of Auxiliary Objectives (LRSAO), a novel approach that selects auxiliary objectives using reinforcement learning (RL) to support the optimization process of an evolutionar…
Reinforcement Learning (RL)Environment Upgrade Reinforcement Learning for Non-Differentiable Multi-Stage Pipelines
Recent advances in multi-stage algorithms have shown great promise, but two important problems still remain. First of all, at inference time, information can't feed back from downstream to upstream. Second, at training t…
Instance SegmentationPose Estimationreinforcement-learningReinforcement Learning+2Hybrid Adversarial Imitation Learning
Extrapolating beyond-demonstrator (BD) performance through the imitation learning (IL) algorithm aims to learn from and outperform the demonstrator. Most existing BDIL algorithms are performed in two stages by first infe…
Imitation LearningReinforcement Learning (RL)Hysteresis-Based RL: Robustifying Reinforcement Learning-based Control Policies via Hybrid Control
Reinforcement learning (RL) is a promising approach for deriving control policies for complex systems. As we show in two control problems, the derived policies from using the Proximal Policy Optimization (PPO) and Deep Q…
reinforcement-learningReinforcement Learning (RL)