Title: Ordonnancement de tâches en présence d’opérateurs dans un environnement de job shop

Speaker: REBAINE, Djamal (Université du Québec à Chicoutimi)

Abstract:

Dans les applications pratiques d’ordonnancement, il est souvent nécessaire, pour différentes raisons, d’avoir recours à des opérateurs pour procéder à l’exécution d’un ensemble de tâches sur un ensemble machines. À l’aide de deux applications, et donc sous deux angles différents, nous allons voir comment aborder la résolution de ces problèmes en présence d’opérateurs.

La première application est celle où les opérateurs jouent le rôle de superviseurs, selon un certain nombre de modes opératoires, dans un environnement de machines parallèles identiques. Ces modes opératoires indiquent les différentes manières dont va s’occuper un opérateur des machines. La difficulté vient du fait que les temps d’exécution des tâches vont être ainsi dépendants des différentes portions de temps mises à la disposition des opérateurs pour chaque machine. Un algorithme pseudo-polynomial est exhibé pour résoudre le cas de deux machines parallèles en présence d’un seul opérateur.

La deuxième application est celle où un certain nombre d’opérateurs sont nécessaires avant l’exécution de chaque tâche dans un environnement d’open shop à deux machines. En tout temps, ce nombre ne doit pas dépasser le nombre total existant d’opérateurs. Bien entendu, si le nombre d’opérateurs requis par une tâche n’est pas disponible, alors cette tâche ne peut s’exécuter. Des résultats de complexité sont présentés, un cas particulier est résolu en le réduisant à un problème de flot dans les graphes, une borne inférieure, déduite encore une fois de la problématique de flots dans les graphes, est présentée. Elle est ensuite utilisée dans l’évaluation de la performance de quelques heuristiques conçues pour la résolution de ce problème d’une manière approchée.