Multi-Agent Model based on Tabu Search for the Permutation Flow Shop Scheduling Problem

摘要

The objective of this work is to present a distributed approach for the problem of finding a minimum makespan in the permutation flow shop scheduling problem. The problem is strongly NP-hard and its resolution optimally within a reasonable time is impossible. For these reasons we opted for a Multi-agent architecture based on cooperative behaviour allied with the Tabu Search meta-heuristic. The proposed model is composed of two classes of agents: Supervisor agent, responsible for generating the initial solution and containing the Tabu Search core, and Scheduler agents which are responsible for the satisfaction of the constraints under their jurisdiction and the evaluation of all the neighborhood solutions generated by the Supervisor agent. The proposed approach has been tested on different benchmarks data sets and results demonstrate that it reaches high-quality solutions.