×

Strong NP-hardness of minimizing total deviation with generalized and periodic due dates. (English) Zbl 1476.90112

Summary: We consider a single-machine scheduling problem with generalized and periodic due dates such that each due date is assigned not to a specific job but to a position and the lengths of the intervals between consecutive due dates are identical. The objective is to minimize the total deviation, which is calculated as the sum of the earliness and tardiness of each job. We show that the problem is strongly NP-hard. We develop a heuristic and verify its performance via experiments.

MSC:

90B35 Deterministic scheduling theory in operations research
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Choi, B. C.; Park, M. J., Just-in-time scheduling with generalized due dates and identical due date intervals, Asia-Pac. J. Oper. Res., 35, Article 1850046 pp. (2018) · Zbl 1407.90148
[2] Gao, Y., Research on Computational Complexity of Some Newly Developing Scheduling Problems (2018), Zhengzhou University, (Ph.D. Thesis)
[3] Gao, Y.; Yuan, J., Unary NP-hardness of minimizing the total deviation with generalized or assignable due dates, Discrete Appl. Math., 189, 49-52 (2015) · Zbl 1332.90109
[4] Gao, Y.; Yuan, J., Unary NP-hardness of minimizing total weighted tardiness with generalized due dates, Oper. Res. Lett., 44, 92-95 (2016) · Zbl 1408.90128
[5] Graham, R.; Lawler, E.; Lenstra, J.; Kan, A. R., Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math., 5, 287-326 (1979) · Zbl 0411.90044
[6] Hall, N. G., Scheduling problems with generalized due dates, IIE Trans., 18, 220-222 (1986)
[7] Hall, N. G.; Kubiak, W.; Sethi, S. P., Earliness-tardiness scheduling problems, II: deviation of completion times about a restrictive common due date, Oper. Res., 39, 847-856 (1991) · Zbl 0762.90037
[8] Hall, N. G.; Lesaoana, M.; Potts, C. N., Scheduling with fixed delivery dates, Oper. Res., 49, 134-144 (2001) · Zbl 1163.90459
[9] Hall, N. G.; Posner, M. E., Earliness-tardiness scheduling problems, I: weighted deviation of completion times about a common due date, Oper. Res., 39, 836-846 (1991) · Zbl 0749.90041
[10] Hall, N. G.; Sethi, S. P.; Srikandarajah, S., On the complexity of generalized due date scheduling problems, European J. Oper. Res., 51, 100-109 (1991) · Zbl 0742.90043
[11] Qi, X. T.; Yu, G.; Bard, J. F., Single machine scheduling with assignable due dates, Discrete Appl. Math., 122, 211-233 (2002) · Zbl 1019.90024
[12] Srikandarajah, S., A note on the generalized due dates scheduling problem, Nav. Res. Logist., 37, 587-597 (1990) · Zbl 0712.90032
[13] Yang, X., Scheduling with generalized batch delivery dates and earliness penalties, IIE Trans., 32, 735-741 (2000)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.