考虑工件具有加工位置上限最小化总加权误工量的单机排序问题.在此排序问题中，每个工件Jj都具有一个加工位置上限kj.也就是说，如果工件Jj是一个可行排序中的第x个工件，那么就需要满足x ≤ kj.证明了（i）当工件具有相同工期时，该排序问题是二元NP-难的并且是拟多项式时间可解的，（ii）当工件具有单位权重时，该排序问题是一元NP-难的.
We consider the single-machine scheduling problem to minimize the total weighted late work with positional due-indices. In the problem, each job Jj has a positional due-index kj. That is, if Jj is the x-th job in a feasible schedule, then it is required that x ≤ kj. 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.
[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.
