Ordonancement d'ateliers : algorithmes et complexité

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

La théorie de l’ordonnancement s’intéresse aux problèmes d’allocation de ressources dans le temps pour réaliser un ensemble 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 et /ou satisfaire les contraintes liés au problème étudié. Il est utile de mentionner que les ressources et les tâches peuvent avoir plusieurs interprétations dépendamment du contexte. Ainsi, le terme ressource peut signifier argent, processeurs, machines, énergie, matériel, etc. L’interprétation des tâches, quant à elle, peut aller des produits manufacturiers jusqu’aux processus dans les systèmes informatiques, en passant par des quarts de travail. Dans ces conditions, il est facile de constater que les problèmes d’ordonnancement sont associés ou surviennent dans la plupart des problèmes réels. Bien entendu, chaque application peut posséder ses propres spécificités dont il faut tenir compte lors de la résolution. Le programme de recherche proposé ici s’intéresse aux effets induits par la prise en compte de certaines paramètres pratiques, négligés ou non suffisamment pris en considération jusque-là dans la littérature, sur les modèles de base d’ordonnancement d’atelier, afin de les rendre plus proches de la réalité. 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 celui lié à l’existence de relations de précédence entre les tâches (dans certains cas, une tâche ne peut commencer son exécution qu’à la fin d’autres tâches ; ces dépendances définissent un graphe de précédence). Le troisième paramètre concerne la présence d'opérateurs qui, dans certaines situations, sont nécessaires au fonctionnement des ressources pour réaliser une solution d’ordonnancement. Et, enfin, le quatrième paramètre considéré concerne l’utilité de dupliquer des machines dans le but d’alléger les éventuels goulots d’étranglements dus à certaines ressources. Le point commun des différents problèmes d’ordonnancement est d'arriver à mieux organiser le travail afin d’utiliser efficacement les ressources existantes (souvent chères et rares) et de diminuer les pertes de temps et/ou les délais de livraison autant que possible. En règle générale, les problèmes d’ordonnancement sont réputés être difficiles à résoudre d’un point de vue de la complexité de calculs ; seule une poignée d’entre eux possède des solutions algorithmiques efficaces. En conséquence, je compte investiguer plusieurs de ces modèles (flow shop, permutation flow shop, open shop, mixed shop, une seule machine et machines parallèles) sur plusieurs fronts : détermination du degré de difficulté de leur résolution, recherche de cas particuliers pertinents, utilisation de méthodes exactes et de méthodes heuristiques (l’évaluation des algorithmes heuristiques constructifs se fera par rapport à l’analyse dans le pire des cas, tandis que celle des solutions méta-heuristiques se fera d’une manière expérimentale).