Affectation équilibrée de tâches périodiques

On considère des tâches devant être exécutées chaque semaine à des horaires précis, ainsi qu’un certain nombre de travailleurs indiscernables chargés de les accomplir. Nous abordons le problème de l’affectation de ces tâches périodiques de manière équilibrée, c’est-à-dire de façon à ce que chaque travailleur réalise chaque tâche avec la même fréquence sur le long terme. Deux versions de ce problème sont considérées : la version de base, où la seule contrainte est qu’un travailleur ne peut pas effectuer deux tâches simultanément, et la version étendue, où l’on peut introduire des contraintes supplémentaires restreignant les plannings hebdomadaires valides.

Nous montrons que, pour les deux versions du problème étudié, lorsqu’il existe une affectation équilibrée, une telle affectation peut toujours être rendue périodique. En outre, pour la version de base, nous établissons une condition nécessaire et suffisante à l’existence d’une affectation équilibrée, condition qui peut être vérifiée en temps polynomial. Pour la version étendue, une condition suffisante d’existence est également donnée. Pour obtenir certains de ces résultats, nous introduisons un problème de déplacement de jetons sur un graphe orienté dont les arcs sont colorés, où les jetons doivent visiter chaque arc avec la même fréquence sur le long terme. Ce problème de jetons et les résultats obtenus à son sujet sont susceptibles d’être intéressants en eux-mêmes.

Travail commun avec Héloïse Gachet.