Makespan minimisation for a parallel machine scheduling problem with preemption and job incompatibility. Issue 6 (19th March 2017)

• Record Type: Journal Article
• Authors: Thevenin, Simon; Zufferey, Nicolas; Potvin, Jean-Yves
• Is Part Of: International journal of production research. Volume 55:Issue 6(2017)
• Page Start: 1588
• Page End: 1606
• Publication Date: 2017-03-19
• Subjects: graph theory -- scheduling -- makespan -- metaheuristics -- tabu search -- evolutionary algorithms -- combinatorial optimisation; Factory management -- Periodicals; 658.57
• DOI: 10.1080/00207543.2016.1181285
• Languages: English
• ISSNs: 0020-7543

Abstract

Abstract : 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.