Multi-Neighborhood Search for the Makespan Minimization Problem on Parallel Identical Machines with Conflicting Jobs

Scheduling conflicting jobs on parallel identical machines is gaining increasing attention in the scientific literature. Among the several possible objective functions proposed so far, we investigate the makespan minimization. As solution approach we propose a Multi-Neighborhood Search method, which uses three neighborhoods (Move, Swap and 2-Opt, adapted from the Vehicle Routing literature) on an implicit solution representation. The search is guided by a Simulated Annealing metaheuristic. Experiments show that our method solves small instances consistently to the optimum and outperforms a constraint programming model on larger or highly conflicted instances, in much shorter runtimes.