Abstract
The problem asks to determine -- given jobs each with its own processing time, weight, and due date -- the minimum weighted number of tardy jobs in any single machine non-preemptive schedule for these jobs. This is a classical scheduling problem that generalizes both Knapsack, and Subset Sum. The best known pseudo-polynomial algorithm for , due to Lawler and Moore [Management Science'69], dates back to the late 60s and has a running time of , where is the number of jobs and is their maximal due date. A recent lower bound by Cygan \emph{et al.}~[ICALP'19] for Knapsack shows that cannot be solved in time, for any , under a plausible conjecture. This still leaves a gap between the best known lower bound and upper bound for the problem. In this paper we design a new simple algorithm for that uses -convolutions as its main tool, and outperforms the Lawler and Moore algorithm under several parameter ranges. In particular, depending on the specific method of computing -convolutions, its running time can be bounded by - . - . - . - . - . Here, denotes the number of \emph{different} due dates in the instance, denotes the maximum processing time of any job, and denotes the maximum weight of any job.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.