4.7 Article

A cooperative coevolutionary algorithm approach to the no-wait job shop scheduling problem

期刊

EXPERT SYSTEMS WITH APPLICATIONS
卷 194, 期 -, 页码 -

出版社

PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.eswa.2022.116498

关键词

Scheduling; No-wait; Job shop; Makespan; Cooperative coevolutionary; Genetic algorithm; Timetabling

资金

  1. CONACyT-Mexico [373108/588771, 493794/588821]
  2. Tecnologico Nacional de Mexico, campus Agua Prieta, Sonora

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

The study proposes a cooperative coevolutionary algorithm for solving the no-wait job shop scheduling problem. The algorithm evolves permutations and binary chains simultaneously to optimize sequencing and timetabling decisions, and includes one-step perturbation mechanisms to improve solution quality. Experimental results show that the proposed algorithm produces competitive results and obtains new best values for some instances.
The no-wait job shop is an extension of the well-known job shop scheduling subject to the constraint that the operations of any job, once started, must be processed immediately, one after the other, until the completion of the job. The problem is NP-hard and exact methods can only solve small instances. In the last two decades of advances on this problem, one aspect became central for the success of metaheuristics to tackle it, namely the decomposition of solution into two parts: sequencing and timetabling. Most of these metaheuristics use a permutation to represent the sequencing part, while the timetabling part uses specific rules that differentiate one approach from the other. The main contribution of this work is the proposal of a cooperative coevolutionary algorithm where the sequencing and the timetabling parts interact with each other to evolve quasi-optimal sequencing and timetabling decisions. To this aim, the algorithm co-evolves a population of permutations with a population of binary chains. The permutation decides the sequencing while each bit in the binary chain decides whether or not a job is shifted to the left-most position on its corresponding machine. Therefore, the whole binary chain defines a timetabling rule that is automatically optimized during the evolution process. The algorithm also includes one-step perturbation mechanisms that help improve the solution quality. The proposed algorithm is tested on a set of benchmark instances to compare it with seven state-of-the-art methods. Computational experiments show that the proposed algorithm produces competitive results, furthermore, new best values for four instances are obtained.

作者

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

评论

主要评分

4.7
评分不足

次要评分

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

推荐

暂无数据
暂无数据