Optimization of Job Tardiness for Job Shop Scheduling Problem Using Reinforcement Learning

Job shop scheduling problems are complex and classified as combinatorial optimization problems. Dispatching rules are often used to solve these problems but they do not guarantee optimal solutions. Moreover, combining different dispatching rules for the same problem proved to be more effective than using only one rule for all decisions of the problem. Several approaches raised in the last years such as machine learning, and particularly Reinforcement Learning (RL) which are based on an agent that takes optimization actions by observing the environment. In this work, we implement this RL type of algorithm, particularly Q-learning to optimize the number of tardy jobs in Job Shop environments. The proposed implementation is based on a new representation of the states of the environment and an adapted reward function to the objective function. Actions taken by the agent consist of selecting one of the available dispatching rules at each decision. The results of the algorithm show a better performance and convergence than single dispatching rules.