A REINFORCEMENT LEARNING APPROACH FOR SCHEDULING PROBLEMS

Abstract

Scheduling problems are an important class of sequencing problems that can be found in many real life situations, especially in the
field of production planning. The problem considered in this work is to find a permutation of operations to be sequentially processed on a number of machines under the restriction that the processing of each job has to be continuous with respect to the objective of minimizing the completion time of all jobs, known in literature as makespan or Cmax. This problem is as NP-hard, it is typical of combinatorial optimization and can be found in manufacturing environments, where there are conventional machines- tools and different types of pieces which can, in some scenarios, share the same route or not. The following research presents a Reinforcement Learning algorithm known as Q-Learning to solve scheduling problems, specifically Job Shop and Flow Shop. This algorithm is based on learning an action-value function that gives the expected utility of taking a given action in a given state, where an agent is associated to each of the resources. To validate the quality of the solutions, test cases of the specialized literature are used and the results obtained were compared with the reported optimal results.