Ce travail concerne la production cyclique de pièces identiques dans un flow-shop robotisé. La Conjecture des 1-cycles, proposée par Sethi et al., suppose que le taux maximum de production peut être atteint en répétant un cycle particulier qui produit une seule pièce. Cette conjecture simplifie la recherche du meilleur cycle de production. Nous présentons de nouvelles preuves (approche par les graphes et approche algébrique) de la validité de cette conjecture pour des cellules à 2 et 3 machines et nous montrons qu'elle est fausse à partir de 4 machines. Nous délimitons ensuite plus précisément son cadre de validité en imposant des restrictions sur les paramètres : distances inter-machines égales ou temps d'usinage égaux. Puis, nous étudions d'autres formes de cellules robotisées en relaxant des contraintes de la cellule robotisée de base. La première variante est l'association de l'entrée et de la sortie de la cellule. Nous proposons quelques remarques sur la recherche du meilleur cycle de production. La deuxième variante est le HSP (Hoist Scheduling Problem) : le temps pendant lequel une pièce peut rester sur une machine admet une borne supérieure. Nous montrons que des propriétés des cellules robotisées ne peuvent pas être étendues au HSP. La troisième variante est l'ajout de zones de stockage entre les machines. Nous montrons que la Conjecture des 1-cycles est vraie et nous analysons le gain par rapport à une cellule sans stockage. Enfin, nous supposons que les distances inter-machines sont quelconques. Nous montrons que trouver le meilleur cycle de production d'une pièce est un problème NP-complet. Ce travail a permis de résoudre complètement une conjecture ouverte depuis 1989 et de décrire l'influence de la relaxation de certaines contraintes des cellules robotisées sur la recherche du meilleur cycle de production. La principale perspective est, pour les cas où la conjecture est fausse, de trouver le meilleur cycle de production.

L'évolution de l'environnement des entreprises a transformé la nature des relations entre elles, qui de simple relations d'achat entre clients et fournisseurs se sont transformées en des rapports plus contractualisés et plus durables. Ces derniers imposent à ces entreprises de revoir leurs méthodes de gestion et de production pour une meilleure synchronisation de leurs flux. Nous nous intéressons dans ce mémoire à une relation particulière entre clients et fournisseurs, celle fondée sur le principe de livraisons cycliques, selon lequel le fournisseur s 'engage à livrer des quantités de produits à des intervalles de temps fixes et de façon répétitive. L'intérêt de ce mode de livraison et qu'il permet, aux donneurs d'ordres, une gestion extrêmement simple des approvisionnements et facilite l'organisation des activités. Comme réponse à ce type de livraisons et afin de synchroniser leurs flux de production à ceux de livraisons, les entreprises adoptent la production cyclique. L'avantage de cette dernière est qu ;elle permet entre autres de réduire les coûts engendrés par la fabrication, et de simplifier l'organisation du travail. Notre travail consiste alors en l'évaluation et la mise en oeuvre d'un plan de production cyclique, pour un atelier de type Flow Shop pur fabricant plusieurs produits, lorsque les appels de livraisons sont cycliques. Nous proposons une nouvelle méthode déterminant un plan de production cyclique minimisant des coûts de lancements, coûts de stockage et des coûts de fabrication. Nous introduisons dans un premier temps le contexte -de notre travail en précisant les différentes hypothèses que 1 'on pose. Nous proposons par la suite une revue de la littérature sur les différents travaux réalisés, et proposons une classification des problèmes traitant de la production cyclique étudiés par la communauté scientifique. Nous exposons également la méthode que l'on propose pour la détermination d'un plan de production cyclique minimisant les différents coûts que l'on considère. Nous présentons une analyse des résultats issus de l'application de notre approche ainsi que ses variantes sur un ensemble de benchmarks générés aléatoirement et respectant les traits caractéristiques des problèmes réels. Nous réalisons une étude comparative d?s approches que l'on propose à 1 'une de celles proposées dans la littérature. Nous terminons ce mémoire par une conclusion et un ensemble de voies de recherches futures.

