  We consider the classic problem of scheduling jobs with precedence
constraints on identical machines to minimize makespan, in the presence of
communication delays. In this setting, denoted by $\mathsf{P} \mid
\mathsf{prec}, c \mid C_{\mathsf{max}}$, if two dependent jobs are scheduled on
different machines, then at least $c$ units of time must pass between their
executions. Despite its relevance to many applications, this model remains one
of the most poorly understood in scheduling theory. Even for a special case
where an unlimited number of machines is available, the best known
approximation ratio is $2/3 \cdot (c+1)$, whereas Graham's greedy list
scheduling algorithm already gives a $(c+1)$-approximation in that setting. An
outstanding open problem in the top-10 list by Schuurman and Woeginger and its
recent update by Bansal asks whether there exists a constant-factor
approximation algorithm.
  In this work we give a polynomial-time $O(\log c \cdot \log m)$-approximation
algorithm for this problem, where $m$ is the number of machines and $c$ is the
communication delay. Our approach is based on a Sherali-Adams lift of a linear
programming relaxation and a randomized clustering of the semimetric space
induced by this lift.
