Makespan minimisation for a parallel machine scheduling problem with preemption and job incompatibility

In this paper, an extension of the graph colouring problem is introduced to model a parallel machine scheduling problem with job incompatibility. To get closer to real-world applications, where the number of machines is limited and jobs have different processing times, each vertex of the graph requires multiple colours and the number of vertices with the same colour is bounded. In addition, several objectives related to scheduling are considered: makespan, number of pre-emptions and summation over the jobs' throughput times. Different solution methods are proposed, namely, two greedy heuristics, two tabu search methods and an adaptive memory algorithm. The latter uses multiple recombination operators, each one being designed for optimising a subset of objectives. The most appropriate operator is selected dynamically at each iteration, depending on its past performance. Experiments show that the proposed algorithm is effective and robust, while providing high-quality solutions on benchmark instances for the graph multi-colouring problem, a simplification of the considered problem.