New algorithms for minimizing the weighted number of tardy jobs on a single machine

Danny Hermelin (), Shlomo Karhi (), Michael Pinedo () and Dvir Shabtay ()
Additional contact information
Danny Hermelin: Ben-Gurion University
Shlomo Karhi: Bar-Ilan University
Michael Pinedo: New York University
Dvir Shabtay: Ben-Gurion University

Annals of Operations Research, 2021, vol. 298, issue 1, No 14, 287 pages

Abstract: Abstract In this paper we study the classical single machine scheduling problem where the objective is to minimize the weighted number of tardy jobs. Our analysis focuses on the case where one or more of three natural parameters is either constant or is taken as a parameter in the sense of parameterized complexity. These three parameters are the number of different due dates, processing times, and weights in our set of input jobs. We show that the problem belongs to the class of fixed parameter tractable (FPT) problems when combining any two of these three parameters. We also show that the problem is polynomial-time solvable when either one of the latter two parameters are constant, complementing Karp’s result who showed that the problem is NP-hard already for a single due date.

Keywords: Single machine scheduling; Weighted number of tardy jobs; Fixed parametrized tractability; NP-hard; Polynomial time algorithms (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-018-2852-9 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:annopr:v:298:y:2021:i:1:d:10.1007_s10479-018-2852-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-018-2852-9

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().