# Maximisation du rayon de stabilité pour l'affectation d'opérations de durée incertaine sur une ligne d'assemblage

André Rossi, Evgeny Gurevsky, Olga Battaïa, Alexandre Dolgui

► To cite this version:

André Rossi, Evgeny Gurevsky, Olga Battaïa, Alexandre Dolgui. Maximisation du rayon de stabilité pour l'affectation d'opérations de durée incertaine sur une ligne d'assemblage. 14e Congrès Annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2013), Feb 2013, Troyes, France. hal-01721568

HAL Id: hal-01721568

https://hal.science/hal-01721568

Submitted on 14 Feb 2023

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.

Public Domain
# Maximisation du rayon de stabilité pour l'affectation d'opérations de durée incertaine sur une ligne d'assemblage

André Rossi¹, Evgeny Gurevsky², Olga Battaïa³, Alexandre Dolgui³

¹ Lab-STICC (UMR CNRS 6285), Université de Bretagne-Sud
BP 92116, 56321 Lorient Cedex, France
andre.rossi@univ-ubs.fr

² LINA (UMR CNRS 6241), Université de Nantes
BP 92208, 44322 Nantes Cedex 3, France
evgeny.gurevsky@univ-nantes.fr

³ LIMOS (UMR CNRS 6158), École des Mines de Saint-Étienne
158, cours Fauriel, 42023 Saint-Étienne Cedex 2, France
{battaia,dolgui}@emse.fr

**Mots-clés** : Lignes d'assemblage, Robustesse, Rayon de stabilité.

## 1 Introduction

