# Équilibrage de ligne d'assemblage aéronautique sous contrainte de ressources avec effet d'apprentissage: une approche de programmation par contraintes

Duc Anh Le, Stéphanie Roussel, Christophe Lecoutre

► To cite this version:

Duc Anh Le, Stéphanie Roussel, Christophe Lecoutre. Équilibrage de ligne d'assemblage aéronautique sous contrainte de ressources avec effet d'apprentissage: une approche de programmation par contraintes. PFIA 2025 - 20es Journées Francophones de Programmation par Contraintes, Association Française de Programmation par Contraintes, Jun 2025, Dijon, France. hal-05265385

HAL Id: hal-05265385

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

Submitted on 17 Sep 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
# Équilibrage de ligne d'assemblage aéronautique sous contrainte de ressources avec effet d'apprentissage : une approche de programmation par contraintes

Duc-Anh Le¹, Stéphanie Roussel¹, Christophe Lecoutre²

¹ DTIS, ONERA, Université de Toulouse, France

² CRIL, Université d'Artois & CNRS, France

duc_anh.le@onera.fr, stephanie roussel@onera.fr, christophe lecoutre@cril.fr

## Résumé

L'équilibrage des lignes d'assemblage en aéronautique est un défi majeur dans le domaine de la production. Les usines aéronautiques sont généralement conçues avec une cadence de production prédéterminée, mais le système de production nécessite un temps d'adaptation au démarrage. Ce phénomène, appelé effet d'apprentissage, correspond à l'amélioration progressive de l'efficacité par la répétition des tâches, réduisant ainsi leur durée. Cependant, la stabilité de la ligne est également un facteur clé, car toute modification du processus de production engendre un coût. Cette étude utilise la programmation par contraintes pour optimiser l'équilibrage des lignes d'assemblage, en intégrant l'effet d'apprentissage afin de gérer le compromis entre l'atteinte d'une cadence de production cible et la minimisation des ajustements apportés à la ligne d'assemblage.

## Mots-clés

Équilibrage de ligne d'assemblage, ressources contraintes, effet d'apprentissage, aéronautique, programmation par contraintes.

## 1 Introduction

Le problème d'équilibrage des lignes d'assemblage (Assembly Line Balancing Problem – ALBP) est un défi majeur d'optimisation en production industrielle. L'objectif est de répartir équitablement les charges de travail entre les postes (les stations de travail) tout en minimisant les temps d'inactivité et en s'assurant que la cadence de production répond à la demande. Il existe différentes catégories et configurations de lignes d'assemblage, et les lignes d'assemblage aéronautiques sont généralement des systèmes droits à modèle unique, comme illustré dabs la figure 1. La cadence de production d'une ligne d'assemblage est représentée par son temps-de-cycle (TdC), c'est-à-dire le temps entre la finalisation de l'assemblage de deux exemplaires consécutifs. Le TdC correspond également au temps imparti à chaque poste de travail pour réaliser s les tâches qui lui sont allouées avant de transmettre l'exemplaire au poste suivant.

Les usines de fabrication d'avion sont conçues pour pro-

duire à une certaine cadence. Cependant, une fois la production lancée, il faut du temps au système pour atteindre cette cadence de production. Les opérateurs doivent acquérir de l'expérience, améliorer leurs compétences, optimiser la gestion de la chaîne d'approvisionnement et affiner le processus de production. Ainsi, la cadence de production initiale des usines est toujours inférieure à la cadence cible, et l'écart entre les deux peut être significatif. À mesure que la production progresse, les améliorations continues dans l'optimisation des flux de travail, l'intégration de l'automatisation et l'accumulation d'expérience permettent de réduire cet écart. Ce phénomène, connu sous le nom d'effet d'apprentissage, désigne l'amélioration progressive de l'efficacité du système de production grâce à la répétition des tâches, ce qui entraîne une réduction de leur durée [25]. La variation de la durée d'exécution d'une tâche en fonction de sa répétition est appelée courbe d'apprentissage [26, 15], et la période durant laquelle cette durée s'améliore continuellement jusqu'à atteindre un état stable est appelée phase d'apprentissage. La période nécessaire au système de production pour atteindre la cadence de production cible est appelée phase de montée en cadence.

