Ordonnancement

Applications :

  • ordonnancement d'atelier

  • gestion de projets

  • conception aéronautique 

  • programmation de prises de vue satellite

  • planification des  formations de pilotes

  • ordonnancement d'instructions  sur processeurs  parallèles




Fig 1. Ordonnancement d'atelier

Méthodes :

  • raisonnement temporel

  • propagation de contraintes

  • méthodes arborescentes

  • algorithmes de graphes

  • programmation linéaire (continue, en nombres entiers, généralisée)

 

Fig 2. Ordonnancement de projet


Un premier volet de notre activité de recherche concerne la proposition de nouvelles méthodes d’ordonnancement, soit pour améliorer la résolution de problèmes d'optimisation NP-difficiles connus, soit pour résoudre de nouveaux problèmes issus de cas réels. Les problèmes étudiés sont des problèmes d'ordonnancement de tâches pouvant comporter les contraintes complexes suivantes : ressources cumulatives, temps de préparation, contraintes de précédences généralisées, flexibilité sur les ressources allouées aux tâches, ordonnancement cyclique. Nous nous attachons en particulier à développer de nouvelles formulations de PLNE, des méthodes arborescentes tronquées basées sur le concept de divergence et des techniques de propagation de contraintes. Nous avons à ce titre obtenu des résultats surclassant les meilleurs résultats connus sur des problèmes de flow-shop hybride et sur des problèmes de job-shop avec temps de préparation et proposé des résultats de complexité sur des problèmes d'insertion de tâches.

Un second volet est consacré à la détermination de solution robustes en ordonnancement sous incertitudes. Nous nous intéressons en particulier au calcul d’un ensemble de solutions de performance au pire et de cardinalité connues. La difficulté consiste à construire l'ensemble en évitant l'énumération des solutions, tout en autorisant un calcul polynomial de la performance au pire et de la cardinalité. Pour cela, des conditions de dominance valables dans le cas du problème à une machine et des analyses de pire performance pour les problèmes disjonctifs généraux ont été obtenues. Nous étudions également la mise en place d'approches coopératives et robustes d'ordonnancement. L'ordonnancement global est construit progressivement par des négociations successives entre ressources, chaque ressource gérant son propre ordonnancement local par la technique robuste. L'objectif est alors de trouver un bon compromis entre la flexibilité accordée à chaque ressource et l'optimisation d'un critère global.


 
Fig 3. Conception Aéronautique

Fig 4. Planification de formations de pilotes
Un dernier volet concerne l'étude de cas pratiques, souvent industriels, permettant d’appliquer les méthodes d'ordonnancement générales développées précédemment. Nous avons ainsi proposé une méthode d'ordonnancement des activités pour la production de biens à la commande (Fig. 1) par une approche à deux niveaux. Le niveau supérieur est chargé de positionner temporellement les Ordres de Fabrication de manière à optimiser la politique de gestion à moyen terme tandis que le niveau inférieur ordonnance finement les activités à court terme suivant la « consigne » issue du niveau supérieur. En collaboration avec Airbus France et EADS-CCR, un travail a été réalisé sur l’ordonnancement des activités de conception au cours du développement d’un nouvel avion (Fig. 3). Nous avons ainsi introduit le concept original de contrainte de précédence énergétique qui définit une contrainte de précédence partielle entre deux activités d’ingénierie. Cette énergie pré-requise modélise la maturité que doit acquérir une activité avant de pouvoir en commencer une autre. En collaboration avec ST-Microelectronics, nous avons proposé de nouvelles approches de résolution de problèmes d’ordonnancement sur processeurs de type VLIW. Notons enfin qu’une étude sur la planification des formations « vol » a été réalisée pour le département Formation d’Airbus. Le système étudié est celui de la planification opérationnelle des formations aux pilotes (Fig. 4) et aux agents de maintenance de l’avion.

Contacts : Christian Artigues, Cyril Briand, Patrick Esquirol, Marie-José Huguet, Pierre Lopez, Julien Moncel

Post-doc : Premysl Sucha

Thèses en cours : Touria Ben Rahhou

Quelques publications  (voir la liste complète sur le serveur du LAAS) :