Scientific article

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

Published inInternational journal of production research, vol. 55, no. 6, p. 1588-1606
Publication date2017

In this paper, an extension of the graph coloring 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 colors and the number of vertices with the same color is bounded. In addition, several objectives related to scheduling are considered: makespan, number of preemptions, 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 optimizing 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-coloring problem, a simplification of the considered problem.

  • Graph theory
  • Scheduling
  • Makespan
  • Metaheuristics
  • Tabu search
  • Evolutionary algorithms
  • Combinatorial optimization
Citation (ISO format)
THEVENIN, Simon, ZUFFEREY, Nicolas, POTVIN, Jean-Yves. Makespan minimisation for a parallel machine scheduling problem with preemption and job incompatibility. In: International journal of production research, 2017, vol. 55, n° 6, p. 1588–1606. doi: 10.1080/00207543.2016.1181285
Main files (1)
Article (Accepted version)
ISSN of the journal0020-7543

Technical informations

Creation03/20/2017 5:43:00 PM
First validation03/20/2017 5:43:00 PM
Update time03/15/2023 1:29:42 AM
Status update03/15/2023 1:29:41 AM
Last indexation01/16/2024 11:33:51 PM
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack