A hypocoloring model for batch scheduling

Dominique De Werra, Ecole Polytechnique Fédérale de Lausanne
Marc Demange, ESSEC, Dept. SID et CERMSEM
Jérôme Monnot, LAMSADE
Vangelis Th. Paschos, LAMSADE

Résumé. Dans le cadre d'un problème d'ordonnancement par paquets, nous considérons une "sous-coloration" pondérée d'un graphe G ; chaque sommet v a un poids w(v) ; chaque couleur S est un ensemble de sommets qui induit une collection de cliques disjointes. Le poids w(S) est défini par max{w(K) = S_{v  K} w(v) ô K   S}. Dans le problème d'ordonnancement, le temps de réalisation est donné par S^k_i=1 w(S_i) où S = (S₁,..., S_k) est une partition des sommets de G en différentes couleurs comme décrit ci-dessus. Nous établissons des propriétés de telles colorations pour différentes classes de graphes ("line-graphes" de cactus, "block-graphes") ; nous présentons des résultats de complexité et d'approximation. Le problème de décision associé est montré NP-complet pour les graphes bipartis de degré maximum 39 et pour les graphes planaires sans triangle de degré maximum k pour tout k supérieur ou égal à 3. Nous proposons des algorithmes polynomiaux pour des graphes de degré maximum 2 et pour les forêts de degré maximum k. Nous décrivons un algorithme (exponentiel) fondé sur le principe de séparation pour les graphes sans triangle.
Mots clés : Ordonnancement par paquets, coloration de graphes, sous-coloration, hypocoloration, coloration pondérée, approximation.

Abstract. Starting from a batch scheduling problem, we consider a weighted subcoloring in a graph G ; each node v has a weight w(v) ; each color class S is a subset of nodes which generates a collection of node disjoint cliques. The weight w(S) is defined as max{w(K) = S_{v  K} w(v) ô K   S}. In the scheduling problem, the completion time is given by S^k_i=1 w(S_i) where S = (S₁,..., S_k) is a partition of the node set of graph G into color classes as defined above. Properties of such colorings concerning special classes of graphs (line graphs of cacti, block graphs) are stated ; complexity and approximability results are presented. The associated decision problem is shown to be NP-complete for bipartite graphs with maximum degree at most 39 and triangle-free planar graphs with maximum degree k for any k greater than or equal to 3. Polynomial algorithms are given for graphs with maximum degree two and for the forests with maximum degree k. An (exponential) algorithm based on a simple separation principle is sketched for graphs without triangles.
Keywords : Batch scheduling, graph coloring, subcolorings, hypocolorings, weighted colorings, approximability.

AMS Classification : 03D15, 68Q25, 68R10.