Ordonnancement sur machines parallèles identiques avec temps de préparation par famille : application à la gestion des tâches de maintenance préventive

Dans cet article, nous etudions le probleme d'ordonnancement des tâches sur des ressources polyvalentes a performance identique. L'objectif est de minimiser la somme ponderee des encours. Nous etudions particulierement le probleme de gestion de tâches de maintenance preventive d'un systeme reparti sur plusieurs sites. Dans chaque site, un ensemble d'equipements est a maintenir selon une politique de maintenance preventive predefinie. Nous supposons qu'un temps de preparation est necessaire lorsqu'une ressource passe d'un site a un autre et que ce temps est independant de la sequence. Dans un premier temps nous nous interessons a l'etude de ce probleme d'un point de vue statique, c'est-a-dire l'ensemble des tâches du systeme est suppose connu a l'avance et ne change pas au cours du temps. Nous proposons trois heuristiques H1, H2 et H3. Les deux premieres sont basees sur des algorithmes de liste avec des ameliorations. Quant a la troisieme, il s'agit d'une heuristique constructive. L'evaluation de ces heuristiques par rapport a une borne inferieure montre que l'heuristique H3 domine les deux autres. La deuxieme partie de ce travail est consacree a l'adaptation de l'heuristique H3 au probleme d'ordonnancement en ligne de tâches de maintenance preventive.