PROBLÈMES COMBINATOIRES EN CONFIGURATION DES LIGNES DE FABRICATION : ANALYSE DE COMPLEXITÉ ET OPTIMISATION - FAYOL / DEMO : Décision en Entreprise : Modélisation, Optimisation Access content directly
Theses Year : 2012

COMBINATORIAL PROBLEMS IN PRODUCTION LINES CONFIGURATION : COMPUTATIONAL ANALYSIS AND OPTIMIZATION

PROBLÈMES COMBINATOIRES EN CONFIGURATION DES LIGNES DE FABRICATION : ANALYSE DE COMPLEXITÉ ET OPTIMISATION

Abstract

The objective of this thesis is to create and develop new effective solution methods for production line configuration problems. Two problems were studied: the equipment selection and balancing problem for dedicated lines and the setup cost minimization problem for multi-product lines. A solution for the first problem consists in a feasible assignment of the resources to an unknown number of stations so that the total cost is minimized. In order to solve this problem, we reduced it to the set partitioning problem and solved it by greedy heuristics and an exact method of constraint generation. The computer experiments on different problem instances showed that the new solution approach outperforms the previous methods from the literature both in terms of solution quality and computational time. For the second problem two criteria were considered lexicographically: the minimization of the number of stations and the minimization of the total setup cost. We examined successively the cases with parallel and sequential execution of operations. Approximate solutions were found by greedy heuristics. Then, we proposed two integer programming models in order to obtain the minimal number of stations and then the minimal setup cost. The experimental results for this new problem proved to be promising both in terms of solution quality and computational time.
L'objectif de la thèse est de créer et développer de nouvelles méthodes de résolution efficaces des problèmes combinatoires en configuration des lignes de fabrication. Deux problèmes ont été particulièrement étudiés: le problème d'équilibrage et de choix d'équipement pour des lignes dédiées et le problème de minimisation des coûts de changements de séries pour des lignes multi-produits. Une solution du premier problème consiste en une affectation admissible des ressources à un nombre de stations à déterminer de sorte que le coût total soit minimal. Afin de résoudre ce problème, nous l'avons réduit au problème de partition d'ensemble et l'avons résolu par des heuristiques gloutonnes et une méthode exacte de génération de contraintes. Les expérimentations sur différentes instances ont montré que la nouvelle approche de résolution surclasse les approches antérieures de la littérature en termes de qualité de solution et de temps de calcul. Pour le second problème deux critères sont considérés lexicographiquement : la minimisation du nombre de stations et la minimisation du coût de changement de séries. Nous avons examiné successivement les cas d'exécution parallèle et séquentielle des opérations. Des solutions approchées ont été trouvées par des heuristiques gloutonnes. Ensuite, nous avons proposé deux modèles de programmation linéaire en nombres entiers (PLNE) afin de trouver le nombre de stations minimal et ensuite d'obtenir le coût de changement de séries minimal. Les résultats des expérimentations sur ces nouveaux problèmes se sont avérés prometteurs à la fois en termes de qualité de solution et de temps de calcul.
Fichier principal
Vignette du fichier
kovalev-sergey-these.pdf (2.38 Mo) Télécharger le fichier
Origin : Version validated by the jury (STAR)
Loading...

Dates and versions

tel-00849179 , version 1 (30-07-2013)

Identifiers

  • HAL Id : tel-00849179 , version 1

Cite

Sergey Kovalev. PROBLÈMES COMBINATOIRES EN CONFIGURATION DES LIGNES DE FABRICATION : ANALYSE DE COMPLEXITÉ ET OPTIMISATION. Autre. Ecole Nationale Supérieure des Mines de Saint-Etienne, 2012. Français. ⟨NNT : 2012EMSE0672⟩. ⟨tel-00849179⟩
402 View
2268 Download

Share

Gmail Facebook X LinkedIn More