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

Weighted earliness/tardiness parallel machine scheduling problem with a common due date

Arik, Oguzhan Ahmet*; Schutten, Marco; Topan, Engin
EXPERT SYSTEMS WITH APPLICATIONS2022-1DOI: 10.1016/j.eswa.2021.115916
15被引1阅读
引用收藏
分享

摘要

This paper investigates an unrelated parallel machine scheduling problem with a restrictive common due date. The objective is to minimize the total sum of earliness/tardiness costs. Using some properties of the problem such as V-Shaped property, optimizing start times of machines, and no idle time between successive jobs, we propose effective construction-based heuristics and local search algorithms for the problem. Using variants of the shortest and longest processing time dispatching rules and job assignment patterns, we propose four different construction algorithms to have a balanced number of jobs or the workload per machine. We construct four deterministic and one stochastic solution improvement heuristic approaches using swap and reinsertion local search mechanisms. In the proposed reinsertion-based local search mechanism, the V-shaped property of each machine is used effectively to determine the proper positions in which the removed job is inserted. After both swap and reinsertion operators, a V-Shaped property preserving mechanism takes place to preserve the V-Shaped property of each machine. We also use an LP formulation in our proposed solution approaches to determine the optimum start times of machines for a given schedule. We compare our proposed heuristics against four metaheuristics, namely simulated annealing, genetic algorithm, artificial bee colony algorithm, and fast ruin and recreate algorithm. A simple lower bound for the optimal objective function value is proposed to show the efficiency of our proposed heuristics. We test our heuristics also in an identical machine environment. The experimental study reveals that the construction and the improvement heuristic methods including swap and reinsertion outperform metaheuristics and other heuristics in solution quality for both identical and unrelated machine environments.

学科与关键词

关键词
Parallel machineCommon due dateEarlinessTardinessHeuristicV-shaped
相关
加载中…
  • Local search based methods for scheduling in the unrelated parallel machines environment
    Ulaga, Lucija; Durasevic, Marko*; Jakobovic, DomagojEXPERT SYSTEMS WITH APPLICATIONS, 2022, 199: 116909.被引 7
  • 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
  • Iterated hybrid metaheuristic algorithms for unrelated parallel machines problem with unequal ready times and sequence-dependent setup times
    Chen, Chun-Lung*INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2012, 60(5-8): 693-705.被引 14
查看全部 →

发表信息

论文状态
公开发表
期刊
EXPERT SYSTEMS WITH APPLICATIONS
发表日期
2022-01
卷期
第 187 卷
页码
115916
DOI
10.1016/j.eswa.2021.115916
语言
ENGLISH
期刊等级
1区
成果收录
SCIE

作者

  • A

    Arik, Oguzhan Ahmet (通讯) (第一作者)

  • S

    Schutten, Marco

查看全部 3 位作者收起作者
  • T

    Topan, Engin

登录解锁更多功能

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

产品服务

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

服务支持

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

联系方式

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

关注或下载科研之友

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

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

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