  In the paper we consider the problem of scheduling $n$ identical jobs on 3
uniform machines with speeds $s_1, s_2,$ and $s_3$ to minimize the schedule
length. We assume that jobs are subjected to some kind of mutual exclusion
constraints, modeled by a cubic incompatibility graph. We show that if the
graph is 2-chromatic then the problem can be solved in $O(n^2)$ time. If the
graph is 3-chromatic, the problem becomes NP-hard even if $s_1>s_2=s_3$.
However, in this case there exists a $4/3$-approximation algorithm running in
$O(n^3)$ time. Moreover, this algorithm solves the problem almost surely to
optimality if $3s_1/4 \leq s_2 = s_3$.
