Auteur : Michaël GABY
Directrice de thèse : Nadia BRAUNER
L’encodage High-Multiplicity est un encodage naturel des données consistant, en ordonnancement, à réunir les tâches similaires (dites de même type) et, pour chaque type, décrire les caractéristiques d’une seule tâche et le nombre de tâches de ce type. Cet encodage est compact et lorsqu'il est considéré, soulève des problème quant à l'analyse de complexité des problèmes considérés. Nous étudions divers problèmes d'ordonnancement et de conditionnement (packing) et proposons des contributions variées autour de ces problèmes.
Nous montrons que le problème d'ordonnancement high-multiplicity avec indisponibilités des opérateurs est polynomial lorsque le nombre d'instants d'indisponibilité est fixé ou que le nombre de types de tâches est supérieur au nombre d'instants d'indisponibilité. Nous proposons des algorithmes efficaces pour le problème d'ordonnancement de tâches couplées identiques et exhibons des difficultés majeures liées à l'encodage high-multiplicity pour ce problème. Sur le problème de bin stretching, nous proposons différentes techniques et algorithmes, améliorant ainsi les meilleures bornes supérieures et inférieures connues. Nous étudions le problème de vector packing avec des récipients hétérogènes et proposons des heuristiques pour celui-ci. Enfin, nous proposons un algorithme de réduction très général pour les problèmes de conditionnement.
À travers ces différentes contributions, nous proposons de nouvelles techniques permettant de traiter des problèmes high-multiplicity et également des problèmes d'ordonnancement et de conditionnement en général.
Directrice de thèse : Nadia BRAUNER
Date : 20 octobre 2014
High-Multiplicity Scheduling and Packing Problems
L’encodage High-Multiplicity est un encodage naturel des données consistant, en ordonnancement, à réunir les tâches similaires (dites de même type) et, pour chaque type, décrire les caractéristiques d’une seule tâche et le nombre de tâches de ce type. Cet encodage est compact et lorsqu'il est considéré, soulève des problème quant à l'analyse de complexité des problèmes considérés. Nous étudions divers problèmes d'ordonnancement et de conditionnement (packing) et proposons des contributions variées autour de ces problèmes.
Nous montrons que le problème d'ordonnancement high-multiplicity avec indisponibilités des opérateurs est polynomial lorsque le nombre d'instants d'indisponibilité est fixé ou que le nombre de types de tâches est supérieur au nombre d'instants d'indisponibilité. Nous proposons des algorithmes efficaces pour le problème d'ordonnancement de tâches couplées identiques et exhibons des difficultés majeures liées à l'encodage high-multiplicity pour ce problème. Sur le problème de bin stretching, nous proposons différentes techniques et algorithmes, améliorant ainsi les meilleures bornes supérieures et inférieures connues. Nous étudions le problème de vector packing avec des récipients hétérogènes et proposons des heuristiques pour celui-ci. Enfin, nous proposons un algorithme de réduction très général pour les problèmes de conditionnement.
À travers ces différentes contributions, nous proposons de nouvelles techniques permettant de traiter des problèmes high-multiplicity et également des problèmes d'ordonnancement et de conditionnement en général.