  We consider scheduling on identical and unrelated parallel machines with job
assignment restrictions. These problems are NP-hard and they do not admit
polynomial time approximation algorithms with approximation ratios smaller than
$1.5$ unless P$=$NP. However, if we impose limitations on the set of machines
that can process a job, the problem sometimes becomes easier in the sense that
algorithms with approximation ratios better than $1.5$ exist. We introduce
three graphs, based on the assignment restrictions and study the computational
complexity of the scheduling problem with respect to structural properties of
these graphs, in particular their tree- and rankwidth. We identify cases that
admit polynomial time approximation schemes or FPT algorithms, generalizing and
extending previous results in this area.
