An Asynchronous Reinforcement Learning Hyper-Heuristic Algorithm for Flow Shop Problem

Wen Shi, Xueyan Song, Cuiling Yu, and Jizhou Sun


Agentbased and Multiagent Systems, Machine Learning, Permutation Flow Shop Scheduling, Hyperheuristic


This paper investigates a hyper-heuristic algorithm for the permutation flow shop problem(FSP) to find a sequence to minimize the makespan. In comparison with existing approaches, our proposed hyper-heuristic algorithm based on multi-agent architecture includes two levels: low level heuristic agents(LLHAs) do local search in the solution domain and hyper-heuristic agent(HHA) manages low level heuristic agents with reinforcement learning. The LLHAs improve the current solution by local search and send it to the HHA. Depending on the last few performances of LLHAs, the HHA decide whether or not to accept the current received solution as an initial solution for the next local search. Simulation studies demonstrate that the hyper-heuristic with asynchronous parallel reinforcement learning yields better solutions than other algorithms.

Important Links:

Go Back