Solving the flexible job shop problem by hybrid metaheuristics-based multiagent model

Subject Areas : Mathematical Optimization

Houssem Eddine Nouri ¹ , Olfa Belkahla Driss ² , Khaled Ghe´dira ³

1 - SOIE-COSMOS, École Nationale des Sciences de l’Informatique, Université de la Manouba, Tunis, Tunisia|Institut Supérieur de Gestion de Tunis, Université de Tunis, Bardo, Tunis, Tunisia
2 - École Supérieure de Commerce de Tunis, Université de la Manouba, Tunis, Tunisia|SOIE-COSMOS, École Nationale des Sciences de l’Informatique, Université de la Manouba, Tunis, Tunisia
3 - SOIE-COSMOS, École Nationale des Sciences de l’Informatique, Université de la Manouba, Tunis, Tunisia|Institut Supérieur de Gestion de Tunis, Université de Tunis, Bardo, Tunis, Tunisia

Received: 2020-10-06 Accepted : 2020-10-06 Published : 2018-03-01

Keywords: Scheduling . Flexible job shop . Genetic algorithm . Local search. Holonic multiagent . Hybrid metaheuristics,

Abstract :

The flexible job shop scheduling problem (FJSP) is a generalization of the classical job shop scheduling problem that allows to process operations on one machine out of a set of alternative machines. The FJSP is an NP-hard problem consisting of two sub-problems, which are the assignment and the scheduling problems. In this paper, we propose how to solve the FJSP by hybrid metaheuristics-based clustered holonic multiagent model. First, a neighborhood-based genetic algorithm (NGA) is applied by a scheduler agent for a global exploration of the search space. Second, 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 NGA final population. The efficiency of our approach is explained by the flexible selection of the promising parts of the search space by the clustering operator after the genetic algorithm process, and by applying the intensification technique of the tabu search allowing to restart the search from a set of elite solutions to attain new dominant scheduling solutions. Computational results are presented using four sets of well-known benchmark literature instances. New upper bounds are found, showing the effectiveness of the presented approach.