Genetic reinforcement learning approach to the heterogeneous machine scheduling problem

摘要

Focuses on the development of a learning-based heuristic for scheduling heterogeneous machines. Although list scheduling methods have been widely used for a large class of scheduling problems, including the heterogeneous machine scheduling problem, they involve designing priority rules, which usually require a fair amount of insights on the characteristics of the problem to be solved. Instead of elaborate design of priority rules in a single step, we propose an iterative list scheduling process, which refines priority rules while generating a number of schedules. The proposed iterative list scheduling is formulated as a reinforcement learning problem, with states and actions defined in list scheduling. Due to the large number of possible states, reinforcement learning algorithms which use value functions in constructing an optimal policy may not be suitable for scheduling problems. Thus, to directly work with policies rather than the values of states, we propose genetic reinforcement learning (GRL), in which the policies of reinforcement learning are encoded into the chromosomes of genetic algorithms and a near-optimal policy is searched for by genetic algorithms. A GRL-based scheduler, called evolutionary intracell scheduler (EVIS), has been developed and applied to various scheduling problems such as the heterogeneous machine scheduling, the processor scheduling, the job-shop scheduling, the flow-shop scheduling, and the open-shop scheduling problems. The proposed model of EVIS, which has a linear order of population-fitness convergence, is verified by computer experiments. Even without fine tuning EVIS, the quality of solutions achieved by EVIS is comparable to that of problem-tailored heuristics for most of the problem instances.