4.5 Article

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

期刊

APPLIED INTELLIGENCE
卷 52, 期 1, 页码 141-153

出版社

SPRINGER
DOI: 10.1007/s10489-021-02406-2

关键词

Job shop scheduling; Metaheuristics; Hybrid algorithms; Diversity management; Parallel optimizers

资金

  1. CONACyT [285599]
  2. Laboratorio de Supercomputo del Bajio through CONACyT [300832]

向作者/读者索取更多资源

Recent advances in the field of memetic algorithms show that explicitly managing the diversity of the population is crucial for the success of solving the job shop scheduling problem. This paper proposes a novel memetic algorithm that integrates advanced components and a replacement strategy to manage diversity, resulting in significant improvements compared to state-of-the-art optimizers. The parallel proposal achieves new best-known solutions in 30 well-known JSSP instances.
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.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.5
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据