fr
Article scientifique
Anglais

Graph multi-coloring for a job scheduling application

Publié dansDiscrete applied mathematics, vol. 234, p. 218-235
Date de publication2018
Résumé

In this paper, we introduce a graph multi-coloring problem where each vertex must be assigned a given number of different colors, represented as integers, and no two adjacent vertices can share a common color. In the variant considered, the number of available colors is such that not all vertices can be colored. Furthermore, there is a bound on the number of vertices which can be assigned the same color. A gain is associated with each vertex and the first objective is to maximize the total gain over all colored vertices. Secondary objectives consider the sequence of colors assigned to each vertex. More precisely, the range and the number of interruptions must be minimized, where the range corresponds to the difference between the largest and smallest colors assigned to a vertex. This variant of the graph multi-coloring problem is of interest because it can model practical job scheduling applications. An integer linear programming formulation is first proposed to address small-size instances. A construction heuristic, as well as local search methods, are then reported to tackle larger instances. The local search methods are based on several neighborhood structures, each one focusing on a specific property of the problem. Different ways to combine these neighborhood structures are also investigated.

Mots-clés
  • Metaheuristics
  • Job scheduling
  • Graph coloring
Citation (format ISO)
THEVENIN, Simon, ZUFFEREY, Nicolas, POTVIN, Jean-Yves. Graph multi-coloring for a job scheduling application. In: Discrete applied mathematics, 2018, vol. 234, p. 218–235. doi: 10.1016/j.dam.2016.05.023
Fichiers principaux (1)
Article (Accepted version)
accessLevelPrivate
Identifiants
ISSN du journal0166-218X
565vues
0téléchargements

Informations techniques

Création20/03/2017 17:45:00
Première validation20/03/2017 17:45:00
Heure de mise à jour15/03/2023 01:29:42
Changement de statut15/03/2023 01:29:41
Dernière indexation16/01/2024 23:33:52
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack