ScholarMate
English简体中文繁體中文
客服热线:400-1616-289
登录注册
期刊论文

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

Valenzuela-Alcaraz, Victor M.; Cosio-Leon, M. A.; Danisa Romero-Ocano, A.; Brizuela, Carlos A.*
EXPERT SYSTEMS WITH APPLICATIONS2022-5-15DOI: 10.1016/j.eswa.2022.116498
10被引3阅读
引用收藏
分享

摘要

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.

学科与关键词

关键词
SchedulingNo-waitJob shopMakespanCooperative coevolutionaryGenetic algorithmTimetabling
相关
加载中…
  • A population-based iterated greedy algorithm for no-wait job shop scheduling with total flow time criterion
    Deng, Guanlong*; Su, Qingtang; Zhang, Zhiwang; Liu, Huixia; Zhang, Shuning; Jiang, TianhuaENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE, 2020, 88: 103369.被引 34
  • Solving no-wait job-shop scheduling problems using a multi-start simulated annealing with bi-directional shift timetabling algorithm
    Ying, Kuo-Ching; Lin, Shih-Wei*COMPUTERS & INDUSTRIAL ENGINEERING, 2020, 146: 106615.被引 16
  • A simple migrating birds optimization algorithm with two search modes to solve the no-wait job shop problem
    Deng, Guanlong*; Wei, Ming; Zhang, Shuning; Xu, Mingming; Jiang, Tianhua; Wang, FucaiEXPERT SYSTEMS WITH APPLICATIONS, 2024, 238: 122112.被引 3
查看全部 →

发表信息

论文状态
公开发表
期刊
EXPERT SYSTEMS WITH APPLICATIONS
发表日期
2022-05-15
卷期
第 194 卷
页码
116498
DOI
10.1016/j.eswa.2022.116498
语言
ENGLISH
期刊等级
1区
成果收录
SCIE
资助标注
CONACyT-Mexico [373108/588771, 493794/588821]; Tecnologico Nacional de Mexico, campus Agua Prieta, Sonora

作者

  • V

    Valenzuela-Alcaraz, Victor M. (第一作者)

  • C

    Cosio-Leon, M. A.

查看全部 4 位作者收起作者
  • D

    Danisa Romero-Ocano, A.

  • B

    Brizuela, Carlos A. (通讯)

登录解锁更多功能

  • 收藏这篇,随时在“我的 · 收藏”找回
  • 认领你的成果,生成推广素材
  • 关注作者获取最新成果
  • 加入项目组、协同写作
注册 / 登录

产品服务

  • 科研之友
  • 创新城
  • 科创云

服务支持

  • 帮助中心
  • 隐私政策
  • 服务条款

联系方式

在线客服:【】
客服热线:400-1616-289
电子邮箱:support@scholarmate.com

关注或下载科研之友

微信二维码
微信公众号
客户端下载二维码
下载客户端
科研成果科研人员科研机构科研动态爱瑞思软件

©2026 深圳市科研之友网络服务有限公司

公安备案图标粤公网安备 44030502000213
粤ICP备 16046710 号粤B2-20110417