Les méthodes d'ordonnancement au service de la performance industrielle

Planification dans l'industrie chimique : un nouveau problème d'ordonnancement avec indisponibilité des opérateurs

Ce sujet de recherche est directement issu d'une problématique industrielle de planification d'expériences rencontrée par l'Institut Français du Pétrole (IFP). La réponse à apporter passait par le développement d'un logiciel d'ordonnancement permettant de déterminer les conditions optimales de synthèse de produits chimiques. Pour chaque produit à tester une première série d'expériences (phase I) est conduite pour déterminer la durée optimale de synthèse. Ensuite, en phase II, différentes conditions opératoires sont testées  avec cette durée pour améliorer la qualité du produit. Le test d'un produit comporte ainsi plusieurs expériences, regroupées en systèmes, qui passent successivement dans les phases I et II. Les expériences à effectuer en phase I sont connues dynamiquement, au fur et à mesure des expérimentations, tandis que toutes les expériences à effectuer en phase II sont connues dès le début de cette phase.

Pour réaliser ces expériences l'Institut Français du Pétrole s'était doté d'un nouveau système automatisé capable de contrôler de manière autonome les conditions expérimentales. Ce robot comporte un ensemble de barres ; dans chacune d'entre elles il est possible d'effectuer simultanément plusieurs expériences, de même durée et de même température. La durée des expériences est comprise entre 1 et 21 jours. Le nombre total d'expériences à réaliser est de plusieurs milliers, ce qui correspond à une année de tests à planifier. Le but recherché par l'IFP est de maximiser le remplissage des barres afin de finir l'ensemble des expériences au plus tôt. Mais il est également primordial de finir régulièrement le test complet d'un produit, les résultats étant attendus pour déterminer de nouveaux mélanges. 

Les actions à effectuer sur une barre, en plus des expérimentations, se décomposent en opérations élémentaires (lavage, remplissage...) ayant des durées fixes. L'une des originalités de ce problème est que certaines de ces opérations requièrent l'intervention d'un opérateur. Si le robot peut travailler en permanence, l'opérateur est, lui, absent typiquement la nuit et les week-ends. La planification doit ainsi tenir compte des contraintes imposées par l'opérateur : on ne doit pas planifier la fin ou le commencement d'une expérimentation sur le robot pendant une période d'absence de l'opérateur.

Problèmes d'ordonnancement sous contraintes de ressources additionnelles

Le problème industriel comporte plusieurs particularités : dynamicité des expériences en phase I, constitution des barres de cuisson et périodes d'indisponibilité de l'opérateur. Nous nous sommes particulièrement intéressés à ce dernier point, qui constitue un nouveau type de problème en ordonnancement lorsque des ressources  additionnelles sont nécessaires à certaines étapes du déroulement des  tâches, typiquement lors du démarrage ou de la terminaison. Ces  ressources additionnelles ne sont pas disponibles en continu ou peuvent coûter plus cher sur certaines périodes. Il s'agit dans le cas de l'IFP d'un  opérateur chargé de lancer le process au démarrage de la tâche et d'analyser le résultat lors de sa terminaison. Il peut s'agir également de traitements spécifiques (thermique, catalyse) très gourmands en énergie avec des coûts de consommation électrique négociés par plages, ou encore de matériel lourd de manutention sous-loué ou sous-traité, avec des contraintes liées au sous-traitant (coût horaire, location de matériel sur des courtes périodes...). L'objectif est alors d'ordonnancer les tâches en tenant compte de cette contrainte d'indisponibilité de la ressource additionnelle pour finir au plus tôt ou pour minimiser les coûts d'utilisation de ces ressources.

Conception  d'un outil d'aide à la planification

Sur le plan théorique, nous avons étudié la difficulté au sens de la théorie de la complexité de ces nouveaux problèmes d'ordonnancement avec indisponibilité de l'opérateur. Nous avons établi des résultats positifs et négatifs d'approximabilité et nous avons également proposé des algorithmes de résolution efficaces (polynomiaux) pour certains cas particuliers. Nous avons notamment étudié le cas d'indisponibilités périodiques, qui correspond aux absences de l'opérateur le week-end. Pour répondre au problème industriel posé par l'IFP, nous avons développé un logiciel d'ordonnancement spécifique en deux phases. Une phase d'initialisation détermine les premières expériences à lancer par la résolution d'un programme linéaire en nombres entiers de taille raisonnable.  Le reste de l'horizon de planification est ensuite confié à un algorithme de liste qui arbitre un compromis entre les deux objectifs de l'industriel : le taux d'utilisation du robot et la terminaison régulière de tests complets d'un produit. Cet arbitrage est basé sur un partage dynamique des ressources : une partie des barres est réservée pour traiter des expériences en phase I, l'autre partie achevant au plus vite une expérience en phase II. Les résultats obtenus se sont avérés répondre aux attentes de l'IFP.

Partenariats : Institut Français du Pétrole (IFP), collaboration internationnale (G.B.) avec C. Potts  et  V. Strusevich

Date : collaboration industrielle étalée sur l'année 2006

Contact : Christophe RAPINE, Laboratoire G-Scop

Publications :

• "Operator non-availability periods", N. Brauner, G. Finke , V. Lehoux-Lebacque, C. Rapine , H. Kellerer, C. Potts, V. Strusevich. 4OR: A Quarterly Journal of Operations Research, 2009
• "Scheduling problems of chemical experiments", N. Brauner, G. Finke, V. Lehoux-Lebacque, C. Rapine. Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), 2007
• "Operator non-availability: the case of small periods",  N. Brauner , G. Finke , V. Lehoux-Lebacque, C. Rapine. Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), 2007
• "Scheduling chemical experiments",  N. Brauner , G. Finke , V. Lehoux-Lebacque, C. Rapine.  International Conference on Computers and Industrial Engineefing (CIE), 2007