Comme le temps nécessaire pour effectuer une tâche dans un environnement de fabrication diminue au fil du temps en raison de l'effet d'apprentissage, la conception de la ligne d'assemblage et du processus d'assemblage est continuellement affinée. Cependant, la stabilité de la ligne est également un facteur critique, car toute modification du processus de production entraîne des coûts. Plusieurs causes potentielles expliquent ce problème : le temps nécessaire

<figure><img src="image_2.png" /><figcaption>FIGURE 1 – Ligne d'assemblage droite à modèle unique, trois postes de travail. $i - 1$, $i$ et $i + 1$ sont des exemplaires d'avion successifs</figcaption></figure>
pour installer ou désinstaller les machines lourdes entre les postes de travail, les erreurs commises par les techniciens(ne)s lorsque le processus d'assemblage change et devient moins familier, ou encore les modifications dans la gestion des stocks et de la chaîne d'approvisionnement, etc. Cela crée un dilemme pour les fabricants : optimiser continuellement la ligne versus minimiser le coût des ajustements apportés au processus de production.

L'objectif de ce travail est d'étudier l'utilisation de la Programmation par Contraintes (Constraint Programming – CP) pour traiter l'ALBP sous contraintes de ressources en tenant compte de l'effet d'apprentissage. Nous désignons ce problème par RC-ALBP/L. La décision implique un compromis entre le temps de montée en cadence – le temps nécessaire pour atteindre le taux de production cible ou le TdC – et le nombre d'ajustements apportés à la ligne – le nombre de fois où on change le TdC. Cette décision consiste en l'allocation des tâches et des ressources à chaque poste de travail, ainsi que le TdC pour chaque période de production.

Cet article présente un travail préliminaire, dans lequel nous définissons formellement RC-ALBP/L. L'encodage en CP ainsi que les expériences associées sont encore en cours de développement, et sa présentation formelle dépasse le cadre de cet article. La structure de l'article est la suivante. Après la présentation de quelques travaux connexes dans la Section 2, RC-ALBP/L est introduit formellement dans la Section 3, avec un exemple illustratif du problème. Enfin, nous concluons et discutons des perspectives pour les travaux futurs dans la Section 4.

## 2 Etat de l'art

L'ALBP est bien connu dans la littérature. À partir de la version simple de l'ALBP (SALBP) [16], de nombreuses extensions ont été proposées au fil des années [6, 7, 8]. Nous nous concentrons spécifiquement sur l'ALBP sous contraintes de ressources (RC-ALBP) et sur l'ALBP tenant compte de l'effet d'apprentissage.

**L'ALBP sous contraintes de ressources.** Ce problème a été désigné par plusieurs noms dans le passé [9, 24], mais il n'a été formellement défini qu'en 2005 dans [2]. La définition du RC-ALBP a été davantage précisée dans [12], où les auteurs ont souligné que les ressources requises par les tâches peuvent être simples ou multiples, alternatives et/ou concurrentes. La complexité du RC-ALBP a été démontrée comme étant fortement NP-difficile dans [20], même sans prendre en compte les aspects de planification. Lorsque des ressources cumulatives sont considérées, il faut non seulement allouer les tâches aux stations mais aussi décider de leur date de début. Cette variante particulière du RC-ALBP a été largement étudiée sous le nom de "Multi-Manned ALBP", introduit pour la première fois dans [13]. Plusieurs approches de résolution ont été développées pour traiter le RC-ALBP, avec ou sans prise en compte de la planification, incluant des techniques basées sur la CP [3, 10, 14, 21, 22, 23, 27].

**L'ALBP avec l'effet d'apprentissage.** Bien que l'ALBP ait été largement étudié avec de nombreuses extensions, peu

