关键词: 调度, 平行机, 增强学习, 马尔可夫决策过程

Abstract: A Reinforcement Learning (RL) method, R-Learning, was used to study parallel machines scheduling problems which was aimed to minimize mean flow time of jobs. The scheduling problem was converted into Semi-Markov Decision Process(SMDP) by defining system state, actions and reward function. It was solved by R-Learning functions. A heuristic, Ranking Algorithm (RA) was proposed and defined as RL as well as two commonly used dispatching rules: Shortest Expected Processing Time (SEPT) and First In First Out (FIFO). Experiment results demonstrated that R-Learning could learn a near-optimal scheduling policy through simulation, i.e. to select optimal or sub-optimal actions at different states. The conclusion was that R-Learning was superior to the above heuristic rules in all test problems.

Key words: scheduling, parallel machines, reinforcement learning, Markov decision process