# Minimisation du délai moyen en présence d'une contrainte de santé de l'équipement : propriétés structurelles

Ernest Foussard, Margaux Nattaf, Marie-Laure Espinouse, Grégory Mounié

## ► To cite this version:

Ernest Foussard, Margaux Nattaf, Marie-Laure Espinouse, Grégory Mounié. Minimisation du délai moyen en présence d'une contrainte de santé de l'équipement : propriétés structurelles. ROADEF 2025 - 26ème édition du congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Feb 2025, Champs-sur-Marne, France. pp.1-2. hal-05023454

HAL Id: hal-05023454

https://hal.science/hal-05023454v1

Submitted on 7 Apr 2025

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Minimisation du délai moyen en présence d'une contrainte de santé de l'équipement : propriétés structurelles

Ernest Foussard¹, Margaux Nattaf¹, Marie-Laure Espinouse¹, Gregory Mounié²

¹ Univ. Grenoble Alpes, CNRS, Grenoble INP, G-SCOP, 38000 Grenoble, France
{ernest.foussard, margaux.nattaf, marie-laure.espinouse}@grenoble-inp.fr

² Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France
gregory.mounie@imag.fr

**Mots-clés** : Ordonnancement, Maintenance, Santé des équipements

Les évolutions techniques et organisationnelles des dernières décennies ont entraîné une augmentation globale des besoins de maintenance des équipements industriels qui peuvent de nos jours représenter entre 15% et 70% des coûts de production selon le type d'industrie [1, 7]. La maintenance est également au cœur de paradigmes économiques modernes mettant en avant durée de vie et la réemployabilité tels que l'économie circulaire. Dans ce contexte, la planification de la maintenance est une problématique centrale de la gestion des systèmes de production. Les innovations sur les capteurs ont permis l'émergence de modèles de dégradations rendant possible des politiques de maintenance prédictive basées sur des indicateurs de l'état de l'équipement [5]. Nous nous intéressons ici à un problème d'ordonnancement conjoint de la production et de la maintenance conditionnée par un indicateur de santé de l'équipement.

**Ordonnancement et santé de l'équipement** Nous considérons un problème d'ordonnance-ment sur une seule machine, ayant un niveau de santé $h_t$ évoluant entre $h_{max}$ (santé maximale, état quasi-neuf) et 0 (état détérioré). En plus des contraintes classiques, lors de l'exécution d'une tâche $i \in \mathcal{N}$ de durée $p_i$, la santé de la machine doit être supérieure au niveau de santé minimal requis pour la tâche $t_i$ (seuil). La tâche cause alors une diminution $w_i$ (usure) de la santé. Des tâches de maintenance parfaite de durée $p_m$ permettent de réinitialiser la santé.

Les problèmes d'existence d'une solution sous contrainte du nombre de maintenances et de minimisation du délai maximum $C_{max}$ sont une variante du Bin-Packing classique [3, 4]. Nous nous intéressons dans la suite à la minimisation du délai moyen $\sum C_i$.

**Minimisation du délai moyen** La minimisation du délai moyen $\sum C_i$ est un objectif très étudié en ordonnancement. Sur une seule machine avec la seule contrainte de non-chevauchement, la règle SPT permet de minimiser cet objectif. En ajoutant les contraintes sur la santé de l'équipement, une solution optimale doit être un bon compromis entre la règle SPT et un partitionnement efficace des tâches permettant de limiter l'impact de la maintenance sur l'objectif. Le problème devient alors NP-difficile au sens fort [4].

On peut décomposer le problème en trois étapes interdépen-dantes : partitionnement des tâches en paquets, ordonnance-ment des tâches au sein de chaque paquet et ordonnancement des paquets eux-mêmes.

Le problème de partitionnement est différent de celui de minimisation du délai maximum. En effet, il peut être parfois intéressant d'effectuer des maintenances supplémentaires afin d'éviter de placer des tâches longues au début du planning. Par exemple l'instance telle que $h_{max} = 100, p_m = 1$ et dont

les données des tâches sont résumées dans TAB. 1 admet une solution réalisable n'utilisant

