Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines

In the paper we consider the problem of scheduling n identical jobs on 3 uniform machines with speeds s1,s2, and s3 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(n2) time. If the graph is 3-chromatic, the problem becomes NP-hard even if s1>s2=s3. However, in this case there exists a 10/7-approximation algorithm running in O(n3) time. Moreover, this algorithm solves the problem almost surely to optimality if 3s1/4≤s2=s3.