In the paper, we consider novel scheduling problems under single-machine, parallel-machine and two-machine open-shop environment. The due date is assigned to a job according to its completion time and the intervals between consecutive due dates are identical. Generally, the due dates are referred as periodic due dates (PDD). The objectives we consider are all to minimize the maximum tardiness. For single machine environment, we give an optimal schedule in polynomial time; for two parallel-machine environment, we prove this problem is NP-hard; for parallel-machine environment, we prove this problem is strongly NP-hard; for two-machine open-shop environment, we prove this problem is strongly NP-hard.
WAN Long, HUANG Xiaoli, MEI Jiajie
. Scheduling with periodic due date to minimize the maximum tardiness[J]. Operations Research Transactions, 2022
, 26(4)
: 75
-86
.
DOI: 10.15960/j.cnki.issn.1007-6093.2022.04.006
[1] Hall N G. Scheduling problems with generalized due dates[J]. IIE Transactions, 1986, 18(2): 220-222.
[2] Sriskandarajah C. A note on the generalized due dates scheduling problem[J]. Naval Research Logistics, 1990, 37(4): 587-597.
[3] Gao Y, Yuan J J. Unary NP-hardness of minimizing total weighted tardiness with generalized due dates[J]. Operations Research Letters, 2016, 44(1): 92-95.
[4] Wan L, Yuan J J. Single-machine scheduling to minimize the total earliness and tardiness is strongly NP-hard[J]. Operations Research Letters, 2013, 41(4): 363-365.
[5] Qi X T, Yu G, Bard J F. Single machine scheduling with assignable due dates[J]. Discrete Applied Mathematics, 2002, 122(1-3): 211-233.
[6] Gao Y, Yuan J J. Unary NP-hardness of minimizing the total deviation with generalized or assignable due dates[J]. Discrete Applied Mathematics, 2015, 189(10): 49-52.
[7] Choi B C, Park M J. Just-in-time scheduling with generalized due dates and identical due date intervals[J]. Asia-Pacific Journal of Operational Research, 2018, 35(6): 1850046.1-1850046.13.
[8] Choi B C, Min Y, Park M J. Strong NP-hardness of minimizing total deviation with generalized and periodic due dates[J]. Operations Research Letters, 2019, 47(5): 433-437.
[9] Choi B C, Park M J. Single-machine scheduling with periodic due dates to minimize the total earliness and tardy penalty[J]. Journal of Combinatorial Optimization, 2021, 41(4): 781-793.
[10] Choi B C, Kim K M, Min Y, et al. Scheduling with generalized and periodic due dates under single-and two-machine environments[J]. Optimization Letters, 2021: 1-11.
[11] Garey M R, Johnson D S. Computers and Intractability: A Guide to The Theory of NP-Completeness[M]. San Francisco: W H Freeman and Company, 1979.
[12] Brucker P. Scheduling Algorithms[M]. Berlin Heidelberg: Springer-Verlag, 2007.
