Minimizing total weighted late work on a single-machine with non-availability intervals

Shi-Sheng Li () and Ren-Xia Chen
Additional contact information
Shi-Sheng Li: Zhongyuan University of Technology
Ren-Xia Chen: College of Science, Zhongyuan University of Technology

Journal of Combinatorial Optimization, 2022, vol. 44, issue 2, No 21, 1330-1355

Abstract: 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)$$ 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{}$$ NP -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.

Keywords: Scheduling; late work; non-availability intervals; dynamic programming (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00890-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:2:d:10.1007_s10878-022-00890-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-022-00890-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().