Ce travail s'intéresse à l'affectation des opérations dans le cadre de l'équilibrage d'une ligne d'assemblage (Simple Assembly Line Balancing Problem, SALBP [1]), sous l'hypothèse que le temps de cycle de la ligne et le nombre de stations sont des constantes connues, et que la durée de certaines opérations est incertaine. Trois versions du problème sont présentées, qui correspondent à trois modèles d'incertitude des durées opératoires. Le premier modèle suppose que l'ensemble des opérations incertaines est connu (il s'agit des opérations dont la durée est susceptible de varier), il est abordé dans [2]. Le second modèle suppose que l'ensemble des stations incertaines est connu (c'est-à-dire que la durée de toutes les opérations qui lui sont affectées est susceptible de varier). Enfin le troisième modèle est une généralisation des deux premiers. On suppose connu l'ensemble des opérations dont la durée est incertaine (quelle que soit leur affectation) ainsi que l'ensemble des stations incertaines (quelles que soient les opérations qui leur sont affectées). L'objectif poursuivi dans ces trois versions consiste à déterminer une affectation des opérations aux stations satisfaisant les contraintes de précédence et de temps de cycle, tout en conférant à cette solution la plus grande robustesse possible. Plus précisément, on mesure la robustesse d'une solution par son aptitude à rester admissible en dépit de l'augmentation de la durée des opérations incertaines. A cet effet, on propose un programme linéaire en variables mixtes visant à maximiser le rayon de stabilité [3], dans le cas où la définition de ce dernier repose sur la distance de Manhattan.

## 2 Maximization du rayon de stabilité

Soit le graphe orienté acyclique $G(V, A)$ où $V$ est l'ensemble des opérations et $A$ est l'ensemble des arcs représentant les contraintes de précédence. $M$ est l'ensemble des stations de travail, et le temps de cycle $T_0$ est commun à toutes les stations. On note $\tilde{V} \subseteq V$ l'ensemble des opérations de durée incertaine, $p_j$ la durée nominale de l'opération $j$ et $\tilde{M} \subseteq M$ l'ensemble des stations incertaines. Le rayon de stabilité basé sur la distance de Manhattan mesure la plus petite augmentation de la durée des opérations incertaines propre à compromettre l'admissibilité de la solution (sans restriction sur la répartition de cette augmentation parmi les opérations). La troisième version du problème est formulée par le programme linéaire en variables mixtes ci-après.
$$ \text{Maximiser } \rho_1 \sum_{k \in M} x_{j,k} = 1 \quad \forall j \in V \quad (1) $$

$$ \sum_{j \in V} p_j x_{j,k} \le T_0 \quad \forall k \in M \quad (2) $$

$$ \sum_{k \in M} k x_{i,k} \le \sum_{k \in M} k x_{j,k} \quad \forall (i, j) \in A \quad (3) $$

$$ x_{j,k} \le a_k \quad \forall j \in \tilde{V}, \forall k \in M \setminus \tilde{M} \quad (4) $$

$$ a_k = 1 \quad \forall k \in \tilde{M} \quad (5) $$

$$ \rho_1 \le T_0(2 - a_k) - \sum_{j \in V} p_j x_{j,k} \quad \forall k \in M \quad (6) $$

$$ a_k \ge 0 \quad \forall k \in M \quad (7) $$

$$ \rho_1 \ge 0 \quad (8) $$

$$ x_{j,k} \in \{0, 1\} \quad \forall j \in V, \forall k \in M \quad (9) $$

Les variables de décision sont $ρ_1$, le rayon de stabilité exprimé avec la distance de Manhattan, $x_{j,k}$ qui est égale à 1 si l'opération $j$ est affectée à la station $k$ et 0 sinon, et enfin $a_k$, une variable continue non négative qui est supérieure ou égale à 1 si la station $k$ traite au moins une opération incertaine, ou si cette station fait partie de $\tilde{M}$. La réciproque est fausse, car rien n'interdit d'avoir $a_k \ge 1$ pour une station hors de $\tilde{M}$ ne traitant aucune opération incertaine.

Les contraintes (1) assurent que toute opération est affectée à exactement une station, (2) que la charge de toute station est inférieure ou égale à $T_0$, et (3) traduisent le respect des contraintes de précédence. Les contraintes (4) assurent que si la station $k$ traite au moins une opération incertaine alors $a_k$ est supérieure ou égale à 1 (la réciproque n'est pas toujours vraie). Les contraintes (5) indiquent que la durée de toute opération est considérée comme incertaine, même si elle n'appartient pas à $\tilde{V}$, dès lors qu'elle est affectée à une station de $\tilde{M}$. Enfin, (6) assurent que si $a_k \ge 1$, alors la marge de la station $k$ est une borne supérieure de $ρ_1$.

Fixer $\tilde{V} \neq \emptyset$ et $\tilde{M} = \emptyset$ conduit à la première version du problème : toute station $k \in M$ peut traiter une opération incertaine, ce qui conduit à $a_k \ge 1$ d'après les contraintes (4).

Fixer $\tilde{V} = \emptyset$ et $\tilde{M} \neq \emptyset$ conduit à la seconde version du problème : la durée d'une opération n'est considérée comme incertaine que si elle est affectée à une station de $\tilde{M}$ d'après (5)-(6).

## 3 Conclusion

Ce travail définit plusieurs versions d'un problème de recherche de solutions robustes pour un problème bien connu (SALBP), et propose un modèle général pour sa modélisation comme pour sa résolution exacte. Une seule des versions a fait l'objet d'une étude approfondie [2].

L'exposé illustrera les trois versions du problème, le modèle proposé sera discuté et on proposera une extension au rayon de stabilité basé sur la distance de Chebychev.

## Références

[1] I. Baybars, A survey of exact algorithms for the simple assembly line balancing problem. Management Science, 32(8):909-932, 1986.

[2] E. Gurevsky, O. Battaïa, and A. Dolgui, Balancing of simple assembly lines under variations of task processing times Annals of Operations Research, 201(1): 265-286, 2012.

[3] Y.N. Sotskov, V.S. Tanaev, and F. Werner, Stability radius of an optimal schedule : a survey and recent developments. In G. Yu, editor, Industrial Applications of Combinatorial Optimization, 16:72-108 in Applied Optimization. Kluwer Academic Publishers, 1998.