  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 $\rho^{\mathrm{in}}_i$ and
out-delay $\rho^{\mathrm{out}}_i$. Likewise, each job $v$ has an in-delay
$\rho^{\mathrm{in}}_v$ and out-delay $\rho^{\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 -
(\rho^{\mathrm{in}}_i + \rho^{\mathrm{out}}_j + \rho^{\mathrm{out}}_u +
\rho^{\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 - \rho_{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.

Data Structures and Algorithms