论文标题
为了最大程度地减少迟到的处理时间，Max-Min偏斜卷积和三角形结构化ILP
On Minimizing Tardy Processing Time, Max-Min Skewed Convolution, and Triangular Structured ILPs
论文作者
论文摘要
本文的起点是在单台计算机上安排$ n $作业的问题，以最大程度地减少迟到作业的总处理时间，即$ 1 || \ sum p_j u_j $。 Bringmann等人确定了这个问题。 （算法2022）作为经典$ 1 || \ sum w_j u_j $问题的自然次级时间特殊情况，由于粒度的下限，它可能需要在总处理时间$ p $中时间进行时间二次。 Bringmann等人获得了他们的$ \ tilde {o}（p^{7/4}）$时间安排算法，通过卷积的新变体，被称为Max-Min偏斜卷积，他们以$ \ tilde {o}（o}（n^{7/4}）求解。我们的主要技术贡献是一种以$ \ tilde {o}（n^{5/3}）$时间运行的更快，更简单的卷积算法。它意味着$ \ tilde {o}（p^{5/3}）$ time算法，$ 1 || \ sum p_j u_j $，但也可能具有独立的利益。 受子集总和和背包问题的最新开发启发，我们研究了$ 1 || \ sum p_j u_j $由最大工作处理时间$ p _ {\ max} $参数化。通过从整数线性编程（ILP）借用的接近技术，我们显示了问题的结构属性，加上新的动态编程公式，导致$ \ tilde {o}（n+p _ {\ max}^3）$ time algorithm。此外，在带有多台计算机的设置中，我们使用类似的技术来获取$ n \ cdot p _ {\ max}^{o（m）} $ time算法，适用于$ pm || \ sum p_j u_j $。 最后，我们指出，所考虑的问题在其ILP公式的约束矩阵中表现出特定的三角形结构。鉴于最近的ILP研究，出现的问题是人们是否可以为此类ILP设计一种通用算法。我们对这个问题给出了负面答案：我们表明，调度ILP的结构已经略有概括导致了强烈的NP问题。
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.
