  In this paper, we consider the parameterized complexity of the following
scheduling problem. We must schedule a number of jobs on $m$ machines, where
each job has unit length, and the graph of precedence constraints consists of a
set of chains. Each precedence constraint is labelled with an integer that
denotes the exact (or minimum) delay between the jobs. We study different
cases; delays can be given in unary and in binary, and the case that we have a
single machine is discussed separately. We consider the complexity of this
problem parameterized by the number of chains, and by the thickness of the
instance, which is the maximum number of chains whose intervals between release
date and deadline overlap.
  We show that this scheduling problem with exact delays in unary is
$W[t]$-hard for all $t$, when parameterized by the thickness, even when we have
a single machine ($m = 1$). When parameterized by the number of chains, this
problem is $W[1]$-complete when we have a single or a constant number of
machines, and $W[2]$-complete when the number of machines is a variable. The
problem with minimum delays, given in unary, parameterized by the number of
chains (and as a simple corollary, also when parameterized by the thickness) is
$W[1]$-hard for a single or a constant number of machines, and $W[2]$-hard when
the number of machines is variable.
  With a dynamic programming algorithm, one can show membership in XP for exact
and minimum delays in unary, for any number of machines, when parameterized by
thickness or number of chains. For a single machine, with exact delays in
binary, parameterized by the number of chains, membership in XP can be shown
with branching and solving a system of difference constraints. For all other
cases for delays in binary, membership in XP is open.