Nos travaux de recherche portent sur le problème de prise en compte des contraintes liées aux ressources humaines, en termes d'affectation des opérateurs aux machines, dans les problèmes d'ordonnancement d'atelier. Ce problème intégrant l'affectation des opérateurs aux machines consiste à déterminer 1 'état d'atelier au cours du temps, et à considérer le problème d'ordonnancement d'atelier dans sa globalité en prenant en compte l'influence de l'affectation des ressources humaines sur les activités de production. Ceci impose en plus de la gestion de la séquence des travaux, la gestion des affectations des hommes aux postes de travail. Nous avons considéré le cas où les productivités des machines dépendant de 1 'affectation des opérateurs. Nous avons supposé que le nombre d'opérateurs est inférieur au nombre de machines, un opérateur peut superviser simultanément plusieurs machines et que la supervision simultanée de plusieurs machines par un opérateur diminue les productivités de ces dernières. L'originalité de nos travaux de recherche est liée au fait que les durées opératoires des travaux sont variables dans le temps et sont fonctions de 1 'évolution des affectations des opérateurs aux machines dans le temps. Deux grandes parties composent nos travaux de recherche. La première partie porte sur le problème de modélisation de 1 'affectation des opérateurs aux machines. Elle consiste en la proposition d'un cadre théorique pour 1 'intégration des contraintes liées à la prise en compte des ressources humaines, en terme d'affectation des opérateurs aux machines, dans la modélisation des problèmes d'ordonnancement d'atelier. Une définition d'un problème d'ordonnancement d'atelier impliquant l'aspect" ressources humaines" est alors proposée. La seconde partie a porté sur une application de la modélisation proposée dans la première partie pour le cas d'une production cyclique. Plus précisément, nous avons étudié le problème d'existence d'une affectation des opérateurs réalisant un ordonnancement cyclique pour un atelier_ de type Flow Shop. Nous avons supposé qu'un ordonnancement cyclique, défini par une durée de cycle et un ensemble de travaux à réaliser durant cette durée, est donné pour des productivités nominales des machines et sans aucune prise en compte des ressources humaines. Par conséquent, et dans le cas où le nombre d'opérateurs est inférieur au nombre de machines et que l'affectation des opérateurs conditionnent les productivités des machines, 1 'introduction et la considération des ressources humaines pour la réalisation de l'ordonnancement cyclique pourrait allonger la durée d'exécution des travaux et remettre en cause la durée de cycle. Nous avons étudié ce problème d'existence d'une affectation des opérateurs réalisable pour Flow Shop Cyclique pour trois modes de réaffectations des opérateurs : calendaire, sur évènement de fin de tâche et libre. Nous avons présenté une formulation mathématique du problème pour ces trois modes de réaffectation des opérateurs, démontré que ce problème est NP-complet pour les deux modes calendaires et sur événement, et qu'une restriction du problème de mode de réaffectation libre est NP-complet. Nous avons également proposé, pour ces trois modes, un modèle mathématique linéaire en nombre entier. Une approche de résolution basée sur le principe de la programmation dynamique a été proposée pour les deux modes réaffectation calendaire et sur événement.

La première partie de ce travail concerne la production cyclique pour l'optimisation du taux de production dans les flowshops robotisés, où un robot est chargé du transport des pièces. Les cellules robotisées peuvent être disposées de façon linéaire ou circulaire. Les principaux résultats théoriques concernant la disposition linéaire ne peuvent être étendus à la configuration circulaire. En particulier, trouver le meilleur cycle de production de une pièce (1-cycle) est un problème polynomial dans le cas des cellules linéaires additives, mais NP-difficile pour la configuration correspondante circulaire.Nous nous concentrons principalement sur le cas des cellules circulaires équilibrées, où le temps d'usinage est identique sur toutes les machines. Après avoir présentés des outils pour l'analyse cyclique dans les cellules circulaires, nous établissons des propriétés nécessaires des 1-cycles performants, ce qui permet de conclure sur le problème du meilleur 1-cycle jusqu'à 8 machines. Toutefois, nous fournissons un contre-exemple pour 6 machines à la conjecture classique des 1-cycles, toujours ouverte dans cette configuration.Ensuite, nous étudions la structure des 1-cycles performants pour des cellules circulaires équilibrées arbitrairement grandes. Nous définissons et étudions les propriétés d'une nouvelle famille de cycles basée sur cette structure et formulons une conjecture sur sa dominance sur les 1-cycles qui conduirait à un algorithme polynomial pour le problème du meilleur 1-cycle dans ce cas. Cette structure permet de déterminer le meilleur 1-cycle jusqu'à 11 machines.Dans la deuxième partie, nous présentons le travail réalisé sur un problème industriel proposé par la SNCF dans le cadre du challenge ROADEF/EURO. Nous proposons un algorithme glouton pour ce problème combinant divers aspects de la gestion des trains au sein d'une gare. / The first part of this work deals with cyclic production for throughput optimization in robotic flow-shops, where a robot is in charge of the material handling of parts. Robotic cells may have a linear or a circular layout. Most theoretical results for the linear layout do not hold for the circular layout. In particular, the problem of finding the best one part production cycle (1-cycle), which is a polynomial problem for linear additive cells, has been proved NP-hard for the corresponding circular configuration.We mainly focus on a special case of circular balanced cells, where the processing times are identical for all machines. After presenting tools for cyclic analysis in circular cells, we study necessary properties of efficient 1-cycles. These results allow to conclude on the best one part production cycle for any parameters in circular balanced cells up to 8 machines. However, we provide a counter-example to the classical 1-cycle conjecture, still open for this configuration.Then, we study the structure of efficient one part production cycles in arbitrarily large circular balanced cells. We introduce and study a new family of cycles based on this structure, and formulate a conjecture on its dominance over one part-production cycles, which would lead to a polynomial algorithm for finding the best 1-cycle for circular balanced cells. This structure allows to settle the best one part production cycle for cells with up to 11 machines.In a second part, we present work on an industrial problem of railway stock scheduling proposed by the French railway company in the context of the ROADEF/EURO competition. We propose a greedy algorithm for this problem combining the various aspects of trains handling inside a station.