A Tabu Search-based Memetic Algorithm for the Multi-objective Flexible Job Shop Scheduling Problem

In this paper we propose a tabu search-based memetic algorithm (TSM) for the multi-objective flexible job shop scheduling problem (FJSSP), with the objectives to minimize the makespan, the total workload and the critical workload. The problem is addressed in a Pareto manner, which targets a set of Pareto optimal solutions. The novelty of our method lies in the use of tabu search (TS) as the local search method as well as a mutation operator and the use of the hypervolume indicator to avoid stagnation by increasing the flow of individuals in the local search. To the best of our knowledge, the use of TS in the context of multi-objective FJSSP has not been reported so far. We apply our algorithm on well known test instances and compare our results to state-of-the art algorithms. The results show that our approach yields competitive solutions in 6 of the 10 instances against two of their algorithms proving that the use of TS as a local search method can provide competitive results.