de travaux ont pris en compte l'effet d'apprentissage, et la plupart d'entre eux appliquent l'approche basée sur la position. Une revue des travaux menés avant 2023 prenant en compte l'effet d'apprentissage dans l'ALBP est disponible dans [1]. Une version relaxée du SALBP avec effet d'apprentissage (SALBP/L) a été abordée pour la première fois dans [11]. Les auteurs y ont démontré que l'affectation optimale des tâches, tout en minimisant le TdC d'un lot de production, est déséquilibrée en présence d'un apprentissage homogène. Ce travail a été étendu au SALBP/L dans [17]. La programmation linéaire en nombres entiers (ILP) et une approche math-heuristique, basée sur la recherche à voisinage variable et la programmation dynamique, ont été utilisées pour traiter le même problème dans [5]. Dans [18], les auteurs ont proposé deux procédures de rééquilibrage pour le SALBP/L afin de réduire le nombre de postes de travail sur la ligne. Cependant, ce travail adopte une vision relaxée de l'effet d'apprentissage lors du comptage du nombre de répétitions des tâches dans l'approche d'apprentissage basée sur la position. En effet, une tâche d'un exemplaire introduit plus tard peut être traitée avant celle d'un exemplaire introduit plus tôt, et plusieurs instances d'une même tâche peuvent être traitées simultanément pour différents exemplaires. Plus récemment, l'ALBP à modèles mixtes incorporant l'effet d'apprentissage a été abordé à l'aide d'approches ILP et math-heuristiques, étendant encore davantage les recherches dans ce domaine [4, 19].

À notre connaissance, aucun travail dans la littérature n'aborde simultanément le RCALBP en tenant compte des aspects de planification avec des durées de tâches dépendantes de l'effet d'apprentissage.

## 3 Description du problème

La ligne d'assemblage considérée est mono-produit et droite. De plus, en raison de la nature de la ligne d'assemblage aéronautique, nous avons introduit la notion de *zone*. Chaque poste de travail contient le même ensemble de zones, situées soit à l'intérieur, soit à l'extérieur de l'appareil. Chaque zone possède une capacité et peut être considérée comme une ressource cumulative et réutilisable pour l'exécution des tâches. En outre, pour des raisons de sécurité, certaines tâches peuvent désactiver temporairement certaines zones pendant leur exécution. Lorsqu'une zone est désactivée, toute tâche nécessitant cette zone ne peut être exécutée. Toutefois, plusieurs tâches qui désactivent la même zone peuvent être réalisées simultanément. Dans cette section, nous décrivons formellement les composants nécessaires à la définition d'une instance de RC-ALBP/L, dans le but de minimiser la durée de la phase d'apprentissage ainsi que le nombre d'ajustements de la ligne.

### 3.1 Entrées du problème

Une instance de RC-ALBP/L est définie par un n-uplet constitué des éléments suivants.

* Le TdC cible $c_{tgt}$, qui correspond au TdC que l'on souhaite atteindre.

* La valeur maximale du TdC $c_{max}$, c'est-à-dire le
temps maximal autorisé entre l'assemblage de deux exemplaires consécutifs.

* L'ensemble des postes de travail $W = \llbracket 1, W \rrbracket^1$. Les postes sont ordonnés de 1 à W le long de la ligne.

* L'ensemble des périodes $\mathcal{P} = \llbracket 1, P \rrbracket$. Au début de chaque période, un nouvel exemplaire entre sur la ligne à la première station, et tous les exemplaires sur la ligne sont déplacés vers leurs stations suivantes. P peut être considéré comme le nombre maximal d'exemplaires pour atteindre la cadence cible. La durée d'une période, qui correspond au TdC de la ligne durant cette période, est une variable de décision.

