Ordonnancement : modèles, algorithmes et applications

点击翻译按钮获取中文摘要

La théorie de l'ordonnancement s'intéresse aux problèmes d'allocation de ressources dans le temps pour réaliser un ensemble donné de tâches. Le nombre de ressources étant limité, la décision d'affecter une tâche à une ressource, à un instant donné, est cruciale pour atteindre le ou les objectifs fixés au départ. Il est intéressant de constater que les ressources et les tâches peuvent avoir plusieurs interprétations dépendamment du contexte. Ainsi, le terme ressource peut signifier processeurs, machines, énergie, radar, personnel, matériel, etc. L'interprétation des tâches peut aller quant à elle des produits manufacturiers jusqu'aux processus informatiques ou physiques, en passant par des quarts de travail ou commandes à livrer. Le programme de recherche proposé porte sur l'investigation des effets induits par la prise en compte de certains paramètres pratiques, négligés ou non suffisamment pris en considération jusque-là dans la littérature, sur les modèles classiques d'ordonnancement que sont le flow shop, flow shop de permutation, open shop et job shop, machine unique et machines parallèles. Le premier paramètre considéré est celui des temps de latence pour exprimer les temps induits par les déplacements des tâches à travers les ressources. Le second paramètre est lié à l'existence d'interdépendances entre les tâches pour exprimer leurs précédences (relations orientées) ou incompatibilités (relations non orientées). Le troisième paramètre concerne quant à lui la présence d'opérateurs pour faire fonctionner les ressources. Le point commun des différentes problématiques d'ordonnancement est d'arriver à mieux organiser le travail de réalisation des tâches dans le but d'utiliser efficacement les ressources existantes et diminuer autant que possible, entre autres, les pertes de temps et/ou les délais de livraison. En règle générale, les problèmes d'ordonnancement sont réputés pour être difficiles à résoudre d'un point de vue de la complexité de calculs ; seule une poignée d'entre eux possède en effet des solutions algorithmiques efficaces. En conséquence, plusieurs de ces modèles seront étudiés sur plusieurs fronts : détermination du degré de difficulté de leur résolution, recherche de cas particuliers pertinents résolubles en temps polynomiaux, utilisation de méthodes exactes et/ou de méthodes heuristiques. Graviteront ensuite autour de cette thématique, des applications connexes liées aux ordres linéaires, flots multicrières en nombres entiers et reconnaissance de graphes, et enfin la répartition d'appels téléphoniques dans un contexte d'une plateforme collaborative pour des appareils mobiles en vue de garder le reseau utilisé le plus pérenne possible.