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

A hybrid algorithm with a new neighborhood structure for job shop scheduling problems

Xie, Jin; Li, Xinyu; Gao, Liang*; Gui, Lin华中科技大学
COMPUTERS & INDUSTRIAL ENGINEERING2022-7DOI: 10.1016/j.cie.2022.108205
24被引11阅读
引用收藏
分享

摘要

Job shop scheduling problems (JSP) arise from the scheduling of modern manufacturing enterprises. It is one of the most famous NP-complete problem. To evaluate the performance of algorithms, several famous benchmarks have been presented from 1990s. A few decades later, some instances had been found the optimal solutions, but more instances remain unresolved. Trying to update the new upper bounds, the paper presents a hybrid algorithm (HA) combining the genetic algorithm (GA) and the tabu search (TS) to solve JSP with the makespan criterion. GA has an excellent global search ability, and TS has a powerful local search ability. Our HA can combine their advantages and well balance the intensification and the diversification. In the GA part, the paper designs a crossover operator referring to a path relinking procedure and a mutation operator on a basis of critical paths. In the TS part, the paper adopts our previously proposed neighborhood structure, which can effectively expand the search space of neighborhood solutions. 135 famous benchmark instances are selected to evaluate the optimization effect of HA. Six state-of-the-art methods are selected to compare with HA. The results verify that the HA outperforms its compared algorithms in both computational efficiency and solution quality. Especially, the proposed HA has updated the upper bounds of two challenging instances, DMU56-4939 and DMU57-4647.

学科与关键词

关键词
Job shop scheduling problemsTabu searchGenetic algorithmNeighborhood structure
相关
加载中…
  • A hybrid genetic tabu search algorithm for solving job shop scheduling problems: a case study
    Meeran, S.*; Morshed, M. S.JOURNAL OF INTELLIGENT MANUFACTURING, 2012, 23(4): 1063-1078.被引 66
  • Evaluation of a hybrid genetic tabu search framework on job shop scheduling benchmark problems
    Meeran, S.*; Morshed, M. S.International Journal of Production Research, 2014, 52(19): 5780-5798.被引 9
  • Improved Hybrid Heuristic Algorithm Inspired by Tissue-Like Membrane System to Solve Job Shop Scheduling Problem
    Tian, Xiang; Liu, Xiyu*Processes, 2021, 9(2): 219.被引 9
查看全部 →

发表信息

论文状态
公开发表
期刊
COMPUTERS & INDUSTRIAL ENGINEERING
发表日期
2022-07
卷期
第 169 卷
页码
108205
DOI
10.1016/j.cie.2022.108205
语言
MULTI-LANGUAGE
成果收录
SCIE
资助标注
National Natural Science Foundation of China [51825502, U21B2029, 52188102]

作者

  • X

    Xie, Jin (第一作者)

    huazhong univ sci & technol

  • L

    Li, Xinyu

    huazhong univ sci & technol

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

    Gao, Liang (通讯)

    huazhong univ sci & technol

  • G

    Gui, Lin

    huazhong univ sci & technol

登录解锁更多功能

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

产品服务

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

服务支持

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

联系方式

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

关注或下载科研之友

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

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

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