UNIGE document Scientific Article
previous document  unige:92812  next document
add to browser collection

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

Potvin, Jean-Yves
Published in International Journal of Production Research. 2017, vol. 55, no. 6, p. 1588-1606
Abstract 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.
Keywords Graph theorySchedulingMakespanMetaheuristicsTabu searchEvolutionary algorithmsCombinatorial optimization
Full text
(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. https://archive-ouverte.unige.ch/unige:92812

46 hits

0 download


Deposited on : 2017-03-24

Export document
Format :
Citation style :