带有退化效应和序列相关运输时间的排序问题

doi:10.15960/j.cnki.issn.1007-6093.2016.04.007

运筹学学报 ›› 2016, Vol. 20 ›› Issue (4): 61-68.doi: 10.15960/j.cnki.issn.1007-6093.2016.04.007

带有退化效应和序列相关运输时间的排序问题

苗翠霞^1,*邹娟¹

1. 曲阜师范大学数学科学学院，山东曲阜 273165

收稿日期:2016-02-28 出版日期:2016-12-15 发布日期:2016-12-15
通讯作者: 苗翠霞 miaocuixia@126.com
基金资助:
国家自然科学基金(No. 11201259), 教育部博士点基金(Nos. 20123705120001, 20123705110003), 山东省自然科学基金(Nos. ZR2014AM012, BS2013SF016), 曲阜师范大学科研奖励基金(No. xkj201516)

Scheduling with simple deterioration and past-sequence-dependent delivery times

MIAO Cuixia^1,*ZOU Juan¹

1. School of Mathematical Sciences, Qufu Normal University, Qufu 273165, Shandong, China

Received:2016-02-28 Online:2016-12-15 Published:2016-12-15

摘要/Abstract

摘要：

考虑带有退化效应和序列相关运输时间的单机排序问题. 工件的加工时间是其开工时间的简单线性增加函数. 当机器单个加工工件时, 极小化最大完工时间、(加权)总完工时间和总延迟问题被证明是多项式可解的, EDD序对于极小化最大延迟问题不是最优排序, 另外, 就交货期和退化率一致情形给出了一最优算法. 当机器可分批加工工件时, 分别就极小化最大完工时间和加权总完工时间问题提出了多项式时间最优算法.

关键词: 排序, 并行分批, 退化效应, 序列相关运输时间

Abstract:

In this paper, the single-machine scheduling problem with simple deterioration and past-sequence-dependent (p-s-d) job delivery times is considered, in which the processing time of each job is a simple linear increasing function of its starting time. When the machine can process only one job at a time, firstly, the makespan, the total (weighted) completion time and the total lateness minimization problems are solvable in polynomial, the EDD rule is not an optimal solution to the maximum lateness minimization problem, and an optimal solution to the case where jobs have agreeable due dates and deteriorating rates is proposed. When the machine can process up to $b$ jobs simultaneously as a batch, i.e., the parallel-batch scheduling problems, two polynomial time optimal algorithms for the makespan minimization problem and the total weighted completion time minimization problem are presented, respectively.

Key words: scheduling, parallel-batch, deterioration, past-sequence-dependent delivery times

苗翠霞, 邹娟. 带有退化效应和序列相关运输时间的排序问题[J]. 运筹学学报, 2016, 20(4): 61-68.

MIAO Cuixia, ZOU Juan. Scheduling with simple deterioration and past-sequence-dependent delivery times[J]. Operations Research Transactions, 2016, 20(4): 61-68.

[1] Gupta G N D, Gupta S K. Single facility scheduling with nonlinear processing times [J]. Computer and Industrial Engineering, 1988, 14: 387-393.

[2] Browne S, Yechiali U. Scheduling deteriorating jobs on a single processor [J]. Operations Research, 1990, 28: 495-498.

[3] Mosheiov G. Scheduling jobs under simple linear deterioration [J]. Computers and Operations Research, 1994, 21: 653-659.

[4] Cheng T C E, Ding Q, Lin B M T. A concise survey of scheduling with time-dependent processing times [J]. European Journal of Operational Research, 2004, 152: 1-13.

[5] Gawiejnowicz S. Time-Dependent Scheduling [M]. Berlin: Springer-Verlag, 2008.

[6] Cheng T C E, Yang S J, Yang D L. Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity [J]. International Journal of Production Economics, 2012, 135: 154-161.

[7] Wang J B, Wang M Z. Single-machine scheduling with nonlinear deterioration [J]. Optimization Letters, 2012, 6: 87-98.

[8] Wang J B, Wang J J. Single-machine scheduling problems with precedence constraints and simple linear deterioration [J]. Applied Mathematical Modelling, 2015, 39: 1172-1182.

[9] Brucker P, Gladky A, Hoogeveen H, et al. Scheduling a batching machine [J]. Journal of Scheduling, 1998, 1: 31-54.

[10] Potts C N, Kovalyov M Y. Scheduling with batching: a review [J]. European Journal of Operational Research, 2000, 120: 228-249.

[11] Yuan J J, Qi X L, Lu L F, et al. Single machine unbounded parallel-batch scheduling [J]. European Journal of Operational Research, 2008, 186: 112-117.

[12] Li S S, Chen R X. Scheduling a bounded parallel-batching machine with incompatible job families and rejection [J]. Journal of the Operations Research Society of China, 2014, 2(4): 499-510.

