# Minimisation du délai moyen en présence d'une contrainte de santé de l'équipement : méthodes de résolution

Camille Bonnin, Ernest Foussard, Margaux Nattaf, Arnaud Malapert, Marie-Laure Espinouse

► To cite this version:

Camille Bonnin, Ernest Foussard, Margaux Nattaf, Arnaud Malapert, Marie-Laure Espinouse. Minimisation du délai moyen en présence d'une contrainte de santé de l'équipement : méthodes de résolution. 26ème congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF'25), Ecole nationale des ponts et chaussées, Feb 2025, Champs Sur Marne, France. hal-05024111

HAL Id: hal-05024111

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

Submitted on 7 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished 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 : méthodes de résolution

Camille Bonnin¹, Ernest Foussard¹, Margaux Nattaf¹, Arnaud Malapert²,
Marie-Laure Espinouse¹

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

² Université Côte d'Azur, CNRS, I3S, France
arnaud.malapert@univ-cotedazur.fr

**Mots-clés** : Ordonnancement à une machine, Délai moyen, Indice de santé, Maintenance.

**Contexte** Les progrès technologiques, en particulier au niveau des capteurs permettent de mesurer et de représenter l'impact de la santé d'une machine sur la qualité des tâches effectuées. Cela a amené à l'apparition de modèles de dégradation pour la machine [3] qui permettent ainsi d'ordonnancer les tâches en tenant compte de l'état de cette dernière. Le modèle utilisé dans cette étude est celui de l'indice de santé de la machine qui a été introduit récemment afin de développer des politiques de maintenance préventive [2].

**Présentation du problème** Le problème étudié dans cette étude est le problème d'ordonnancement à une machine possédant un indice de santé ($h_t$) dépendant du temps ($t$) et pouvant prendre des valeurs entières allant de 0 à 100, 100 représentant une machine neuve.

L'objectif est d'ordonnancer toutes les $n$ tâches en minimisant le délai moyen (ie. la somme des dates de fin $C_j$ des tâches). Chaque tâche $j$ du problème possède trois caractéristiques. La première est sa durée ($p_j$) qui indique le temps nécessaire à son exécution. La seconde est son usure ($w_j$) qui indique le nombre d'unités de santé perdues par la machine à la fin de l'exécution la tâche. Enfin, la dernière caractéristique est son seuil ($t_j$) qui indique le niveau de santé minimum requis sur la machine au début de la tâche afin de pouvoir l'exécuter.

Afin de restaurer la santé de la machine, il est possible d'effectuer des maintenances. Toutes les maintenances utilisées ici sont *parfaites* (ie. elles restaurent complètement la santé de la machine) et de même durée $m$. Il n'y a pas de limite au nombre de maintenances. Les groupes de tâches séparés par des maintenances sont appelés des *batchs*. Ce problème peut être vu comme une combinaison de *bin-packing* (création des *batchs*) et d'ordonnancement. Il s'agit d'un problème *NP*-dur au sens fort [1]. Un exemple de solution (non optimale) du problème de faisabilité associé est donné en Figure 1.

**Méthodes de résolution** Ce problème peut être modélisé afin d'appliquer des méthodes de résolution exactes comme la Programmation Par Contraintes et la Programmation Linéaire. Ces méthodes ne sont pas décrites ici, mais des résultats de ces dernières seront abordés dans la présentation. Les modèles de base indexés par le temps étant long à résoudre pour les deux méthodes, quatre heuristiques permettant d'obtenir une solution réalisable, mais pas forcement optimales sont présentées ici. Ces dernières sont décrites ci-dessous :

*Heuristique SPT* : les tâches sont exécutées dans l'ordre croissant de leurs durées ($p_j$) (règle SPT ou règle de Smith [4]) tout en insérant une maintenance si et seulement si le niveau de santé de la machine ne permet pas d'exécuter la prochaine tâche de la liste. L'idée est

<footnote>*Institute of Engineering Univ. Grenoble Alpes</footnote>
d'ordonnancer les tâches de manière optimale pour le problème sans maintenance puis d'ajouter les maintenances afin d'obtenir une solution au problème étudié ici.

*Heuristique SPT First Fit*: une combinaison de la règle SPT et de l'heuristique de *bin paclking first fit*. Les tâches sont rangées dans l'ordre SPT et insérées les unes à la suite des autres dans le premier *batch* où elles peuvent être exécutées ($h_t \ge t_j$). Les *batchs* sont ensuite exécutés dans l'ordre croissant de leur création. L'ajout de *first fit* permet de diminuer le nombre de *batchs* et donc de maintenances par rapport à l'heuristique SPT.

*Heuristique $t_j - w_j$ First Fit*: le principe est identique à celui de l'heuristique SPT First Fit à la différence qu'au début les tâches sont ordonnées par ordre décroissant de la différence entre leur seuil et leur usure ($t_j - w_j$) et non suivant l'ordre SPT. L'idée est de répartir les tâches dans des *batchs* tout en veillant à respecter l'ordre $t_j - w_j$ décroissants, à l'intérieur de ces-derniers. En effet, cette propriété est respectée à l'intérieur des *batchs* par une solution optimale du problème pour le critère de minimisation du délai total ($C_{max}$) [1] et permet de maximiser le nombre de tâches par paquet.

*Heuristique $(t_j - w_j)/p_j$ First Fit*: le principe est le même que celui de l'heuristique SPT First Fit hormis qu'au début les tâches sont ordonnées par ordre croissant du quotient de la différence entre leur seuil et leur usure par leur durée ($(t_j - w_j)/p_j$) et non suivant l'ordre SPT. L'idée est d'adapter la règle SPT pondérée à notre problème.

*Exemple*: Voici un exemple de solution donnée par l'heuristique SPT First Fit avec $m = 10$.

<table><caption>TAB. 1 – Exemple d'instance à six tâches avec $m = 10$.</caption><thead><tr><th>j</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th></tr></thead><tbody><tr><th>p<sub>j</sub></th><td>5</td><td>7</td><td>3</td><td>1</td><td>8</td><td>2</td><td>4</td></tr><tr><th>w<sub>j</sub></th><td>10</td><td>10</td><td>5</td><td>15</td><td>20</td><td>10</td><td>5</td></tr><tr><th>t<sub>j</sub></th><td>90</td><td>90</td><td>80</td><td>50</td><td>80</td><td>65</td><td>40</td></tr></tbody></table>

<figure><img src="image_2.png" /><figcaption>FIG. 1 – Solution de l'heuristique SPT First Fit pour cette instance un délai moyen de 139.</figcaption></figure>

**Conclusion et perspectives** Dans ce travail nous avons proposé des méthodes exactes ainsi que quatre heuristiques afin de trouver une solution au problème de planification de maintenances à une machine avec seuils et indice de santé avec pour objectif de minimiser le délai moyen. Les performances de ces méthodes seront comparées et analysées lors de la présentation. Une perspective est d'améliorer ces heuristiques en identifiant des critères respectés par une solution optimale. Une autre est d'utiliser ces heuristiques afin de trouver des bornes sur l'objectif et le nombre de maintenances dans le but d'améliorer les modèles PPC et PLNE.

Références

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

[2] L. Penz, S. Dauzère-Pérès, et M. Nattaf. Minimizing the sum of completion times on a single machine with health index and flexible maintenance operations. *Computers & Operations Research*, 151:106092, 2023

[3] H. Rostami, J. Blue, A. Chen, et C. Yugma. Equipment deterioration modeling and cause diagnosis in semiconductor manufacturing. *International Journal of Intelligent Systems*, 36(6):2618-2638, 2021.

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