* L'ensemble des tâches $\mathcal{T}$, avec pour chaque tâche $t \in \mathcal{T}$, une fonction décroissante, notée $dur_t: \mathbb{Z} \to \mathbb{N}$, qui retourne la durée de la tâche en fonction du nombre de fois qu'elle a été entièrement exécutée auparavant, ou zéro si l'entrée est négative. Notons que, dans la période numéro $p$, le nombre d'exécutions complètes d'une tâche affectée au poste $w$ est $p-w$. Par exemple, la durée d'une tâche $t$ affectée au poste 3 pendant la période 2 est $dur_t(2-3) = 0$, puisque le poste 3 n'est pas encore en service pendant la période 2. Pendant la période 5, sa durée est $dur_t(5-3) = dur_t(2)$, car elle a été exécutée deux fois (période 3 et période 4).

* Le graphe $\mathcal{G} = (\mathcal{T}, \mathcal{A})$ représente la relation de précédence entre les tâches dans $\mathcal{T}$. Un arc $(t, u)$ indique que $t$ doit être terminée avant le début de $u$.

* L'ensemble des ressources $\mathcal{R}$, où pour chaque ressource $r \in \mathcal{R}$, $capa_r$ désigne la capacité de $r$, et $cons_{r,t}$ désigne la quantité de ressource $r$ consommée par la tâche $t \in \mathcal{T}$. Les ressources peuvent généralement représenter un ensemble de machines ou un ensemble de technicien(ne)s affectés à un poste de travail pour exécuter des tâches dans ce poste.

* L'ensemble des zones $\mathcal{Z}$, où, pour chaque zone $z \in \mathcal{Z}$, $capa_z$ désigne la capacité de $z$, $cons_{z,t}$ désigne la place de la zone $z$ occupée par la tâche $t \in \mathcal{T}$, et $\mathcal{D}_t \subseteq \mathcal{Z}$ est l'ensemble des zones qui sont désactivées pendant l'exécution de la tâche $t$.

* L'horizon temporel est relatif à chaque station de travail, et noté $\mathcal{H} = \llbracket 0, c_{max} \rrbracket$.

**Hypothèses.** Une instance de RC-ALBP/L est dite bien formée si les hypothèses suivantes sont vérifiées.

1. Le nombre de périodes $P$ est supérieur au nombre de postes de travail $W$.

2. Le TdC ne peut pas être modifié pendant la phase de remplissage de la ligne (les $W$ premières périodes). Sous cette hypothèse, le TdC durant ces périodes est égal au TdC maximal parmi elles.

3. Le premier TdC est supérieur au TdC cible.

**Exemple 1.** Nous considérons un exemple simplifié, instance de RC-ALBP/L, composé de 2 postes de travail, 2 ressources $\{r_1, r_2\}$, chacune avec une capacité de 6, et une

zone $z$ ayant une capacité de 1. Le TdC cible est de 12 et le nombre maximal de périodes pour la montée en cadence est de 6. La valeur maximale du TdC est de 20. Il y a 6 tâches, chacune ayant une courbe d'apprentissage individuelle, c'est-à-dire des durées dépendant du nombre d'exécutions complètes de la tâche. La consommation des ressources et de la zone par chaque tâche est représentée dans la Table 1. La tâche $c$ est la seule à désactiver la zone $z$ pendant son exécution. Le graphe de précédence entre les tâches est présenté dans la Figure 2.

<table><caption>TABLE 1 – Exemple : l’informations sur les tâches</caption><thead><tr><th rowspan="2">Task</th><th colspan="3">Consumption</th><th rowspan="2">D<sub>t</sub></th><th colspan="5">dur<sub>t</sub>(n) avec n =</th></tr><tr><th>r<sub>1</sub></th><th>r<sub>2</sub></th><th>z</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th></tr></thead><tbody><tr><td>a</td><td>3</td><td>1</td><td>1</td><td>-</td><td>9</td><td>8</td><td>7</td><td>6</td><td>5</td><td>5</td></tr><tr><td>b</td><td>2</td><td>2</td><td>1</td><td>-</td><td>10</td><td>7</td><td>4</td><td>4</td><td>4</td><td>4</td></tr><tr><td>c</td><td>1</td><td>1</td><td>0</td><td>z</td><td>4</td><td>4</td><td>4</td><td>4</td><td>4</td><td>4</td></tr><tr><td>d</td><td>0</td><td>3</td><td>0</td><td>-</td><td>8</td><td>5</td><td>3</td><td>3</td><td>2</td><td>2</td></tr><tr><td>e</td><td>2</td><td>1</td><td>1</td><td>-</td><td>7</td><td>6</td><td>6</td><td>5</td><td>5</td><td>5</td></tr><tr><td>f</td><td>1</td><td>2</td><td>0</td><td>-</td><td>5</td><td>5</td><td>4</td><td>4</td><td>3</td><td>3</td></tr></tbody></table>

