2022/11/09 by Kim-Manuel Klein, Klein, Kim-Manuel, Adam Polak +3 · 2 citations
Engineering · Computer Science · #Scheduling and Optimization Algorithms #Optimization and Packing Problems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2211.05053
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||∑ pj Uj. This problem was identified by Bringmann et al. (Algorithmica 2022) as a natural subquadratic-time special case of the classic 1||∑ wj Uj problem, which likely requires time quadratic in the total processing time P, because of a fine-grained lower bound. Bringmann et al.~obtain their O(P7/4) time scheduling algorithm through a new variant of convolution, dubbed Max-Min Skewed Convolution, which they solve in O(n7/4) time. Our main technical contribution is a faster and simpler convolution algorithm running in O(n5/3) time. It implies an O(P5/3) time algorithm for 1||∑ pj Uj, but may also be of independent interest. Inspired by recent developments for the Subset Sum and Knapsack problems, we study 1||∑ pj Uj parameterized by the maximum job processing time pmax. 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 O(n+pmax3) time algorithm. Moreover, in the setting with multiple machines, we use similar techniques to get an n ⋅ pmaxO(m) time algorithm for Pm||∑ pj Uj. 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.