论文标题
在不均匀的工作和机器延迟下安排
Scheduling under Non-Uniform Job and Machine Delays
论文作者
论文摘要
我们研究了在存在不均匀的作业和机器通信延迟的情况下，在异源机器上安排优先限制的工作的问题。我们被以输入$ n $单位大小的优先级作业和$ m $相关的计算机提供给我们，因为机器$ i $一次可以一次执行高达$ m_i $ $。每个计算机$ i $都有一个in-delay $ρ^{\ mathrm {in}} _ i $和out-delay $ρ^{\ mathrm {out}} _ i $。同样，每个作业$ v $都有一个in-delay $ρ^{\ mathrm {in}} _ v $和out-delay $ρ^{\ mathrm {out}} _ v $。在时间表中，如果每个先前的$ u $ u $ u $ u $ o $ v $在$ i $上完成$ i $或在时间$ t $之前或任何机器$ j $之前完成$ i $ t $，则可以在计算机$ i $上执行工作$ v $，或者在时间$ t $之前完成了工作$ v $ ρ^{\ mathrm {out}} _ u +ρ^{\ mathrm {in}} _v）$。目标是构建一个时间表，以最大程度地减少MakePan。 我们考虑允许重复作业的时间表以及没有的时间表。当允许重复时，我们会提供渐近$ \ mathrm {polylog}（n）$ - 近似算法时均在允许重复时且不得。我们还获得了一个真正的$ \ mathrm {polylog}（n）$ - 对称机器和工作延迟的近似。这些是第一个针对不均匀通信延迟进行调度的Polyogarithmic近似算法。 我们还考虑了一个更通用的模型，其中延迟可以是作业的任意函数，并且机器执行它：如果所有$ v $ t $ $ v $ t $ $ v $ t $ t $ i $ t $ i $ y $ $ i $ ty $ t -$ t -time $ t -1 $或任何机器上的任何机器$ t -p -ρ_p -ρ_{v，i} $在$ i $上执行所有$ i $ t $。我们从[DKRSTZ22]中首先定义的唯一机器优先限制的调度（UMP）问题介绍了近似保护的减少。减少需要在此延迟设置的情况下进行对数硬度，以及如果UMP的猜想硬度固定，则需要多项式硬度。
We study the problem of scheduling precedence-constrained jobs on heterogenous machines in the presence of non-uniform job and machine communication delays. We are given as input $n$ unit size precedence-ordered jobs and $m$ related machines such that machine $i$ can execute up to $m_i$ jobs at a time. Each machine $i$ has an in-delay $ρ^{\mathrm{in}}_i$ and out-delay $ρ^{\mathrm{out}}_i$. Likewise, each job $v$ has an in-delay $ρ^{\mathrm{in}}_v$ and out-delay $ρ^{\mathrm{out}}_v$. In a schedule, job $v$ may be executed on machine $i$ at time $t$ if each predecessor $u$ of $v$ is completed on $i$ before time $t$ or on any machine $j$ before time $t - (ρ^{\mathrm{in}}_i + ρ^{\mathrm{out}}_j + ρ^{\mathrm{out}}_u + ρ^{\mathrm{in}}_v)$. The goal is to construct a schedule that minimizes makespan. We consider schedules that allow duplication of jobs as well as schedules which do not. When duplication is allowed, we provide an asymptotic $\mathrm{polylog}(n)$-approximation algorithms both when duplication is allowed and when it is not. We also obtain a true $\mathrm{polylog}(n)$-approximation for symmetric machine and job delays. These are the first polylogarithmic approximation algorithms for scheduling with non-uniform communication delays. We also consider a more general model, where the delay can be an arbitrary function of the job and the machine executing it: job $v$ can be executed on machine $i$ at time $t$ if all of $v$'s predecessors are executed on $i$ by time $t-1$ or on any machine by time $t - ρ_{v,i}$. We present an approximation-preserving reduction from the Unique Machines Precedence-constrained Scheduling (UMPS) problem, first defined in [DKRSTZ22], to this job-machine delay model. The reduction entails logarithmic hardness for this delay setting, as well as polynomial hardness if the conjectured hardness of UMPS holds.
