Genetic Algorithm Combined with Tabu Search in a Holonic Multiagent Model for Flexible Job Shop Scheduling Problem

摘要

The Flexible Job Shop scheduling Problem (FJSP) is an extension of the classical Job Shop scheduling Problem (JSP) presenting an additional difficulty caused by the operation assignment problem on one machine out of a set of alternative machines. The FJSP is an NP-hard problem composed by two complementary problems, which are the assignment and the scheduling problems. In this paper, we propose a combination of a genetic algorithm with a tabu search in a holonic multiagent model for the FJSP. In fact, firstly, a scheduler agent applies a genetic algorithm for a global exploration of the search space. Then, secondly, a local search technique is used by a set of cluster agents to guide the research in promising regions of the search space and to improve the quality of the final population. To evaluate our approach, numerical tests are made based on two sets of well known benchmark instances in the literature of the FJSP: Kacem and Brandimarte. The experimental results show that our approach is efficient in comparison to other approaches.