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

An Evolutionary Variable Neighbourhood Search for the Unrelated Parallel Machine Scheduling Problem

Abdullah, Salwani; Turky, Ayad; Nazri, Mohd Zakree Ahmad; Sabar, Nasser R.*
IEEE Access2021DOI: 10.1109/ACCESS.2021.3065109
4被引2阅读
引用收藏
分享

摘要

This article addresses a challenging industrial problem known as the unrelated parallel machine scheduling problem (UPMSP) with sequence-dependent setup times. In UPMSP, we have a set of machines and a group of jobs. The goal is to find the optimal way to schedule jobs for execution by one of the several available machines. UPMSP has been classified as an NP-hard optimisation problem and, thus, cannot be solved by exact methods. Meta-heuristic algorithms are commonly used to find sub-optimal solutions. However, large-scale UPMSP instances pose a significant challenge to meta-heuristic algorithms. To effectively solve a large-scale UPMSP, this article introduces a two-stage evolutionary variable neighbourhood search (EVNS) methodology. The proposed EVNS integrates a variable neighbourhood search algorithm and an evolutionary descent framework in an adaptive manner. The proposed evolutionary framework is employed in the first stage. It uses a mix of crossover and mutation operators to generate diverse solutions. In the second stage, we propose an adaptive variable neighbourhood search to exploit the area around the solutions generated in the first stage. A dynamic strategy is developed to determine the switching time between these two stages. To guide the search towards promising areas, a diversity-based fitness function is proposed to explore different locations in the search landscape. We demonstrate the competitiveness of the proposed EVNS by presenting the computational results and comparisons on the 1640 UPMSP benchmark instances, which have been commonly used in the literature. The experiment results show that our EVNS obtains better results than the compared algorithms on several UPMSP instances.

学科与关键词

关键词
SwitchesHeuristic algorithmsSpace explorationJob shop schedulingBenchmark testingOptimizationLicensesMachine scheduling problemgenetic algorithmlocal search algorithm
相关
加载中…
  • Exact and metaheuristic approaches for unrelated parallel machine scheduling
    Moser, Maximilian; Musliu, Nysret; Schaerf, Andrea; Winter, Felix*JOURNAL OF SCHEDULING, 2022, 25(5): 507-534.被引 23
  • Heuristic and metaheuristic methods for the parallel unrelated machines scheduling problem: a survey
    Durasevic, Marko*; Jakobovic, DomagojArtificial Intelligence Review, 2023, 56(4): 3181-3289.被引 35
  • Enhanced symbiotic organisms search algorithm for unrelated parallel machines manufacturing scheduling with setup times
    Ezugwu, Absalom E.*Knowledge-Based Systems, 2019, 172: 15-32.被引 58
查看全部 →

发表信息

论文状态
公开发表
期刊
IEEE Access
发表日期
2021
卷期
第 9 卷
页码
42857-42867
DOI
10.1109/ACCESS.2021.3065109
语言
ENGLISH
期刊收录
NSL
期刊等级
3区
成果收录
SCIE
资助标注
Universiti Kebangsaan Malaysia [DIP-2016-024]

作者

  • A

    Abdullah, Salwani (第一作者)

  • T

    Turky, Ayad

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

    Nazri, Mohd Zakree Ahmad

  • S

    Sabar, Nasser R. (通讯)

登录解锁更多功能

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

产品服务

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

服务支持

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

联系方式

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

关注或下载科研之友

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

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

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