Exact and metaheuristic approaches to minimizing makespan in parallel machine scheduling with conflicting jobs

Abstract We address the scheduling conflicting jobs on parallel identical machines problem with makespan minimization, a classical and computationally challenging variant of parallel machine scheduling. We develop and evaluate three distinct solution methodologies: a novel constraint programming (CP) formulation, and two metaheuristics: a multi‐neighborhood simulated annealing that relies on an implicit solution representation and a greedy decoder, and a CP‐based large neighborhood search that employs operators specifically tailored for the problem. The methods are tuned using statistically rigorous procedures and compared to highlight the strengths and weaknesses of each approach. For this purpose, we introduce and make publicly available a novel, challenging dataset, appropriately divided into training and validation instances. This dataset supports our experiments and provides a foundation for future benchmarking. Computational results show that the proposed CP formulation significantly outperforms an existing CP method, proving optimality on several instances within short computing times. Meanwhile, the MNSA metaheuristic consistently delivers high‐quality solutions, especially on instances where the exact method has difficulty converging, with more consistent gaps in the presence of high conflict rates.