论文标题
在均匀机器上进行高质地调度的结构性结果
Structural Results for High-Multiplicity Scheduling on Uniform Machines
论文作者
论文摘要
通过最大的处理时间$ p_ {max} $和不同的工作处理时间$ d $的参数化，我们为在统一机器上安排高质量的接近技术，以使目标最小化（$ c_ {max} $）和Santa Claus（$ c_ {max} $）和Santa Claus（$ C_ {min} $），以获取新的结构性结果。我们方法中的新颖性是，我们仅针对一个子机构处理一个分数解决方案，而该子构成本身并不是先验的。尽管与通常的接近技术相反，分数解的构建和计算并未在多项式时间内完成，但这也使我们能够制定出相当强大且一般的接近性陈述。最终，这使我们能够减少需要将需要分配给每种机器和工作类型的多项式的作业数量，通过根据分数解决方案对作业进行预先签名的作业，本质上是返回有界数的数字（最多最多$ o（p_ {max}^{max}^{o（d^2^2）$）。 我们可以使用我们的结构结果来获得具有运行时间的算法，为$ p_ {max}^{o（d^2）} poly | i | $，与Knop等人到目前为止最著名的相匹配。 （操作。Res。Lett。'21）。 此外，我们提出了一个$ p_ {max}^{o（d^2）} poly | i | $ time算法，用于嫉妒最小化$ c_ {eNVY} $在均匀机器上的高质量设置中，表明此问题是\ textsc {fpts {fpt} in $ p_ {max {max} $。 最终，我们还提出了一种通用机制，以绑定SO \ Emph {load平衡问题}的配置ILP中最大系数，该机制由$（dp_ {max}）^{o（d）} $绑定，我们希望这对算法的开发感兴趣。
Parameterizing by the largest processing time $p_{max}$ and the number of different job processing times $d$, we propose a proximity technique for High-Multiplicity Scheduling on Uniform Machines for the objectives Makespan Minimization ($C_{max}$) and Santa Claus ($C_{min}$) to obtain new structural results for these problems. The novelty in our approach is that we deal with a fractional solution for only a sub-instance, where the sub-instance itself is not known a priori. While the construction and computation of the fractional solution -- in contrast to usual proximity techniques -- is not done in polynomial time, this also allows us to formulate a comparably strong and general proximity statement. Eventually, this allows us to reduce the number of jobs that need to be distributed to a polynomial in $p_{max}$ for each machine and job type, by preassigning jobs according to the fractional solution, essentially returning a bounded number (at most $O(p_{max}^{O(d^2)})$) of kernels, one for each (guessed) sub-instance. We can use our structural results to obtain an algorithm with running time is $p_{max}^{O(d^2)}poly|I|$, matching the best-known so far by Knop et al. (Oper. Res. Lett. '21). Moreover, we propose an $p_{max}^{O(d^2)} poly |I|$ time algorithm for Envy Minimization $C_{envy}$ in the High-Multiplicity Setting on Uniform Machines, showing that this problem is \textsc{fpt} in $p_{max}$. Eventually, we also propose a general mechanism to bound the largest coefficient in the Configuration ILP for so called \emph{Load Balancing Problems} by $(dp_{max})^{O(d)}$, which we hope to be of interest for the development of algorithms.
