论文标题
吞吐量最大化的近似值
Approximations for Throughput Maximization
论文作者
论文摘要
在本文中，我们研究了吞吐量最大化的经典问题。在此问题中，我们有一个$ n $ jobs的$ j $ j $，每个都有一个发布时间$ r_j $，deadline $ d_j $和处理时间$ p_j $。它们必须在$ m $相同的并行机器上进行非抢先安排。目标是找到一个时间表，该时间表最大化其在其$ [r_j，d_j] $ window中完全安排的作业数量。该问题已经进行了广泛的研究（即使是$ M = 1 $）。该问题的几个特殊案例仍然开放。 Bar-Noy等。 [STOC1999]提出了一种算法，其比率为$ 1-1/（1+1/m）^m $，用于$ M $ $机器，该算法接近$ 1-1/e $的$ M $增加。对于$ m = 1 $，chuzhoy-Ostrovsky-rabani [focs2001]提出了一种算法，其近似值$ 1- \ frac {1} {e} {e} - \ varepsilon $（对于任何$ \ varepsilon> 0 $）。最近，Im-Li-Moseley [IPCO2017]提出了一种比率$ 1-1/e- \ varepsilon_0 $的算法，对于任何固定$ m $，对于某些绝对常数$ \ varepsilon_0> 0 $。他们还提出了一种比率$ 1-o（\ sqrt {\ log m/m}）的算法 - \ varepsilon $ for General $ m $，它接近1 $ m $的生长。 $ m = o（1）$的问题的近似性仍然是一个主要的开放问题。即使对于$ m = 1 $和$ c = o（1）$差异处理时间的情况即使是打开问题（sgall [esa2012]）。在本文中，我们研究了$ m = o（1）$的情况，并表明，如果有$ c $不同的处理时间，即$ p_j $ s来自一组尺寸$ c $，那么就有一个$（1- \ varepsilon）$ - 近似值，在时间$ o（n^7 \ varepsilon $ o（$）$ o（$ o（mc^7 \ varepsilon^ug） 最后期限。因此，对于常数$ m $和常数$ c $，这会产生PTA。我们的算法基于证明近乎最佳解决方案的结构属性，该解决方案允许使用修剪的动态编程。
In this paper we study the classical problem of throughput maximization. In this problem we have a collection $J$ of $n$ jobs, each having a release time $r_j$, deadline $d_j$, and processing time $p_j$. They have to be scheduled non-preemptively on $m$ identical parallel machines. The goal is to find a schedule which maximizes the number of jobs scheduled entirely in their $[r_j,d_j]$ window. This problem has been studied extensively (even for the case of $m=1$). Several special cases of the problem remain open. Bar-Noy et al. [STOC1999] presented an algorithm with ratio $1-1/(1+1/m)^m$ for $m$ machines, which approaches $1-1/e$ as $m$ increases. For $m=1$, Chuzhoy-Ostrovsky-Rabani [FOCS2001] presented an algorithm with approximation with ratio $1-\frac{1}{e}-\varepsilon$ (for any $\varepsilon>0$). Recently Im-Li-Moseley [IPCO2017] presented an algorithm with ratio $1-1/e-\varepsilon_0$ for some absolute constant $\varepsilon_0>0$ for any fixed $m$. They also presented an algorithm with ratio $1-O(\sqrt{\log m/m})-\varepsilon$ for general $m$ which approaches 1 as $m$ grows. The approximability of the problem for $m=O(1)$ remains a major open question. Even for the case of $m=1$ and $c=O(1)$ distinct processing times the problem is open (Sgall [ESA2012]). In this paper we study the case of $m=O(1)$ and show that if there are $c$ distinct processing times, i.e. $p_j$'s come from a set of size $c$, then there is a $(1-\varepsilon)$-approximation that runs in time $O(n^{mc^7\varepsilon^{-6}}\log T)$, where $T$ is the largest deadline. Therefore, for constant $m$ and constant $c$ this yields a PTAS. Our algorithm is based on proving structural properties for a near optimum solution that allows one to use a dynamic programming with pruning.
