Real-time job shop scheduling based on simulation and Markov decision processes

Abstract

Real-time job shop scheduling is a sequential decision making problem. The main task is to decide which job in a queue should be processed next. The problem can be modeled as a Markov decision process. Jobs in the queue form an action set. Selecting one job to process is regarded as taking an action from the set. A dummy action, which means no job will be selected and the machine will keep idle, is also contained in the set. This removes the no-delay restriction from the problem. The reward function comprises the critical ratio of the selected job and the global job holding cost. Two algorithms, simulation-based value iteration and simulation-based Q-learning, are introduced to solve the scheduling problem from the perspective of a Markov decision process. The simulation explores the state space and accomplishes state transitions. The value function is parameterized and estimated by using a feedforward neural network.