Minimizing the Weighted Number of Tardy Jobs via (max,+)-Convolutions

Danny Hermelin (), Hendrik Molter () and Dvir Shabtay ()
Additional contact information
Danny Hermelin: Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, 84105 Beer-Sheva, Israel
Hendrik Molter: Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, 84105 Beer-Sheva, Israel
Dvir Shabtay: Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, 84105 Beer-Sheva, Israel

INFORMS Journal on Computing, 2024, vol. 36, issue 3, 836-848

Abstract: In this paper we consider the fundamental scheduling problem of minimizing the weighted number of tardy jobs on a single machine. We present a simple pseudo polynomial-time algorithm for this problem that improves upon the classical Lawler and Moore algorithm from the late 60’s under certain scenarios and parameter settings. Our algorithm uses (max,+)-convolutions as its main tool, exploiting recent improved algorithms for computing such convolutions, and obtains several different running times depending on the specific improvement used. We also provide a related lower bound for the problem under a variant of the well-known Strong Exponential Time Hypothesis (SETH).

Keywords: weighted number of tardy jobs; single machine scheduling; pseudo-polynomial algorithms; conditional lower bounds (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0307 (application/pdf)

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:inm:orijoc:v:36:y:2024:i:3:p:836-848

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().