Dans cette thèse, nous proposons et évaluons des algorithmes pour résoudre des problèmes d'ordonnancement en ligne. Pendant des décennies, les études en ordonnancement considèrent des modèles déterministes où toutes les informations nécessaires pour la définition du problème sont supposées connues à l'avance. Cette hypothèse n'est généralement pas réaliste. Ceci a motivé les études sur l'ordonnancement en ligne. Dans un problème d'ordonnancement en ligne, un algorithme doit prendre des décisions sans connaissance du futur. L'analyse compétitive est généralement la méthode utilisée pour évaluer les performances de tels algorithmes. Dans cette analyse, la performance d'un algorithme en ligne est mesurée par le ratio compétitif qui est le ratio dans le pire cas entre la performance de la solution obtenue et celle d'une solution optimale hors ligne. Nous considérons principalement deux paradigmes en ligne: celui où les tâches se présentent dans la liste et celui où les tâches arrivent au fur et à mesure. Sur la base de ces deux paradigmes, nous considérons différents modèles : une seule machine, deux machines identiques parallèles, deux machines uniformes parallèles, batch machines et open shop. Pour chacun des problèmes, nous démontrons une borne inférieure de ratios compétitifs et proposons des algorithmes en ligne. Ensuite, nous évaluons la performance de ces algorithmes à l'aide de l'analyse compétitive. Pour certains problèmes, nous montrons que les algorithmes proposés sont optimaux dans le sens où le ratio compétitif est égal à la borne inférieure.

Cette thèse est consacrée au problème de la planification et de l'ordonnancement des tâches sous contraintes temporelles et incertitude. Les contraintes temporelles que nous traitons sont de deux types : qualitatives et quantitatives. L'incertitude sur la durée des tâches se traduit par une distribution de probabilités sur un ensemble fini.<br />Les tâches et les contraintes sont représentées à l'aide d'un graphe ET/OU et les durées des tâches sont pondérées par des probabilités d'exécution. Celles-ci expriment une incertitude sur la connaissance exacte des durées d'exécution des tâches qui ne seront réellement connues que lors de l'exécution effective. Ainsi, une tâche s'exécute durant l'une de ses durées d'exécution possibles avec la probabilité associée à celle-ci. Étant donné ce graphe, notre objectif est de déterminer un plan de tâches qui satisfait toutes les contraintes et qui répond aux critères de choix exigés par l'utilisateur en terme de temps, de coût et de probabilité. L'application de ce plan doit garantir le monde de façon que le but soit atteint tout en satisfaisant les contraintes du domaine.<br />Nous avons appliqué notre méthode de planification à un cas pratique relativement complexe qui concerne la planification d'un ensemble d'agents travaillant ensemble dans un lieu afin d'atteindre un but donné tout en respectant les délais et les contraintes du domaine (temps, coût, probabilité, disponibilité, spécialité,...).

Thèse de doctorat : SCIENCES ET TECHNIQUES : Metz : 1999. / 1999METZ023S. 161 ref.

Reproduction de : Thèse de doctorat : Systèmes industriels : Toulouse, INPT : 2005. / Titre provenant de l'écran-titre. Bibliogr. 100 réf.

Thèse de doctorat : Informatique : INPL : 2007. / Texte en anglais et en français. Titre provenant de l'écran-titre. Bibliogr.

Thèse de doctorat : Automatique, Traitement du Signal, Génie Informatique : Nancy 1 : 2007. / Titre provenant de l'écran-titre. Bibliogr.

Reproduction de : Thèse doctorat : Informatique : Avignon : 2003. / Titre provenant de l'écran-titre. Bibliogr. p. 131-139.

Reproduction de : Thèse de doctorat : Automatique : Metz : 2002. / Titre provenant de l'écran-titre. Notes bibliographiques.

Thèse de doctorat : Informatique : Paris 12 : 2007. / Titre provenant de l'écran-titre. Pagination : 141 p. Bibliogr. : 7 f.

Reproduction de : Thèse de doctorat : Informatique : Poitiers : 2008. / Titre provenant de l' écran-titre. Bibliogr. 122 réf.