  In the restricted assignment problem, the input consists of a set of machines
and a set of jobs each with a processing time and a subset of eligible
machines. The goal is to find an assignment of the jobs to the machines
minimizing the makespan, that is, the maximum summed up processing time any
machine receives. Herein, jobs should only be assigned to those machines on
which they are eligible. It is well-known that there is no polynomial time
approximation algorithm with an approximation guarantee of less than 1.5 for
the restricted assignment problem unless P=NP. In this work, we show hardness
results for variants of the restricted assignment problem with particular types
of restrictions.
  In the case of interval restrictions the machines can be totally ordered such
that jobs are eligible on consecutive machines. We resolve the open question of
whether the problem admits a polynomial time approximation scheme (PTAS) in the
negative (unless P=NP). There are several special cases of this problem known
to admit a PTAS.
  Furthermore, we consider a variant with resource restriction where each
machine has capacities and each job demands for a fixed number of resources. A
job is eligible on a machine if its demand is at most the capacity of the
machine for each resource. For one resource, this problem is known to admit a
PTAS, for two, the case of interval restrictions is contained, and in general,
the problem is closely related to unrelated scheduling with a low rank
processing time matrix. We show that there is no polynomial time approximation
algorithm with a rate smaller than 48/47 or 1.5 for scheduling with resource
restrictions with 2 or 4 resources, respectively, unless P=NP. All our results
can be extended to the so called Santa Claus variants of the problems where the
goal is to maximize the minimal processing time any machine receives.
