Time slot scheduling of compatible jobs

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

Résumé. Nous introduisons une version pondérée du problème de coloration d'un graphe motivée par différents types de problèmes d'ordonnancement : chaque sommet vd'un graphe Gcorrespond à des tâches à réaliser (avec une durée de réalisation w(v)), les arêtes représentent des contraintes de non-simultanéïté (incompatibilités). On doit alors affecter chaque tâche à une fenêtre temporelle de sorte que les tâches d'un même intervalle sont compatibles ; la largeur d'une fenêtre de temps est alors la durée maximum des tâches correspondantes. Le nombre kde telles fenêtres doit être déterminé. Il s'agit alors de construire une k-coloration S = (S_1,..., S_k)de Gminimisant w(S₁+....+ w(S_k)où w(S_i) = max {w(v) : v appartient à V}.Nous discutons les propriétés des solutions optimales et présentons des résultats de complexité et d'approximation. En particulier, le problème de décision associé est prouvé NP-complet pour des graphes bipartis, pour des graphes aux arêtes de graphes bipartis ou encore pour des "split-graphes".
Mots clés : Coloration pondérée des sommets, ordonnancement chromatique, approximations, coloration d'arêtes, ordonnancement par paquets.

Abstract. A version of weighted coloring of a graph is introduced which is motivated by some types of scheduling problem : each node vof a graph Gcorresponds to some operation to be processed (with a processing time w(v)), edges represent non-simultaneity requirements (incompatibilities). We have to assign each operation to one time slot in such a way that in each time slot all operations assigned to this slot are compatible ; the length of a time slot will be the maximum of the processing times of its operations. The number kof time slots to be used has to be determined as well. So we have to find a k-coloring S = (S_1,..., S_k)of Gsuch that w(S₁+....+ w(S_k)is minimized where w(S_i) = max {w(v) : v appartient à V}. Properties of optimal solutions are discussed, complexity and approximability results are presented. Heuristic methods are given for establishing some of these results. The associated decision problems are shown to be NP-complete for bipartite graphs and for line-graphs of bipartite graphs and for split graphs.
Keywords : Weighted coloring, chromatic scheduling, approximations, edge coloring, bath scheduling.

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