A parallel memetic algorithm with explicit management of diversity for the job shop scheduling problem

摘要

The job shop scheduling problem (JSSP) is a very popular NP-hard optimization problem that involves assigning jobs to resources. Recent advances in the field of memetic algorithms show that explicitly managing the diversity of the population by taking into account the stopping criterion with the aim of dynamically adapting the balance between exploration and exploitation is key to their success. This is especially the case in long-term executions. However, this design principle has not yet been applied to the JSSP. This paper proposes a novel memetic algorithm that integrates some of the most advanced components devised in the literature for the JSSP with a replacement strategy that explicitly manages the diversity by considering a novel dissimilarity measure. To properly address large instances, a parallel master-worker model is used. Experimental validation shows the important advances attained by our proposal when compared to two state-of-the-art optimizers. The advantages are clear in both sequential and parallel cases, with more impressive achievements appearing in the parallel case. The parallel proposal has yielded new best-known solutions in 30 well-known JSSP instances, matching the lower bound in two of them, meaning that at least two new optimal solutions have been discovered.