Back to Search
Start Over
Revisit the scheduling problem with assignable or generalized due dates to minimize total weighted late work.
- Source :
- International Journal of Production Research; Nov2023, Vol. 61 Issue 22, p7630-7648, 19p, 4 Diagrams, 12 Charts
- Publication Year :
- 2023
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00207543
- Volume :
- 61
- Issue :
- 22
- Database :
- Complementary Index
- Journal :
- International Journal of Production Research
- Publication Type :
- Academic Journal
- Accession number :
- 172441289
- Full Text :
- https://doi.org/10.1080/00207543.2022.2160502