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

Graph multi-coloring for a job scheduling application

Potvin, Jean-Yves
Published in Discrete Applied Mathematics. 2018, vol. 234, p. 218-235
Abstract 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.
Keywords MetaheuristicsJob schedulingGraph coloring
Full text
(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 https://archive-ouverte.unige.ch/unige:92813

373 hits

0 download


Deposited on : 2017-03-24

Export document
Format :
Citation style :