  The problem of scheduling conflicting jobs on parallel machines consists in
assigning a set of jobs to a set of machines so that no two conflicting jobs
are allocated to the same machine, and the maximum processing time among all
machines is minimized. We propose a new compact mixed integer linear
formulation based on the representatives model for the vertex coloring problem,
which overcomes a number of issues inherent in the natural assignment model. We
present a polyhedral study of the associated polytope, and describe classes of
valid inequalities inherited from the stable set polytope. We describe
branch-and-cut algorithms for the problem, and report on computational
experiments with benchmark instances. Our computational results on the hardest
instances of the benchmark set show that the proposed algorithms are superior
(either in running time or quality of the solutions) to the current
state-of-the-art methods. We find that our new method performs better than the
existing ones especially when the gap between the optimal value and the trivial
lower bound (i.e., the sum of all processing times divided by the number of
machines) increases.
