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||\sum 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||\sum 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 $\tilde{O}(P^{7/4})$ time scheduling algorithm through a new variant of convolution, dubbed Max-Min Skewed Convolution, which they solve in $\tilde{O}(n^{7/4})$ time. Our main technical contribution is a faster and simpler convolution algorithm running in $\tilde{O}(n^{5/3})$ time. It implies an $\tilde{O}(P^{5/3})$ time algorithm for $1||\sum 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||\sum 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 $\tilde{O}(n+p_{\max}^3)$ time algorithm. Moreover, in the setting with multiple machines, we use similar techniques to get an $n \cdot p_{\max}^{O(m)}$ time algorithm for $Pm||\sum 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.
翻译:本文的起始点是将一个处理时间和到期日期的UP 工作安排在一台机器上,以便最大限度地减少延迟工作的总处理时间, 也就是说, 1zz sum p_ j U_ j$。 Bringmann 等人( Agorithmica 2022) 将这一问题确定为经典的 $sum w_j dical_ j_ j j$ 问题的自然次赤道时间特例。 我们的主要技术贡献可能要求在整个处理时间里, 美元( Pdrout) 中进行时间反调 。 Bringmann 和 Al. 保持它们最近的 $tilde{O} (P\ 7/4} 美元) 的处理时间, 通过新的演算方式, Max- Min Skead Convolution 解答一个问题。 我们的主要技术贡献是, 一个快速和简单的递增的算算法问题, 以美元计 美元计价调 美元 =O} (n=xxxxx max lax lax lax lax lax lax lax lax lax lax lax lax lax) lax a max max max a max lax max max max