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

Just-in-time scheduling problem with affine idleness cost

Tan, Zhen*; Fu, Guanqiuniv nottingham ningbo china; zhejiang univ finance & econ
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH2024-3-16DOI: 10.1016/j.ejor.2023.08.038
1被引1阅读
引用收藏
分享

摘要

We study a single-machine scheduling problem which minimizes total earliness, tardiness and idleness costs. In this problem, n jobs with job-specific due dates and processing times need to be processed in a non-preemptive fashion. We assume that when the idle time between two jobs is strictly positive, an idleness cost will be generated which is affine in the idle time. A hybrid solution approach is designed by integrating a tailored dynamic programming (TDP) algorithm for the exact timing solution and a customized Genetic Algorithm with restarts and early discarding (GARED) as the sequencing heuristic. By bounding the number of segments of the optimal cost function, we show that the proposed TDP algorithm has a low time complexity of O (n2 ) despite the non-convexity of the idleness cost function. In GARED, we utilize the monotonicity in the optimal cost in TDP to design a fast-screening scheme called Early Discarding which identifies and abandons an unpromising sequencing solution by evaluating only a short starting sub-sequence. Restarts are allowed to make the algorithm more robust in the case of premature local convergence of one evolutionary trial. Experimental results show that GARED significantly outperforms the basic elitist GA with or without restarts under most problems tested. Our hybrid method also scales well to large problem instances with n = 300 and achieves similar or better performance compared to an exact algorithm in the literature, but the latter only applies to problems with integer-valued time parameters and no idleness cost in between the jobs.

学科与关键词

关键词
SchedulingEarliness/tardiness costIdleness costDynamic programmingGenetic algorithm
相关
加载中…
  • Single machine scheduling with unequal release times and idle insert for minimizing the sum of maximum earliness and tardiness
    Mahnam, Mehdi; Moslehi, Ghasem; Ghomi, Seyyed Mohammad Taghi Fatemi*MATHEMATICAL AND COMPUTER MODELLING, 2013, 57(9-10): 2549-2563.被引 18
  • Minimizing the total weighted earliness and tardiness for a sequence of operations in job shops
    Girish, Baby Sivanandan*; Habibullah; Dileeplal, JessammaRAIRO-OPERATIONS RESEARCH, 2022, 56(4): 2621-2649.被引 2
  • Hybrid approach for a single -batch -processing machine scheduling problem with a just -in -time objective and consideration of non-identical due dates of jobs
    Zhang, Hongbin; Wu, Feng; Yang, Zhen*COMPUTERS & OPERATIONS RESEARCH, 2021, 128: 105194.被引 7
查看全部 →

发表信息

论文状态
公开发表
期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
发表日期
2024-03-16
卷期
第 313 卷, 第 3 期
页码
954-976
DOI
10.1016/j.ejor.2023.08.038
语言
ENGLISH
成果收录
SCIE
资助标注
Natural Science Foundation of China [72372015]; Natural Science Foundation of Zhejiang Province, China [LQ23G010 0 05]; Nottingham University Ningbo China [RESI202309003]

作者

  • T

    Tan, Zhen (通讯) (第一作者)

    univ nottingham ningbo china

  • F

    Fu, Guanqi

    univ nottingham ningbo china · zhejiang univ finance & econ

登录解锁更多功能

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

产品服务

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

服务支持

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

联系方式

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

关注或下载科研之友

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

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

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