Revisit the scheduling problem with assignable or generalized due dates to minimize total weighted late work

ABSTRACT

We revisit the single-machine scheduling for minimising the total weighted late work with assignable due dates (ADD-scheduling) and generalised due dates (GDD-scheduling). In particular, we consider the following three problems: (i) the GDD-scheduling problem for minimising the total weighted late work, (ii) the ADD-scheduling problem for minimising the total weighted late work, and (iii) the ADD-scheduling problem for minimising the total late work. In the literature, the above three problems are proved to be NP-hard, but their exact complexity (unary NP-hardness or pseudo-polynomial-time solvability) are unknown. In this paper, we address these open problems by showing that the first two problems are unary NP-hard and the third problem admits pseudo-polynomial-time algorithms. For the third problem, we also present a 2-approximation solution and a fully polynomial-time approximation scheme. Computational experiments show that our algorithms and solutions are efficient. When the jobs have identical processing times, we further present more efficient polynomial-time algorithms.

KEYWORDS:

• Scheduling
• total weighted late work
• assignable/generalized due dates
• NP-hard
• algorithms

Acknowledgments

The authors would like to thank the Editor, the Associate Editor and two anonymous referees for their helpful insights and suggestions. Apart from the abstract of this paper, which was published in Yuan (2022), all the other contents of this paper have not been published elsewhere.

Disclosure statement

No potential conflict of interest was reported by the authors.

Data availability statement

Not relevant for this paper.

Additional information

Funding

This research was supported in part by the National Natural Science Foundation of China under grant numbers 12101567, 12071442, 11901539, and 11971443.

Notes on contributors

Rubing Chen

Rubing Chen is a research associate at the School of Mathematics and Statistics, Zhengzhou University (Zhengzhou, Henan). Her research interests in scheduling theory include bicriteria scheduling, computational complexity, algorithm designing. Her work has appeared in European Journal of Operational Research, Journal of Scheduling, Naval Research Logistics, and other journals.

Yuan Gao

Yuan Gao is a lecturer in the School of Mathematics and Statistics, Zhengzhou University (Zhengzhou, Henan). Her principal research interests are in combinatorial optimization and scheduling theory. Her work has been published in European Journal of Operational Research, Journal of Scheduling, Operations Research Letters, and other journals.

Zhichao Geng

ZhiChao Geng received the B.S. degree and the Ph. D. degree in School of Mathematics and Statistics from Zhengzhou University (Zhengzhou, Henan). His research interests include Combination Optimization, Scheduling Theory, Graph Theory and Sub-modular Optimization. He has been published papers in many journals such as European Journal of Operational Research, Applied Mathematics and Computation, Journal of Combinatorial optimization, and so on.

Jinjiang Yuan

Jinjiang Yuan is a Professor in the School of Mathematics and Statistics, Zhengzhou University (Zhengzhou, Henan). His principal research interests are in combinatorial optimization and scheduling theory. His papers have been published in European Journal of Operational Research, International Journal of Production Economics, Information Sciences, Journal of Scheduling, Optimization Letters, Operations Research Letters, Applied Mathematics and Computation, and other journals.