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

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

Abstract

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

CLC Number:

O221.7

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.

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 9

Recommended Articles

Metrics

Comments

[1]	REN Jianfeng, TIAN Xiaoyun. Squared metric facility location problem with outliers [J]. Operations Research Transactions, 2021, 25(1): 114-122.
[2]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[3]	JIANG Yanjun, XU Dachuan, ZHANG Dongmei. An approximation algorithm for the squared metric dynamic facility location problem [J]. Operations Research Transactions, 2018, 22(3): 49-58.
[4]	MIAO Cuixia, MENG Fanxiao. Two-machine flow-shop scheduling with deterioration and rejection [J]. Operations Research Transactions, 2017, 21(2): 66-72.
[5]	ZHANG Long. Two-stage supply chain scheduling with a limited holding time [J]. Operations Research Transactions, 2017, 21(2): 126-134.
[6]	XU Dachuan, XU Yicheng, ZHANG Dongmei. A survey on algorithms for k-means problem and its variants [J]. Operations Research Transactions, 2017, 21(2): 101-109.
[7]	MA Lu, ZHANG Xingong. Two-agent scheduling problem about total late work on a single machine [J]. Operations Research Transactions, 2017, 21(1): 13-22.
[8]	FAN Jing, ZHANG Feng. Supply chain scheduling problem with multiple unavailability intervals on a single machine [J]. Operations Research Transactions, 2015, 19(3): 116-122.
[9]	ZHONG Weiya, MA Wenhui, HUO Zhiming. A preemptive multiprocessor order parallel machine scheduling problem [J]. Operations Research Transactions, 2013, 17(3): 115-123.