[13] Wang C F, Zhang Y Z. On-line batch scheduling with known information in advance [J]. Operations Research Transactions, 2016, 20(1): 84-90.

[14] Koulamas C, Kyparisis G J. Single-machine scheduling problems with past-sequence-dependent delivery times [J]. International Journal of Production Economics, 2010, 126: 264-266.

[15] Liu M, Zheng F F, Chu C B, et al. New results on single-machine scheduling with past-sequence-dependent delivery times [J]. Theoretical Computer Science, 2012, 438: 55-61.

[16] Liu M, Zheng F F, Chu C B, et al. Single-machine scheduling with past-sequence-dependent delivery times and release times [J]. Information Processing Letters, 2012, 112: 835-838.

[17] Cheng T C E, Lee W C, Wu C C. Single-machine scheduling with deteriorating jobs and past-sequence-dependent setup times [J]. Applied Mathematical Modelling, 2011, 35: 1861-1867.

[18] Liu M, Zheng F F, Wang S J, et al. Scheduling deteriorating jobs with past-sequence-dependent delivery times [J]. International Journal of Production Economics, 2013, 44: 418-421.

[19] Shen L X, Wu Y B. Single machine past-sequence-dependent delivery times scheduling with general position-dependent and time-dependent learning effects [J]. Applied Mathematical Modelling, 2013, 37: 5444-5451.

[20] Zhao C L, Tang H Y. Single machine scheduling problems with general position-dependent processing times and past-sequence-dependent delivery times [J]. Journal of Applied Mathematics Computer, 2014, 45: 259-274.

[21] Yin Y Q, Cheng T C E, Xu J Y, et al. Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration [J]. Journal of Industral and Management Optimization, 2013, 9(2): 323-339.

[22] Graham R L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic sequencing and scheduling: a survey [J]. Annals of Discrete Mathematics, 1979, 5: 287-326.

带有退化效应和序列相关运输时间的排序问题

Scheduling with simple deterioration and past-sequence-dependent delivery times

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 15

编辑推荐

Metrics

本文评价

[1]	陈荣军, 刘永财, 黄河, 唐国春. 单机供应链排序问题动态规划算法[J]. 运筹学学报（中英文）, 2026, 30(1): 171-178.
[2]	孟兰梦, 马冉, 张玉忠. 在NDP约束条件下考虑带退化效应的单机在线调度[J]. 运筹学学报（中英文）, 2026, 30(1): 179-187.
[3]	吴弘一, 王冬, 万龙, 罗文昌. 嵌套加工型限制下的混合分批平行机排序问题的近似算法[J]. 运筹学学报（中英文）, 2026, 30(1): 188-196.
[4]	李大伟, 李刚刚. 考虑人员不可用及工件带退化效应的单机排序问题[J]. 运筹学学报（中英文）, 2025, 29(4): 14-26.
[5]	赵娣, 余金, 鲁习文. 单机两代理串行分批排序问题的近似算法[J]. 运筹学学报（中英文）, 2025, 29(2): 184-193.
[6]	崔同欣, 夏倩, 张新功. 基于松弛工期的总加权误工单机双代理排序问题[J]. 运筹学学报（中英文）, 2025, 29(1): 31-40.
[7]	杜诗翩, 顾满占. 带机器维护的最小化总误工数期望的随机排序问题研究[J]. 运筹学学报（中英文）, 2025, 29(1): 142-158.
[8]	李文杰, 杜智慧, 苏孟龙. 加工时间与运输时间具有一致性的单机NDP约束在线排序问题研究[J]. 运筹学学报（中英文）, 2024, 28(4): 18-28.
[9]	葛晴, 录岭法, 原晋江, 张利齐. 单机上一个与总完工时间及最大完工时间相关的工件可拒绝的ND双代理排序问题[J]. 运筹学学报（中英文）, 2024, 28(4): 66-74.
[10]	焦成文. 具有线性前瞻区间的单机平行批在线排序[J]. 运筹学学报（中英文）, 2024, 28(4): 111-116.
[11]	徐娟年, 马冉, 韩雯雯, 张玉忠. 工件权重带限制的最小化最大加权完工时间的单机在线排序问题[J]. 运筹学学报（中英文）, 2024, 28(2): 71-80.
[12]	高洁, 邹娟, 隋玉康, 张玉忠. 带有退化维护活动和工件可拒绝的非同类机排序问题[J]. 运筹学学报, 2023, 27(3): 137-149.
[13]	龚铭炀, 谈之奕, 严羽洁. 两台同类机排序问题SPT算法的最坏情况比[J]. 运筹学学报, 2022, 26(3): 92-108.
[14]	成夏炎, 何滢, 赵聪聪, 李荣珩. 两台自私型机器上自私工件排序的PoA紧界[J]. 运筹学学报, 2022, 26(3): 109-119.
[15]	王冬, 李刚刚, 罗文昌. 工件具有任意尺寸的混合分批平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(3): 133-142.