基于退化效应的两台机器流水作业可拒绝排序

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

运筹学学报

基于退化效应的两台机器流水作业可拒绝排序

苗翠霞^1,* 孟凡晓¹

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

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

Two-machine flow-shop scheduling with deterioration and rejection

MIAO Cuixia^1,*MENG Fanxiao¹

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

Received:2017-03-28 Online:2017-06-15 Published:2017-06-15

摘要/Abstract

摘要：

考虑了工件具有退化效应的两台机器流水作业可拒绝排序问题, 其中工件的加工时间是其开工时间的简单线性增加函数. 每个工件或者被接收, 依次在两台流水作业机器上被加工, 或者被拒绝但需要支付一个确定的费用. 考虑的目标是被接收工件的最大完工时间加上被拒绝工件的总拒绝费用之和. 证明了问题是NP-难的, 并提出了一个动态规划算法. 最后对一种特殊情况设计了多项式时间最优算法.

关键词: 排序, 流水作业, 退化效应, 可拒绝, NP-难

Abstract:

In this paper, we consider the two-machine flow-shop scheduling with deterioration and rejection, in which each job's processing time is simple linear increasing function of its starting time. A job is either accepted and processed on the two machines in a flow-shop system, or rejected with a certain penalty having to be paid. The objective is to minimize the sum of the makespan of the accepted jobs plus the total penalty of the rejected jobs. We show that the problem is NP-hard and present a dynamic programming algorithm. Furthermore, we propose an optimal schedule for one special case.

Key words: scheduling, flow-shop, deterioration, rejection, NP-hard

苗翠霞, 孟凡晓. 基于退化效应的两台机器流水作业可拒绝排序[J]. 运筹学学报, doi: 10.15960/j.cnki.issn.1007-6093.2017.02.008.

MIAO Cuixia, MENG Fanxiao. Two-machine flow-shop scheduling with deterioration and rejection[J]. Operations Research Transactions, doi: 10.15960/j.cnki.issn.1007-6093.2017.02.008.

参考文献

[1] 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.

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

[3] Browne S, Yechiali U. Scheduling deteriorating jobs on a single processor [J]. Operations Research, 1990, 38(3): 495-498.

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

[5] 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.

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

[7] 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.

[8] Bartal Y, Leonardi S, Marchetti-Spaccamela A, et al. Multiprocessor scheduling with rejection [J]. SIAM Journal Discrete Mathematics, 2000, 13: 64-78.

[9] Shabtay D, Gaspar N, Kaspi M. A survey on offline scheduling with rejection [J]. Journal of Scheduling, 2013, 16: 3-28.

[10] Choi B C, Chung J. Two-machine flow shop scheduling problem with an outsourcing option [J]. European Journal of Operational Research, 2011, 213: 66-72.

[11] Shabtay D, Gaspar N. Two-machine flow-shop scheduling with rejection [J]. Computers and Operations Research, 2012, 39: 1087-1096.

[12] Zhang L Q, Lu L F, Li S S. New results on two-machine flow-shop scheduling with rejection [J]. Journal of Combinatorial Optimization, 2016, 31: 1493-1504.

[13] Cheng Y S, Sun S T. Scheduling linear deteriorating jobs with rejection on a single machine [J]. European Journal of Operational Research, 2009, 194: 18-27.

[14] Li S S, Yuan J J. Parallel-machine scheduling with deteriorating jobs and rejection [J]. Theoretical Computer Science, 2010, 411: 3642-3650.

[15] Garey M R, Johnson D S. Computers and intractability: a guide to the theory of NP-completeness [M]. San Francisco: Freeman, 1979.

[16] Johnson S M. Optimal two-and-three-stage production schedules with set-up times included [J]. Naval Research Logistics Quarter, 1954, 1: 61-68.

基于退化效应的两台机器流水作业可拒绝排序

Two-machine flow-shop scheduling with deterioration and rejection

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	赵聪聪, 方丹丹, 李荣珩. 具有学习效应的两台机上最优混合流水作业算法[J]. 运筹学学报, 2020, 24(2): 42-60.
[2]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[3]	陈如冰, 原晋江. 工件具有加工位置上限最小化加权总误工量的单机排序问题[J]. 运筹学学报, 2020, 24(2): 131-144.
[4]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[5]	苟燕, 戴秦, 张新功. 具有时间与位置相关的两类平行机排序问题[J]. 运筹学学报, 2019, 23(4): 86-94.
[6]	李刚刚, 鲁习文. 目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法[J]. 运筹学学报, 2019, 23(4): 95-104.
[7]	李文华, 翟威娜, 柴幸, 高超. 具有两个不相容工件族单位工件的有界分批在线排序问题[J]. 运筹学学报, 2019, 23(4): 105-110.
[8]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[9]	仲维亚, 杨若瑶. 工件具有子工件工期的排序问题[J]. 运筹学学报, 2019, 23(2): 67-74.
[10]	彭南南, 张玉忠, 柏庆国, 王成飞. 工件满足一致性的同类机在线分批排序问题[J]. 运筹学学报, 2019, 23(1): 111-118.
[11]	姜燕君, 徐大川, 张冬梅. 平方度量动态设施选址问题的近似算法[J]. 运筹学学报, 2018, 22(3): 49-58.
[12]	赵晓成, 李大刚. 机器和工人都有加工资质约束的平行机排序问题研究[J]. 运筹学学报, 2018, 22(3): 99-108.
[13]	何程, 韩鑫鑫. 同时最小化最大费用和最大完工时间的双代理无界平行分批排序[J]. 运筹学学报, 2018, 22(3): 109-116.
[14]	闵啸，朱俊蕾，刘静. 两台带服务等级的可拒绝同型机排序问题的在线算法[J]. 运筹学学报, 2018, 22(3): 117-124.
[15]	酒明珠, 高园, 原晋江. 工件可自由下线最小化总完工时间的平行分批排序问题[J]. 运筹学学报, 2018, 22(1): 32-41.