Reward Calculation in Real-Time Scheduling Based on Simulation and Q-learning

The precondition for reinforcement learning to solve real-time scheduling problems is that the defined reward function must guarantee that the objective of the scheduling is achieved while the cumulated reward is maximized in the algorithm. This requires that the reward function must directly derive from the objective. Since jobs are unknown in real-time scheduling, an overall objective is not able to know before the concerned time horizon ends. As a substitute, the whole horizon is divided into several small periods. A period-wide objective is calculated after each period. It is considered to be the collective reward of the decisions in the period. Then the collective reward is distributed to every decision in this period. The value function will be updated according to these individual rewards. Based on this idea, five methods are proposed to distribute the reward and evaluated by experiments in a single-machine model.