Improved algorithms for single-machine common due window assignment and scheduling with batch deliveries

被引:5
作者
Li, Chung-Lun [1 ]
机构
[1] Hong Kong Polytech Univ, Dept Logist & Maritime Studies, Kowloon, Hong Kong, Peoples R China
关键词
Scheduling; Due window; Batch delivery; Computational complexity; MAINTENANCE ACTIVITY;
D O I
10.1016/j.tcs.2014.12.021
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We consider a single-machine due window assignment and scheduling problem with batch deliveries, where all jobs have a common due window, and the start time and size of the due window are decision variables. Finished jobs are delivered in batches with unlimited batch capacity. The objective is to determine the due window, a job sequence, and the delivery times, so as to minimize the total cost which comprises earliness of delivery, job holding, start time of due window, size of due window, number of delivery batches, and tardiness penalty. We consider three different variants of the problem corresponding to different measurements of tardiness penalty. We present polynomial-time solution procedures for these variants with significantly lower computational complexities than those of known algorithms in the literature. (C) 2015 Elsevier B.V. All rights reserved.
引用
收藏
页码:30 / 39
页数:10
相关论文
共 50 条
  • [41] Common due date assignment and single-machine scheduling with release times to minimize the weighted number of tardy jobs
    Chuanli Zhao
    Japan Journal of Industrial and Applied Mathematics, 2016, 33 : 239 - 249
  • [42] Improved algorithms for proportionate flow shop scheduling with due-window assignment
    Jin Qian
    Haiyan Han
    Annals of Operations Research, 2022, 309 : 249 - 258
  • [43] A note on the complexity of single-machine scheduling with a common due date, earliness-tardiness, and batch delivery costs
    Yuan, JJ
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 94 (01) : 203 - 205
  • [44] Common due window size and location determination in a single machine scheduling problem
    Liman, SD
    Panwalkar, SS
    Thongmee, S
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1998, 49 (09) : 1007 - 1010
  • [45] A Scheduling Problem on a Single Batching Machine with Batch Deliveries
    Gong Hua
    Tang Lixin
    2011 30TH CHINESE CONTROL CONFERENCE (CCC), 2011, : 2175 - 2179
  • [46] Single-machine slack due-window assignment and scheduling with past-sequence-dependent delivery times and controllable job processing times
    Ji, Min
    Yao, Danli
    Ge, Jiaojiao
    Cheng, T. C. E.
    EUROPEAN JOURNAL OF INDUSTRIAL ENGINEERING, 2015, 9 (06) : 794 - 818
  • [47] Single-machine common due-date scheduling with batch delivery costs and resource-dependent processing times
    Yin, Yunqiang
    Cheng, T. C. E.
    Wu, Chin-Chia
    Cheng, Shuenn-Ren
    INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2013, 51 (17) : 5083 - 5099
  • [48] Single-machine batch scheduling of linear deteriorating jobs
    Ji, Min
    Yang, Qinyun
    Yao, Danli
    Cheng, T. C. E.
    THEORETICAL COMPUTER SCIENCE, 2015, 580 : 36 - 49
  • [49] SCHEDULING PROBLEMS WITH A COMMON DUE WINDOW ASSIGNMENT: A SURVEY
    Janiak, Adam
    Kwiatkowski, Tomasz
    Lichtenstein, Maciej
    INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS AND COMPUTER SCIENCE, 2013, 23 (01) : 231 - 241
  • [50] Common due date assignment and cumulative deterioration scheduling on a single machine
    Li, Shi-Sheng
    Chen, Ren-Xia
    ENGINEERING OPTIMIZATION, 2017, 49 (06) : 976 - 989