•Minimizing the makespan of scheduling identical conflicting jobs on uniform machines.•New complexity results on complete bipartite graphs with computational illustration.•Lower bounds and three MILP models to solve the problem with arbitrary graphs.•Two heuristic approaches meticulously designed to deliver good quality solutions.•Computational experiments conducted to assess the performance of the given methods. This paper addresses the problem of scheduling n identical jobs on a set of m parallel uniform machines. The jobs are subjected to conflicting constraints modelled by an undirected graph G, in which adjacent jobs are not allowed to be processed on the same machine. Minimising the maximum completion time in the schedule (makespan Cmax) is known to be NP-hard. We prove that when G is restricted to complete bipartite graphs the problem remains NP-hard for arbitrary number of machines, however, if m is fixed an optimal solution can be obtained in polynomial time. To solve the general case of the problem, we propose mixed-integer linear programming (MILP) formulations alongside with lower bounds and heuristic approaches. Furthermore, computational experiments are carried out to measure the performance of the proposed methods.