A multi-objective memetic algorithm for the job-shop scheduling problem

Abstract

Planning means, in the realm of production activities, to design, coordinate, manage and control all the operations involved in the production system. Many MOPs (Multi-Objective Optimization Problems) are generated in this framework. They require the optimization of several functions that are usually very complex, which makes the search for solutions very expensive. Multi-objective optimization seeks Pareto-optimal solutions for these problems. In this work we introduce, a Multi-Objective Memetic Algorithm intended to solve a very important MOP in the field, namely, the Job-Shop Scheduling Problem. The algorithm combines a MOEA (Multi-Objective Evolutionary Algorithm) and a path-dependent search algorithm (Multi-Objective Simulated Annealing), which is enacted at the genetic phase of the procedure. The joint interaction of those two components yields a very efficient procedure for solving the MOP under study. In order to select the appropriate MOEA both NSGAII and SPEAII as well as their predecessors (NSGA and SPEA) are pairwise tested on problems of low, medium and high complexity. We find that NSGAII yields a better performance, and therefore is the MOEA of choice.