Impact de la contrainte d'incompatibilité sur la complexité et l'approximation des problèmes d'ordonnancement en présence de tâches-couplées
Institution:
Montpellier 2Disciplines:
Directors:
Abstract EN:
The last couple of years have seen the advent of sub-marine machines like the sub-marine torpedo. This torpedo must execute two kind of tasks : acquisition tasks and treatment tasks. The acquisition tasks are equivalent to coupled-tasks, and treatment tasks are equivalent to classical tasks with preemption constraints. The torpedo possess different captors in order to realize the acquisitions, few captors cannot be use in same time because of the interferences. In this way, we introduce a compatibility graph in order to represent the acquisition tasks which can be executed in the same time. The torpedo possess a mono-processor used to execute the different tasks. In the first part, we introduce the model of the problem, and define the different tasks and their constraints. We discuss on the impact of the compatibility constraint on the general problem. Finally, we finish this part with a related works on general scheduling theory, on coupled-tasks, and on the different cover problems in the graph theory. In a second part, we give the classification of the different problems according to the parameters of the coupled-tasks. We give several proves of complexity for specific problem which are at the limit between polynomiality and completeness. For each studied problem, we propose either a optimal solution with an algorithm in polynomial time, or an approximation algorithm with guarantee of performance. For few problems, we study the complexity in details according to specific parameters or different topologies for the compatibility graph. All the long of this part, we try to show the impact of the introduction of the compatibility constraint on the scheduling problem with coupled-tasks
Abstract FR:
Depuis quelques années les véhicules sous-marins autonomes sont en plein essor, les torpilles sous-marines d'exploration en sont le parfait exemple. Cette torpille a pour objectif d'exécuter deux types de tâches : celles d'acquisition et celles de traitement. Les tâches d'acquisition sont semblables à des tâches-couplées, et les tâches de traitement sont des tâches classiques. La torpille utilise différents capteurs pour réaliser les acquisitions, certains capteurs ne peuvent pas être utilisés en même temps pour cause d'interférences. Nous introduisons donc un graphe de compatibilité permettant de représenter les tâches d'acquisition pouvant avoir leurs exécutions qui se chevauchent. La torpille possède un monoprocesseur embarqué permettant d'exécuter toutes la tâches. La première partie de nos travaux s'intéresse à la modélisation du problème, de la définition des différentes tâches utilisées et les contraintes qui leur sont appliquées. Nous mettons en avant la contrainte de compatibilité qui nous contraint à utiliser la théorie des graphes pour analyser nos problèmes. Enfin, nous finissons cette partie avec un état de l'art sur les différents résultats portant sur l'ordonnancement de tâches-couplées sur mono-processeur, et sur des problèmes de recouvrement de sommets dans des graphes. Dans une seconde partie, nous donnons la classification des problèmes possibles en faisant varier les paramètres des tâches-couplées. Nous donnons des preuves de complexité pour certains problèmes se trouvant à la limite entre la polynomialité et la NP-complétude selon les contraintes sur les paramètres. Pour chacun de ces problèmes, qui sont NP-complets, nous proposons des algorithmes d'approximation en temps polynomial et analysons les bornes obtenues selon les paramètres ou les topologies du graphe de compatibilité. L'ensemble des résultats est décomposé en trois chapitres prenant chacun en compte l'introduction d'une contrainte (d'incompatibilité et/ou de précédence). Tout au long de cette partie nous cherchons à montrer l'impact de l'introduction de la contrainte d'incompatibilité sur la complexité des problèmes d'ordonnancement avec tâches-couplées, à travers les preuves de NP-complétude et les techniques employées pour résoudre ou approximer un problème