On Minimizing Tardy Processing Time, Max-Min Skewed Convolution, and Triangular Structured ILPs
share
The starting point of this paper is the problem of scheduling n jobs with processing times and due dates on a single machine so as to minimize the total processing time of tardy jobs, i.e., 1||∑ p_j U_j. This problem was identified by Bringmann et al. (Algorithmica 2022) as a natural subquadratic-time special case of the classic 1||∑ w_j U_j problem, which likely requires time quadratic in the total processing time P, because of a fine-grained lower bound. Bringmann et al. obtain their Õ(P^7/4) time scheduling algorithm through a new variant of convolution, dubbed Max-Min Skewed Convolution, which they solve in Õ(n^7/4) time. Our main technical contribution is a faster and simpler convolution algorithm running in Õ(n^5/3) time. It implies an Õ(P^5/3) time algorithm for 1||∑ p_j U_j, but may also be of independent interest. Inspired by recent developments for the Subset Sum and Knapsack problems, we study 1||∑ p_j U_j parameterized by the maximum job processing time p_max. With proximity techniques borrowed from integer linear programming (ILP), we show structural properties of the problem that, coupled with a new dynamic programming formulation, lead to an Õ(n+p_max^3) time algorithm. Moreover, in the setting with multiple machines, we use similar techniques to get an n · p_max^O(m) time algorithm for Pm||∑ p_j U_j. Finally, we point out that the considered problems exhibit a particular triangular block structure in the constraint matrices of their ILP formulations. In light of recent ILP research, a question that arises is whether one can devise a generic algorithm for such a class of ILPs. We give a negative answer to this question: we show that already a slight generalization of the structure of the scheduling ILP leads to a strongly NP-hard problem.
READ FULL TEXT