工件具有加工位置上限最小化加权总误工量的单机排序问题

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

运筹学学报 ›› 2020, Vol. 24 ›› Issue (2): 131-144.doi: 10.15960/j.cnki.issn.1007-6093.2020.02.010

• • 上一篇

工件具有加工位置上限最小化加权总误工量的单机排序问题

陈如冰, 原晋江^*

郑州大学数学与统计学院, 郑州 450001

收稿日期:2020-02-28 发布日期:2020-06-13
通讯作者: 原晋江 E-mail:yuanjj@zzu.edu.cn
基金资助:
The National Nature Science Foundation of China (Nos. 11671368, 11771406, 11971443)

Single-machine scheduling to minimize total weighted late work with positional due-indices

CHEN Rubing, YUAN Jinjiang^*

School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China

Received:2020-02-28 Published:2020-06-13
Supported by:
The National Nature Science Foundation of China (Nos. 11671368, 11771406, 11971443)

摘要/Abstract

摘要： 考虑工件具有加工位置上限最小化总加权误工量的单机排序问题.在此排序问题中，每个工件J_j都具有一个加工位置上限k_j.也就是说，如果工件J_j是一个可行排序中的第x个工件，那么就需要满足x ≤ k_j.证明了（i）当工件具有相同工期时，该排序问题是二元NP-难的并且是拟多项式时间可解的，（ii）当工件具有单位权重时，该排序问题是一元NP-难的.

关键词: 机排序, 加工位置上限, NP-难, 误工量

Abstract: We consider the single-machine scheduling problem to minimize the total weighted late work with positional due-indices. In the problem, each job J_j has a positional due-index k_j. That is, if J_j is the x-th job in a feasible schedule, then it is required that x ≤ k_j. In this paper, we show that (i) the problem is binary NP-hard and can be solved in pseudo-polynomial-time if all the jobs have a common due date, (ii) the problem is unary NP-hard even if all the jobs have a unit weight.

Key words: single-machine scheduling, positional due-indices, NP-hard, late work

中图分类号:

O221.7

陈如冰, 原晋江. 工件具有加工位置上限最小化加权总误工量的单机排序问题[J]. 运筹学学报, 2020, 24(2): 131-144.

CHEN Rubing, YUAN Jinjiang. Single-machine scheduling to minimize total weighted late work with positional due-indices[J]. Operations Research Transactions, 2020, 24(2): 131-144.

参考文献

[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] Zhao Q L, Yuan J J. Rescheduling to minimize the maximum lateness under the sequence disruptions of original jobs[J]. Asia-Pacific Journal of Operational Research, 2017, 34:1750024.
[3] Zhao Q L, Lu L F, Yuan J J. Rescheduling with new orders and general maximum allowable time disruptions[J]. 4OR-A Quarterly Journal of Operations Research, 2016, 14:261-280.
[4] Chen R B, Yuan J J. Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices[J]. 4OR-A Quarterly Journal of Operations Research, 2020, 18:177-196.
[5] Blazewicz J. Scheduling preemptible tasks on parallel processors with information loss[J]. TSI-Technique et Science Informatiques, 1984, 3:415-420.
[6] Potts C N, Van Wassenhove L N. Single machine scheduling to minimize total late work[J]. Operations Research, 1992, 40:586-595.
[7] Potts C N, Van Wassenhove L N. Approximation algorithms for scheduling a single machine to minimize total late work[J]. Operations Research Letters, 1992, 11:261-266.
[8] Lin B M, Hsu S W. Minimizing total late work on a single machine with release and due dates[C]//SIAM conference on computational science and engineering, Orlando, 2005.
[9] Kovalyov M, Potts C N, Van Wassenhove L N. A fully polynomial approximation scheme for scheduling a single machine to minimize total weighted late work[J]. Mathematics of Operations Research, 1994, 19:86-93.
[10] Hariri A M A, Potts C N, Van Wassenhove L N. Single machine scheduling to minimize total weighted late work[J]. ORSA Journal on Computing, 1995, 7:232-242.
[11] Leung J Y T, Vincent K M, Wei W D. Minimizing the weighted number of tardy task units[J]. Discrete Applied Mathematics, 1994, 51:307-316.
[12] Chen R B, Yuan J J, Ng C T, et al. Single-machine scheduling with deadlines to minimize the total weighted late work[J]. Naval Research Logistics, 2019, 66:582-595.
[13] Sterna M. A survey of scheduling problems with late work criteria[J]. Omega, 2011, 39:120-129.
[14] Garey M R, Johnson D S. Computers and Intractability:A Guide to the Theory of NPCompleteness[M]. San Francisco:Freeman, 1979.
[15] Yuan J J. Unary NP-hardness of minimizing the number of tardy jobs with deadlines[J]. Journal of Scheduling, 2017, 20:211-218.

工件具有加工位置上限最小化加权总误工量的单机排序问题

Single-machine scheduling to minimize total weighted late work with positional due-indices

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

编辑推荐

Metrics

本文评价

[1]	任建峰, 田晓云. 带有异常点的平方度量设施选址问题[J]. 运筹学学报, 2021, 25(1): 114-122.
[2]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[3]	姜燕君, 徐大川, 张冬梅. 平方度量动态设施选址问题的近似算法[J]. 运筹学学报, 2018, 22(3): 49-58.
[4]	赵晓成, 李大刚. 机器和工人都有加工资质约束的平行机排序问题研究[J]. 运筹学学报, 2018, 22(3): 99-108.
[5]	苗翠霞, 孟凡晓. 基于退化效应的两台机器流水作业可拒绝排序[J]. 运筹学学报, 2017, 21(2): 66-72.
[6]	徐大川, 许宜诚, 张冬梅. k-平均问题及其变形的算法综述[J]. 运筹学学报, 2017, 21(2): 101-109.
[7]	范静, 张峰. 具有多个不可用时间段的单机供应链排序问题[J]. 运筹学学报, 2015, 19(3): 116-122.
[8]	仲维亚，马文慧，霍志明. 可中断的多任务平行机排序问题[J]. 运筹学学报, 2013, 17(3): 115-123.
[9]	张新功. 基于加工时间之和学习效应下的单机成组排序问题[J]. 运筹学学报, 2013, 17(1): 98-105.