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.
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
.
DOI: 10.15960/j.cnki.issn.1007-6093.2020.02.010
[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.
