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

A self-tuning variable neighborhood search algorithm and an effective decoding scheme for open shop scheduling problems with travel/setup times

Mejia, Gonzalo; Yuraszeck, Francisco
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH2020-9-1DOI: 10.1016/j.ejor.2020.02.010
32被引1阅读
引用收藏
分享

摘要

In this paper, we study Open Shop Scheduling Problems (OSSPs) that involve (1) travel times between machines and/or (2) sequence-dependent setup times. First, we propose a new decoding scheme on the well-known permutation list representation and study its properties. Second, we describe an effective Variable Neighborhood Search (VNS) algorithm which incorporates the proposed decoding scheme and that uses a self-tuning routine to set its most important parameter. Last, we tested the performance of the algorithm on several sets of instances: the first two sets consisted of classical instances of OSSPs extended with randomly generated both travel times and anticipatory sequence-dependent setup times. The third set of problems were instances of OSSPs with travel times previously presented in the literature. The last set of problems consisted of classical OSSP of the literature and was used mainly to corroborate our results. The solutions of the proposed VNS were compared with the solutions of constraint programming (CP) algorithms, previous solutions and with the optimal solutions where available. The results revealed three important things: First, the decoding strategy was the factor that had the greatest influence on the performance of the VNS algorithm. Second, the proposed self-tuning VNS algorithm was robust and very easy to adapt to a variety of OSSPs. Third, the algorithm exhibited consistent and very competitive performance in terms of computer time and solution quality in all sets of instances.

学科与关键词

关键词
SchedulingOpen shopVariable neighborhood searchSequence-dependent setup timesTravel times
相关
加载中…
  • New efficient heuristics for scheduling open shops with makespan minimization
    Abreu, Levi R.*; Prata, Bruno A.; Framinan, Jose M.; Nagano, Marcelo S.COMPUTERS & OPERATIONS RESEARCH, 2022, 142: 105744.被引 14
  • Solving the flexible job shop scheduling problem with sequence-dependent setup times
    Shen, Liji*; Dauzere-Peres, Stephane; Neufeld, Janis S.EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2018, 265(2): 503-516.被引 151
  • A meta-heuristic to solve the just-in-time job-shop scheduling problem
    Ahmadian, Mohammad Mahdi; Salehipour, Amir*; Cheng, T. C. E.EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2021, 288(1): 14-29.被引 67
查看全部 →

发表信息

论文状态
公开发表
期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
发表日期
2020-09-01
卷期
第 285 卷, 第 2 期
页码
484-496
DOI
10.1016/j.ejor.2020.02.010
语言
ENGLISH
期刊收录
NSL.SCIE
期刊等级
1区
成果收录
SCIE

作者

  • M

    Mejia, Gonzalo (第一作者)

  • Y

    Yuraszeck, Francisco

登录解锁更多功能

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

产品服务

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

服务支持

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

联系方式

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

关注或下载科研之友

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

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

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