Résumé de rapport du LIF

Téléchargement / Download : pdf 1492k , ps.gz 1128k , bibtex

Abstract

The mutual exclusion scheduling problem can be formulated as follows in graph-theoretic terms: given a graph G and an integer k, determine a minimum coloring of G such that each color is used at most k times. When the graph G is an interval graph, this problem has some applications in workforce planning. Then, the subject of this thesis is to detail the complexity of the mutual exclusion scheduling problem for interval graphs and related classes.

Keywords

Mutual exclusion scheduling, graph coloring, workforce planning, interval graphs, classes of graphs.

Résumé

Le problème d'ordonnancement avec exclusion mutuelle peut être formulé comme suit en les termes de la théorie des graphes : étant donné un graphe G et un entier k, déterminer une coloration minimum de G tel que chaque couleur apparaisse au plus k fois. Lorsque le graphe G est un graphe d'intervalles, ce problème a des applications dans le domaine de la planification de personnel. Ainsi, cette thèse a pour objet l'étude détaillée de la complexité du problème d'ordonnancement avec exclusion mutuelle pour les graphes d'intervalles ou de classe apparentée.

Mots clés

Ordonnancement avec exclusion mutuelle, coloration de graphes, planification de personnel, graphes d'intervalles, classes de graphes.

Bibtex

@TECHREPORT{25-2005,
    AUTHOR	= {Frédéric Gardi},
    TITLE	= {{Ordonnancement avec exclusion mutuelle par un graphe d'intervalles ou d'une classe apparentée : complexité et algorithmes}},
    INSTITUTION	= {{LIF}},
    ADDRESS	= {Marseille, France},
    TYPE	= {Research report},
    NUMBER	= {25-2005},
    MONTH	= {Juin},
    YEAR	= {2005},
    NOTE	= {http://pageperso.lif.univ-mrs.fr/~edouard.thiel/RESP/Rapports/25-2005.html},
}