A Reinforcement Learning Approach to job-shop Scheduling

Abstract

We apply reinforcement learning methods to learn domain-specific heuristics for job shop scheduling. A repair-based scheduler starts with a critical -path schedule and incrementally repairs const ra int violations with the goal of finding a s hort conflict-free schedule. The temporal difference al gorithm TD(>..) is applied to train a neural network to learn a heuristic evaluation function over states. This evaluation function is used by a one-step lookahead search procedure to find good solutions to new scheduling problems. We evalu ate t his approach on sy nth etic problems and on problems from a NASA space shuttle payload processing tas k. The evalu ation function is trained on problems involving a small numb er of jobs and then tested on larger problems. The TD scheduler performs better t h an the best known existing algorithm for this task-Zweben 's iterative repair method based on si mul ated ann ea ling. The results suggest that reinforcement learning can provide a new method for constructing high-performance scheduling systems.