<table><caption>TAB. 1 – Données de l'instance pour FIG. 1 and FIG. 2</caption><thead><tr><th>Tâche i</th><th>1</th><th>2</th><th>3</th><th>4</th></tr></thead><tbody><tr><td>Durée p<sub>i</sub></td><td>1</td><td>1</td><td>4</td><td>4</td></tr><tr><td>Usure w<sub>i</sub></td><td>80</td><td>70</td><td>20</td><td>20</td></tr><tr><td>Seuil t<sub>i</sub></td><td>90</td><td>80</td><td>20</td><td>25</td></tr></tbody></table>
<figure><img src="image_2.png" /><figcaption>FIG. 1 – Solution avec $\sum C_i = 24$</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>FIG. 2 – Solution optimale avec $\sum C_i = 23$</figcaption></figure>

qu'une seule maintenance, représentée sur FIG. 1, mais ses solutions optimales utilisent deux maintenances, comme représenté sur FIG. 2. Toutefois, nous démontrons que trier les tâches selon SPT et intercaler les maintenances le plus tard possible permet d'obtenir une borne supérieure du nombre de maintenances dans les solutions optimales. Concernant l'ordonnancement des tâches au sein de chaque paquet, nous montrons qu'en l'absence de la contrainte de seuil, la règle SPT est optimale. De même, si les durées sont proportionnelles aux usures, nous montrons qu'une adaptation de la règle de Smith pour $1|d_i| \sum C_i$ [6] donne l'optimum en temps polynomial. Toutefois, dans le cas général, la question de l'existence d'un algorithme polynomial est encore ouverte à ce jour. Enfin, pour l'ordonnancement des paquets, nous proposons une règle de dominance faisant intervenir la durée totale des paquets, leur nombre de tâches et la durée de maintenance. La difficulté du problème semble donc résider principalement dans l'affectation des tâches aux paquets. La présentation orale au congrès se focalisera sur nos différents résultats théoriques connus et propriétés remarquables pour ce problème.

**Verrous scientifiques et perspectives de recherche** Le découplage total du temps et de l'usure ajoute un degré de liberté supplémentaire dans les instances par rapport aux problèmes classiques de la littérature : les techniques de preuves, algorithmes et résultats doivent prendre en compte les deux dimensions du problème ce qui pose un véritable défi. Les modèles classiques de PLNE ne permettent pas la résolution de grandes instances et nous ne disposons pas à ce jour de garantie de performance sur des heuristiques. L'une des principales perspectives de ces travaux est la mise au point de méthodes de résolution s'appuyant sur les différentes propriétés structurelles du problème. Une seconde présentation à la conférence [2] se concentrera sur les méthodes de résolution mises en place pour ce problème : PLNE, programmation par contraintes et heuristiques hybrides ordonnancement/bin packing.

Références

[1] Umar M. Al Turki, Tahir Ayar, Bekir S. Yilbas et Ahmet Z. Sahin. Integrated maintenance planning. Springer International Publishing, 2014.

[2] Camille Bonnin, Ernest Foussard, Margaux Nattaf, Arnaud Malapert et Marie-Laure Espinouse. Minimisation du délai moyen en présence d'une contrainte de santé de l'équipement : méthodes de résolution ROADEF, 2025.

[3] Ernest Foussard. Planification et ordonnancement de la maintenance conditionnée par la santé de l'équipement. Thèse de doctorat, Université Grenoble Alpes, 2023.

[4] Ernest Foussard, Gérémi Bridonneau, Marie-Laure Espinouse, Margaux Nattaf et Grégory Mounié. Génération de colonnes pour le Bin-Packing avec seuils. ROADEF, 2023.

[5] Hamideh Rostami, Jakey Blue, Argon Chen et Claude Yugma. Equipment deterioration modeling and cause diagnosis in semiconductor manufacturing. Journal of Intelligent Systems 36(6):2618-2638, 2021.

[6] Wayne E. Smith. Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3(1-2):59-66, 1956.

[7] Enrico Zio et Michele Compare. Evaluating maintenance policies by quantitative modeling and analysis. Reliability Engineering & System Safety, 109(4598):53-65, 2013.