Graph multi-coloring for a job scheduling application

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.