Scientific article

Graph multi-coloring for a job scheduling application

Published inDiscrete applied mathematics, vol. 234, p. 218-235
Publication date2018

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.

  • Metaheuristics
  • Job scheduling
  • Graph coloring
Citation (ISO format)
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
Main files (1)
Article (Accepted version)
ISSN of the journal0166-218X

Technical informations

Creation03/20/2017 5:45:00 PM
First validation03/20/2017 5:45:00 PM
Update time03/15/2023 1:29:42 AM
Status update03/15/2023 1:29:41 AM
Last indexation08/30/2023 2:15:53 PM
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack