Paper Info
Title
Minimizing total weighted late work on a single-machine with non-availability intervals
Abstract
We explore the problem of scheduling n jobs on a single machine in which there are m fixed machine non-availability intervals. The target is to seek out a feasible solution that minimizes total weighted late work. Three variants of the problem are investigated. The first is the preemptive version, the second is the resumable version, and the third is the non-resumable version. For the first one, we present an $$O((m+n) \log n)$$ -time algorithm to solve it. For the second one, we develop an exact dynamic programming algorithm and a fully polynomial time approximation scheme. For the third one, we first demonstrate that it is strongly $$\mathcal{NP}\mathcal{}$$ -hard for the case where all jobs have the unit weight and common due date, and then we develop a pseudo-polynomial time algorithm for the unit weight case where the number of non-availability intervals is fixed, finally we propose a pseudo-polynomial time algorithm for the case where there is only one non-availability interval.
Year
DOI
Venue
2022
10.1007/s10878-022-00890-x
Journal of Combinatorial Optimization
Keywords
DocType
Volume
Scheduling, late work, non-availability intervals, dynamic programming
Journal
44
Issue
ISSN
Citations 
2
1382-6905
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Shi-Sheng Li100.34
Ren-Xia Chen200.34