  In this paper we consider the problem of scheduling on parallel machines with
a presence of incompatibilities between jobs. The incompatibility relation can
be modeled as a complete multipartite graph in which each edge denotes a pair
of jobs that cannot be scheduled on the same machine. Our research stems from
the work of Bodlaender et al.~[1992, 1993]. In particular, we pursue the line
investigated partially by Mallek et al.~[2019], where the graph is complete
multipartite so each machine can do jobs only from one partition. We also tie
our results to the recent approach for so-called identical machines with class
constraints by Jansen et al.~[2019], providing a link between our case and
their generalization. In the paper we provide several algorithms constructing
schedules, optimal or approximate with respect to the two most popular criteria
of optimality: Cmax (the makespan) and {\Sigma}Cj(the total completion time).
We consider a variety of machine types in our paper: identical, uniform,
unrelated, and a natural subcase of unrelated machines. Our results consist of
delimitation of the easy (polynomial) and NP-hard problems within these
constraints. In the case when the problem is hard, we also provide algorithm,
either with a guaranteed constant worst-case approximation ratio or even in
some cases a PTAS. In particular, we fill the gap on research for the problem
of finding a schedule with smallest total completion time on uniform machines.
We address this problem by developing a linear programming relaxation technique
with an appropriate rounding, which to our knowledge is a novelty for this
criterion in the considered setting.
