An approximation algorithm for a supply-chain scheduling problem with an assignable common due window and holding time

被引：0
作者：
Long Zhang
Yuzhong Zhang
Qingguo Bai
机构：
[1] Qufu Normal University,Institute of Operations Research, School of Management
来源：
Journal of Combinatorial Optimization | 2022年 / 44卷
关键词：
Supply chain scheduling; Due window assignment; Holding time; Approximation algorithm; Fully polynomial-time approximation scheme;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
This paper studies single machine scheduling with batch deliveries, where a common due window for all jobs has to be determined, not given in advance. The objective is to minimize the overall cost for the process and delivery. Concretely, it includes the penalty of a job being early or tardy, the cost for holding and delivering a job, and the cost incurred by a late starting or a long duration of the common due window. Observing the NP-hardness, we provide an optimal algorithm of the problem and convert it to a fully polynomial time approximation scheme for a special case.
引用
收藏
页码：2167 / 2179
页数：12
相关论文
共 71 条
  • [1] Assarzadegan P(2016)Minimizing sum of the due date assignment costs, maximum tardiness and distribution costs in a supply chain scheduling problem Appl Soft Comput 47 343-356
  • [2] Rasti-Barzoki M(1996)Scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costs Eur J Oper Res 93 49-60
  • [3] Chen ZL(1988)Optimal common due-date with limited completion time deviation Comput Oper Res 15 91-96
  • [4] Cheng TCE(2012)Common due window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity Int J Prod Econ 135 154-161
  • [5] Cheng TCE(1979)Optimization and approximation in deterministic sequencing and scheduling: a survey Ann Discrete Math 4 287-326
  • [6] Yang SJ(1993)On scheduling to minimize earliness-tardiness and batch delivery costs with a common due date Eur J Oper Res 70 272-288
  • [7] Yang DL(1994)Earliness-tardiness scheduling problems with a common delivery window Oper Res Lett 15 195-203
  • [8] Graham RL(1996)Determination of common due window location in a single machine scheduling problem Eur J Oper Res 93 68-74
  • [9] Lawler EL(1998)Common due window size and location determination in a single machine scheduling problem J Oper Res Soc 49 1007-1010
  • [10] Lenstra JK(2017)A two-agent single machine scheduling problem with due-window assignment and a common flow-allowance J Combin Optim 33 1454-1468
12345678