<figure><img src="image_3.png" /><figcaption>FIGURE 2 – Exemple : la relation de précédence</figcaption></figure>

## 3.2 Affectation, solution et Pareto-optimalité

**Affectation.** Une affectation d'une instance de RC-ALBP/L est définie par un n-uplet $(wks, raw, start, cyc)$, où :

* $wks: \mathcal{T} \to \mathcal{W}$ est une fonction qui associe, à chaque tâche $t \in \mathcal{T}$, le poste $w \in \mathcal{W}$ auquel elle est affectée;

* $raw: \mathcal{R} \times \mathcal{W} \to \mathbb{N}$ est une fonction qui associe, à chaque paire composée d'une ressource $r \in \mathcal{R}$ et d'un poste $w \in \mathcal{W}$, la quantité de $r$ allouée au $w$;

* $start: \mathcal{T} \times \mathcal{P} \to \mathbb{N}$ est une fonction qui associe, à chaque tâche $t \in \mathcal{T}$ et à chaque période $p \in \mathcal{P}$, la date de début de $t$ relativement au poste de travail auquel elle est affectée pendant la période $p$;

* $cyc: \mathcal{P} \to \mathbb{N}$ est une fonction qui associe, à chaque période $p \in \mathcal{P}$, son TdC.

Notons que nous supposons dans cette étude que l'affectation des tâches et du nombre de ressources aux stations est le même pour toutes les périodes. Cependant, l'ordonnancement des tâches au sein de chaque station peut changer d'une période à l'autre.

On définit une fonction supplémentaire $end: \mathcal{T} \times \mathcal{P} \to \mathbb{N}$ qui retourne, pour chaque tâche $t$ et chaque période $p$, la date de fin de $t$ pendant $p$, relative à son poste de travail. La valeur de cette fonction peut être calculée comme suit :

$$end(t, p) = start(t, p) + dur_t(p - wks(t))$$

<footnote n="1">1. La notation $\llbracket 1, n \rrbracket$ désigne l'ensemble $\{1, 2, \dots, n\}$.</footnote>
# Remerciements

Ce travail a bénéficié du soutien de l'ANR (France 2030), dans le cadre du projet MAIA (ANR-22-EXES-0009).

# Références

[1] Z.Z. El Abidine and T. Koltai. The effect of learning on assembly line balancing : A review. *Periodica Po-lytechnica Social and Management Sciences*, 2023.

[2] K. Ağpak and H. Gökçen. Assembly line balancing : Two resource constrained cases. *International Journal of Production Economics*, 96(1):129-140, 2005.

[3] H.M. Alakaş, M. Pınarbaşı, and M. Yüzükırmızı. Constraint programming model for resource-constrained assembly line balancing problem. *Soft Computing*, 24:5367-5375, 2020.

[4] E. Alhomaidhi. Enhancing efficiency and adaptability in mixed model line balancing through the fusion of learning effects and worker prerequisites. *International Journal of Industrial Engineering Computations*, 15(2):541-552, 2024.

[5] Z. Bao and L. Chen. A matheuristic approach for the aircraft final assembly line balancing problem considering learning curve. In *2023 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM)*, pages 1389-1393. IEEE, 2023.

[6] O. Battaïa and A. Dolgui. A taxonomy of line balancing problems and their solution approaches. *International Journal of Production Economics*, 142(2):259-277, 2013.

