Abstract

The 1∣∣ΣwjUj1 \mid \mid Σw_j U_j problem asks to determine -- given nn 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 1∣∣ΣwjUj1 \mid \mid Σw_j U_j, due to Lawler and Moore [Management Science'69], dates back to the late 60s and has a running time of O(dmax⁡n)O(d_{\max}n), where nn is the number of jobs and dmax⁡d_{\max} is their maximal due date. A recent lower bound by Cygan \emph{et al.}~[ICALP'19] for Knapsack shows that 1∣∣ΣwjUj1 \mid \mid Σw_j U_j cannot be solved in O~((n+dmax⁡)2−ε)\widetilde{O}((n+d_{\max})^{2-\varepsilon}) time, for any ε>0\varepsilon > 0, 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 1∣∣ΣwjUj1 \mid \mid Σw_j U_j that uses (max⁡,+)(\max,+)-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 (max⁡,+)(\max,+)-convolutions, its running time can be bounded by - O~(n+d#dmax⁡2)\widetilde{O}(n+d_{\#}d_{\max}^2). - O~(d#n+d#2dmax⁡wmax⁡)\widetilde{O}(d_{\#}n +d^2_{\#}d_{\max}w_{\max}). - O~(d#n+d#dmax⁡pmax⁡)\widetilde{O}(d_{\#}n +d_{\#}d_{\max}p_{\max}). - O~(n2+dmax⁡wmax⁡2)\widetilde{O}(n^2 +d_{\max}w^2_{\max}). - O~(n2+d#(dmax⁡wmax⁡)1.5)\widetilde{O}(n^2 + d_{\#}(d_{\max}w_{\max})^{1.5}). Here, d#d_{\#} denotes the number of \emph{different} due dates in the instance, pmax⁡p_{\max} denotes the maximum processing time of any job, and wmax⁡w_{\max} denotes the maximum weight of any job.

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 reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.