[7] O. Battaïa and A. Dolgui. Hybridizations in line balancing problems : A comprehensive review on new trends and formulations. *International Journal of Production Economics*, 250:108673, 2022.

[8] N. Boysen, P. Schulze, and A. Scholl. Assembly line balancing : What happened in the last fifteen years? *European Journal of Operational Research*, 301(3):797-814, 2022.

[9] J. Bukchin and M. Masin. Multi-objective design of team oriented assembly systems. *European Journal of Operational Research*, 156(2):326-352, 2004.

[10] Z.A. Çil and D. Kizilay. Constraint programming model for multi-manned assembly line balancing problem. *Computers & Operations Research*, 124:105069, 2020.

[11] Y. Cohen, G. Vitner, and S.C. Sarin. Optimal allocation of work in assembly lines for lots with homogeneous learning. *European Journal of Operational Research*, 168(3):922-931, 2006. Balancing Assembly and Transfer lines.

[12] A. Corominas, L. Ferrer, and R. Pastor. Assembly line balancing : general resource-constrained case. *International Journal of Production Research*, 49(12):3527-3542, 2011.

[13] S.G. Dimitriadis. Assembly line balancing and group working : A heuristic procedure for workers' groups operating on the same product and workstation. *Computers & Operations Research*, 33(9):2757-2774, 2006. Part Special Issue : Anniversary Focused Issue of Computers & Operations Research on Tabu Search.

[14] E.B. Edis. Constraint programming approaches to disassembly line balancing problem with sequencing decisions. *Computers & Operations Research*, 126:105111, 2021.

[15] E.H. Grosse, C.H. Glock, and S. Müller. Production economics and the learning curve : A meta-analysis. *International Journal of Production Economics*, 170:401-412, 2015.

[16] W.B. Helgeson and D.P. Birnie. Assembly line balancing using the ranked positional weight technique. *Journal of industrial engineering*, 12(6):394-398, 1961.

[17] T. Koltai and N. Kalló. Analysis of the effect of learning on the throughput-time in simple assembly lines. *Computers & Industrial Engineering*, 111:507-515, 2017.

[18] Y. Li and T.O. Boucher. Assembly line balancing problem with task learning and dynamic task reassignment. *The International Journal of Advanced Manufacturing Technology*, 88:3089-3097, 2017.

[19] Y. Li, D. Liu, and I. Kucukkoc. Mixed-model assembly line balancing problem considering learning effect and uncertain demand. *Journal of Computational and Applied Mathematics*, 422:114823, 2023.

[20] D. Ogan and M. Azizoglu. A branch and bound method for the line balancing problem in u-shaped assembly lines with equipment requirements. *Journal of Manufacturing Systems*, 36:46-54, 2015.

[21] X. Pucel and S. Roussel. Constraint Programming Model for Assembly Line Balancing and Scheduling with Walking Workers and Parallel Stations. In Paul Shaw, editor, *30th International Conference on Principles and Practice of Constraint Programming (CP 2024)*, volume 307, pages 23:1-23:21, 2024.

[22] S. Roussel, T. Polacsek, and A. Chan. Assembly line preliminary design optimization for an aircraft. In *CP 2023 (The 29th International Conference on Principles and Practice of Constraint Programming)*, 2023.

[23] K.E. Stecke and M. Mokhtarzadeh. Balancing collaborative human-robot assembly lines to optimise cycle time and ergonomic risk. *International Journal of Production Research*, 60(1):25-47, 2022.

[24] J.M. Wilson. Formulation of a problem involving assembly lines with multiple manning of work stations. *International Journal of Production Research*, 24(1):59-63, 1986.

[25] T.P. Wright. Factors affecting the cost of airplanes. *Journal of the aeronautical sciences*, 3(4):122-128, 1936.
[26] L.E. Yelle. The learning curve : Historical review and comprehensive survey. *Decision sciences*, 10(2):302–328, 1979.

[27] Z.A. ÇİL. An exact solution method for multi-manned disassembly line design with and/or precedence relations. *Applied Mathematical Modelling*, 99:785–803, 2021.