Keywords: Scheduling, Flowshop, Robotic cell, Material Handling System, Cyclic Production, Circular Layout, Railway Stock Management

Une thèse, c'est comme l'éternité : un peu long, surtout vers la fin. En revanche, c'est sans doute moins solitaire. Dans ces pages, déjà trop longues et malgré tout trop courtes pour remercier toutes celles et ceux qui ont eu leur rôle à jouer, inutile de chercher un plan, fut-il chronologique, thématique, encore moins didactique. Lecteur, lectrice : débrouillez-vous.

Commençons par la fin : je tiens à remercier Safia Kedad-Sidhoum et Ameur Soukhal d'avoir accepté de rapporter ce travail et de lire avec attention mes divague-ations (c'était facile) en pleine période de rentrée. Merci à Fabien Mangione d'avoir replongé dans sa petite enfance pour faire partie de mon jury, et merci à Alessandro Agnetis de m'avoir fait l'honneur de présider celui-ci. Grazie anche per il tuo accoglio, et per avere corretto i miei congiuntivi. A tou•te•s, merci pour vos remarques, vos questions, votre intérêt et votre bienveillance qui ont contribué à faire de la clôture de ces années un bon souvenir.

On recommencerait presque ? Quand même pas. Revenons tout de même aux débuts, et donc à Nadia Brauner et Nicolas Catusse. Nadia, la toute première fois que tu m'as parlé de cellules robotisées avec des pièces de 5 centimes, elles tournaient déjà en rond : ce n'est que plus tard que j'ai compris pourquoi. Merci de m'avoir fait confiance quand je ne l'aurais pas fait moi-même, et d'avoir inlassablement tenté de me convaincre que ma thèse est une thèse (maintenant, je vais bien finir par le croire). Merci aussi d'avoir patiemment repris mes « s » et mes calculs -pour les virgules, par contre, je ne céderai pas. Merci Nicolas pour ton enthousiasme contagieux, tes intuitions bluffantes et ton pragmatisme salutaire. Merci à tou•te•s les deux pour votre disponibilité touchante (malgré la rude compétition avec Caseine). Et surtout, si finir une thèse, c'est avoir appris, alors grâce à vous celle-ci est réussie.

Quatre ans de thèse dont deux d'enseignement, et il faut croire que j'y ai pris goût : merci à toute l'équipe du département MMI, Vanda Luengo, Jean-François Berdjugin et Vincent Lestideau avec qui j'ai eu le plaisir de travailler, et merci bien sûr à mes étudiant•e•s toujours là pour me rappeler que « mais Madame, c'est pas logique ! » -c'était pour voir si vous suiviez. * * * vii viii REMERCIEMENTS Avant l'histoire, il y a la préquelle : sans remonter à ma première pâte à sel (encore que...), je tiens à remercier Madame Cornet pour avoir fait des « maths » un joli monde traversé de petites et grandes histoires parsemées de ponctuations interrogatives, suspendues ou enthousiastes, sans jamais sacrifier une rigueur qui m'a fait gagner beaucoup de temps par la suite.

Suivent les ami•e•s qui ont balisé mon chemin jusqu'ici. Cécile, bien sûr : après tout c'est pour le plaisir de ta conversation (et pas pour la science ni les beaux yeux de Justin !) que j'ai atterri dans mon premier cours de « Combinatoire et Graphes ». Pour reprendre tes mots, on n'aurait pas cru à l'époque, il y a 8 ou 9 ans d'ici, finir un jour en haut de la tour Zamansky (ou dans mon cas, plus modestement, du bâtiment F) « pompettes, et doctoresses » ! Tu remercieras aussi Thomas pour ses « conseils de vieux » que je n'ai, bien évidemment, jamais suivis (je ne dis pas que ce n'était pas un tort). Je n'oublie pas Sophie, à qui je pense encore à chaque fois que ma bouilloire chauffe pour une tasse de thé nocturne (sur ces dernières années, ça veut dire « souvent » !), Laure sans qui la prépa est beaucoup moins drôle, Mélissa avec qui j'ai (énergiquement !) fait mes armes et mes griffes de bébé-informaticienne et qui s'entête malgré tout à me supporter régulièrement le temps d'une pause en bord de mer.

A propos de binôme, Eli : sans nos démêlées avec la coloration de Juliette, la décomposition de Benders et même une transformée de Laplace égarée, sans nos doutes partagés, je ne me serais sans doute pas dit que peut-être, après tout... une thèse... tu crois qu'on peut ? Enfin, voilà le reste de la dream-team : Hugo, coauteur, co-équipier, co-ADOC, co-procrastinateur, co-à peu près tout sauf bureau, en fait, et Lucas, co-bureau adoptif aux talents de portraitiste incontestés (mais pas que). Depuis les après-midi à élaborer des plans de carrière alternatifs entre deux preuves par déchargement sur les tableaux de l'UFR IM 2 AG, on a pas mal grandi, et les plans ont changé 1 . Je suis heureuse d'avoir commencé et de terminer cette histoire à vos côtés -à ce propos, Hugo : c'est bon, tu peux soutenir maintenant. * * * Me voilà avec vous revenue aux portes de G-SCOP : merci Maria et Marie-Laure d'y avoir accompagné mes premiers pas -quelque peu maladroits. Merci à mes co-bureau successifs et simultanés, d'abord Boris et Saleh Eddine tout au bout du bout du 2C, puis Michaël qui a placé la barre drôlement haut, enfin Kean et ses implacables 10 pages/semaine qui n'empêchent pas de rigoler pour autant, et puis Nicolas qui entre ses deux trains, ses quatre stagiaires et ses vingt problèmes à gérer trouve toujours le temps pour une petite bataille de chansons agaçantes à se coincer en tête.

Hors des bureaux, il y a des couloirs animés, une kfet pleine à craquer (et parfois d'autres lieux mieux irrigués : selon votre génération, Saint-Vincent, Re-1 Alors, ce labo indépendant dans le Trièves, on s'y met quand ? * * * Repassons la porte. Merci aux Grenobloi•se•s, Téo qui n'a jamais abandonné la bière du vendredi soir malgré mes réponses sporadiques en 3ème année et plus, Quentin pour la pastèque (désolée, pour cette soutenance-ci ce n'était plus la saison), Kévin pour nos trop rares synchronisations compensées par la densité des discussions, Irina, toujours une bonne raison pour faire le trajet jusqu'au campus, et bien sûr Seb, malgré ses infidélités avec la Savoie et l'Ardèche.

Dézoomons encore un peu : de leurs labos français ou européens (ou d'un bateau en Antarctique), un grand merci aux habituées du topic doctorat, et tout particulièrement au « bureau » des Licornes à Paillettes (voilà, c'est dit) : Anaïs, Cori, Dom, Emilie, Léa... de râlages en verbalisations, de soutien moral en digressions, on n'a pas toujours fait avancer la Science et la Recherche, mais depuis qu'ils jouent gentiment entre eux, nos Gonzague, Charles-Henri, Gérard et autres Raichu nous fichent un peu plus la paix, non ? * * * Il y en aurait bien d'autres (Guillaume pour m'avoir aidé à résoudre ce problème crucial : « le jury, deuxième ou troisième rang ? », MamieCaro pour la meilleure citation de tableau au monde, et même un plombier bio pas étranger à ma décision de commencer une thèse...), mais pour ne pas précéder ce manuscrit d'un roman, il va falloir conclure. Je finirai donc en mêlant ici et peut-être ailleurs, passé, présent et je l'espère futur : merci David, d'avoir été, d'être et de rester, celui auprès de qui j'ai envie de me réveiller chaque matin et de m'endormir chaque soir (mais jamais sur mes lunettes). Eh, monsieur, tu sais quoi ? T'es quand même chouette.

ix naissance ou Sun Valley). J'ai pu y faire la connaissance, au gré de discussions plus ou moins scientifiques, plus ou moins échauffées, d'un paquet de personnalités. Permanentes : entre autres Bernard, Hadrien2 , Louis, Nicolas (encore un), Olivier, Vincent (préviens-moi quand même si tu casses ma conjecture), Zoltán... et moins permanentes : les matheux qu'il ne faut pas placer côte-à-côte dans les dîners où l'on cause, Quentin, Rémi, Yohann, les coincheur•se•s qui m'ont tolérée malgré tout et tout•e•s les autres, Alex, Clément, Élodie, Franck, Justine, Lisa, Matthieu, Nico la tête me tourne et j'en oublie. Merci Tom de lire mes mailspresque-sérieux, merci Aurélie et Lucie grâce à qui je me suis parfois sentie moins seule, et bon courage à mon p'tit frère Florian pour venir à bout du cas 4.2.42bis (hein que c'est chouette, les preuves d'ordonnancement ?).

Pour rester en famille, un merci à part (désolée) pour mon très-grand frère de thèse, Pierre avec et sans initiale, d'avoir relevé ces années de nouveaux paysages, de jolies découvertes, et même de (vrais) petits lutins dansant entre les lignes de L A T E X3 . De m'avoir, aussi, prêté un peu de sa bienveillance quand la mienne me faisait défaut. Et puisqu'il a bien fallu penser à « l'après », merci à Julie pour ses conseils (parfois par procuration), et sur une autre note, la franchise d'un sourire contagieux (même si ses Gourdon, eux, me regardent un peu de travers).

Un labo peuplé uniquement de chercheur•se•s (fussent-illes enseignant•e•s) sombrerait vite dans le chaos. Merci donc à celles et ceux qui font que pourtant, il tourne : Marie Jo grâce à qui je sais maintenant (entre autre) charger correctement une agrafeuse, Fadila, Myriam, ainsi que les membres passés et présents des services informatique et financier -en particulier Amandine et Christine pour leur aide lors de l'organisation des journées G-SCOP.

x REMERCIEMENTS Allez, tant qu'on y est, traversons l'Atlantique : Emeline, tu rentres dans tellement de catégories à la fois (et en même temps aucune) que je ne sais pas où te placer. Merci d'être là depuis maintenant 13 ans, pour ta fenêtre ouverte malgré le décalage horaire, pour ton fauteuil encore mieux qu'un canapé-lit et tes tentatives de nourrir « une thésarde en rédaction » ; merci à Émile de te maintenir en forme parce que sinon je serais quand même super embêtée. Et puis courage : on dirait pas comme ça, mais c'est bientôt fini. * * * Retour aux sources (géographiquement instables). « Mieux vaut Thiard que jamais », dit l'adage, et cette thèse n'y échappe pas. Merci à ma maman qui ne s'est pas trop fichue de moi en me voyant traîner de mois d'août en mois d'août un chapitre 1 toujours à commencer, à mon papa sans qui je n'aurais pas poussé si loin la métaphore maritime (et me serais contentée en bonne Grenobloise de parler de montagnes et de cols), et à tou•te•s deux de m'avoir envoyée dans le vaste monde équipée, en sus d'une trousse à couture, d'un tournevis et de conseils plus ou moins avisés, du réconfort de se savoir soutenue. Renaud, Jérôme, Sophie : si je peux parler 45 minutes d'affilée déguisée en madame presque sans rougir, c'est sans doute grâce à Rires en Folies. Et si ces remerciements commencent à déborder, c'est bien sûr à cause de la propension familiale au discours plutôt qu'à la synthèse. Merci enfin Grand-maman de m'avoir accueillie pendant mes études parisiennes, et ne t'inquiètes pas : je crois que cette thèse n'a mis personne au chômage (sauf moi). Je n'oublie pas non plus les additions, Anne, Céline, J.-B. (ni la multiplication, Alice qui m'a gentiment attendue), ainsi que la famille adverse : merci Félix, Sophie pour votre accueil chaleureux et vos encouragements, et Sacha d'avoir supporté mes humeurs de fin de rédaction.

Introduction et guide de lecture

Ordonnancer consiste à décider quand et comment allouer des ressources (machines, processeurs...) à un ensemble de tâches, en respectant certaines contraintes (capacité, précédence...), afin d'optimiser un ou plusieurs objectif ou indicateurs de performance (temps d'achèvement, retards, coûts de traitement...).

Dans le cas de ressources physiques, si les tâches sont constituées de plusieurs opérations s'effectuant sur différentes ressources, on est amené à se poser la question du transport des objets ou matériaux impliqués entre les ressources affectées. La prise en compte du transport génère alors des contraintes propres, liées à l'utilisation éventuelle de ressources spécifiques pour assurer les déplacements, et à la disposition physique des ressources de traitement : temps de déplacements, capacités et disponibilités des ressources de transport, connexions et accessibilité d'une ressource de traitement depuis une autre... Dans ce travail, nous nous intéressons à deux problèmes associant ordonnancement et transport, dans deux contextes différents : la production manufacturière (Chapitres 1 à 4) et la gestion ferroviaire (Chapitre 5).

Le premier problème concerne les cellules robotisées : il s'agit d'un modèle d'atelier en ligne (flow-shop), où le transport des pièces entre les machines est assuré par un bras robotisé. Les pièces à produire doivent être récupérées à l'entrée de la cellule, être transportées sur chacune des machines pour y être traitées, et enfin déposées à la sortie de la cellule. On cherche à déterminer une programmation cyclique du robot afin d'optimiser le débit de la cellule. En fonction du type de robot utilisé et de la disposition des machines, on peux distinguer deux types de configuration : linéaire et circulaire. Dans le cas de la configuration linéaire, l'entrée et la sortie de la cellule sont séparées, le robot ne peut se rendre de l'une à l'autre sans traverser l'ensemble de la cellule (cas, par exemple, d'un robot circulant sur un rail rectiligne). Dans le cas circulaire, l'entrée et la sortie de la cellules sont jointes ou très proches, et le robot peut faire le tour complet de la cellule (cas de machines disposées en cercle et desservies par un bras robotisé situé au centre) : ceci permet d'économiser du temps de transport, au prix, semble-t-il, d'une plus grande complexité. En effet, les principaux résultats théoriques établis pour la configuration linéaire ne s'appliquent pas à la configuration circulaire, et xi xii

INTRODUCTION ET GUIDE DE LECTURE

celle-ci demeure moins bien comprise. Notre objectif est donc d'en d'améliorer la compréhension théorique ; nous nous intéressons pour cela à un cas particulier, celui des cellules régulières et équilibrées.

Les Chapitres 1 à 4 sont consacrés à ce premier problème. Le Chapitre 1 présente une introduction aux cellules robotisées : nous y exposons les concepts nécessaires à la modélisation d'une cellule robotisée, les principales questions théoriques ainsi qu'un état de l'art sur le sujet ; nous y précisons ensuite le cadre choisi pour les travaux menés dans les chapitres suivants. Le Chapitre 2 présente des outils utilisés par la suite pour l'analyse des programmations (cycles) possibles : sa lecture est recommandée avant d'aborder les Chapitres 3 et 4. Ces deux chapitres abordent, dans le cas des cellules robotisées circulaires régulières et équilibrées, deux problèmes théoriques classiques (introduits dans le Chapitre 1) concernant les cycles de production d'une pièce exactement (1-cycles) : la conjecture des 1cycles et le problème des meilleurs 1-cycles. Dans le Chapitre 3 nous établissons certaines propriétés des cycles performants, qui nous permettent de fermer le problème du meilleur 1-cycle pour des cellules de petite taille (jusqu'à 8 machines) ; nous donnons également un contre-exemple à la conjecture des 1-cycles pour 6machines. Dans le Chapitre 4 nous nous intéressons aux cellules arbitrairement grandes (plus de 8 machines), et cherchons à dégager des propriétés structurelles des programmations dominantes. Sans trop en dévoiler, disons qu'on y parle de vagues -et qu'il vaut mieux bien s'amarrer.

Le Chapitre 5 est consacré au second problème, concernant la gestion ferroviaire -il peut donc être lu indépendamment des précédents. Il s'agit d'un problème industriel présenté dans le cadre du Challenge EURO/ROADEF 2014 ; ce chapitre présente notre contribution. On s'intéresse à la gestion des trains au sein d'une gare. Une gare est constituée de ressources de différents types : ressources de traitement (plate-forme pour le traitement des arrivées et des départs, ressources de maintenance), de stockage (parkings et voies de garage) et enfin ressources de transition (aiguillages). Le déplacement des trains sur et entre ces ressources obéit à des contraintes liées aux ressources elles-mêmes (capacité, temps de parcours), à leur disposition (adjacence et connexité des ressources), et aux autres trains (collisions et blocages). La formulation originale mêle un grand nombre de sous-problèmes (affectation des départs et arrivées, affectation des plateformes, routage, maintenance des trains, jonctions et disjonction des rames), contraintes et objectifs (nombre de départs satisfaits, coûts de performance et d'occupation des ressources, de maintenances...) reflétant la complexité du problème en pratique. Nous simplifions la formulation originale afin de nous concentrer sur le problème du routage, pour lequel nous proposons un algorithme par propagation de contraintes multi-intervalles, suffisamment souple pour permettre, couplé à un algorithme d'affectation glouton, d'obtenir une solution réalisable.

Chapter 1 An introduction to robotic cells

Scheduling consists in deciding how and when to allocate available resources (servers) to a set of tasks (or jobs) to be performed, subject to certain constraints (capacity, precedence between tasks...) in order to optimize one or more objective function (total completion time, cycle time, lateness, cost...). In the context of manufacturing production, the tasks may be parts to be produced, and the resources the machines on which the processing takes place.

Classical scheduling theory distinguishes between scheduling problems on parallel servers, and on dedicated servers. The second class is itself divided into 3 categories: job-shops, open-shops and flow-shops. Several operations have to be performed on a job: in a flow-shop, the operations sequence is fixed and is the same for all the jobs; in a job-shop, it is still fixed but job-dependent; in an open-shop, the operations sequence is up to the scheduler to decide. In terms of manufacturing production, in a flow-shop, all parts are processed on the machines in the same order. The minimization of the makespan in a flow-shop with 3 machines or more is NP-Hard, with and without buffer between machines (Garey et al., 1976, Hall andSriskandarajah, 1996). For 2 machines, it is polynomial both for the case with unlimited buffering capacity [START_REF] Johnson | Optimal two-and three-stage production schedules with setup times included[END_REF] and the no-buffer case [START_REF] Gilmore | Sequencing a one state-variable machine: A solvable case of the traveling salesman problem[END_REF]Gomory, 1964, Hall andSriskandarajah, 1996). However, it is NP-hard when the buffer is of limited non-zero capacity (Papadimitriou and Kanellakis, 1980)). [START_REF] Pinedo | Scheduling Theory, Algorithms, and Systems[END_REF] and [START_REF] Leung | Handbook of Scheduling: Algorithms, Models, and Performance Analysis[END_REF] are, for instance, reference books on classical scheduling theory and algorithms; the web page http://www2.informatik.uni-osnabrueck.de/knust/class/ maintains an inventory of classical scheduling problems and their complexity status.

However, classical scheduling theory (and, specifically, the classical flow-shop model) does not fully account for modern manufacturing systems. Additionally to the processing machines, auxiliary resources must be considered for example human operators in the case of semi-automated systems, and handling resources such as automated guided vehicles or mobile robots.

CHAPTER 1. AN INTRODUCTION TO ROBOTIC CELLS

Section 1.1 presents robotic cells, one of the models which take into account handling resources (namely handling robots). Section 1.2, Section 1.3 and Section 1.4 present a literature review on three types of robotic cells: with no-wait condition, with unbounded waiting times, and with flexibility. Section 1.5 states the scope of our work and the notations used throughout this document.

Robotic cells: generalities

A robotic cell consists of a flow-shop where the m machines M 1 , . . . , M m are served by one or several robotic arms. The cell also contains an input buffer, where parts to be processed are usually supposed to be available in infinite quantity, and an output buffer of similarly infinite capacity where fully processed parts are to be transferred. The input and output buffer are generally represented by two auxiliary machines M 0 = In and M m+1 = Out. Figure 1.1 shows two examples of threemachine cells with two different layouts, semi-circular (where the input and input buffers are separated) and circular (where the input and output buffers coincide). Each part must be taken from the input buffer, transferred successively on each machine (M 1 , then M 2 , etc. until M m ) to complete their processing, then it is transferred to the output buffer.

The model was first introduced by [START_REF] Asfahl | Robots and manufacturing automation[END_REF] to describe a production cell for truck differentials, while [START_REF] Sethi | Sequencing of parts and robot moves in a robotic cell[END_REF] provided the first formal study for small dimension cells.

ROBOTIC CELLS: GENERALITIES

In the general case, where multiple part types must be produced, two types of decisions must be made: sequencing the parts, and scheduling the robot moves. In the case where only one type of part is to be produced, there is no decision to make for the part sequencing: the problem reduces to finding an optimal robot move schedule.

In the classical model, the cell is equipped with a single robot able to handle only one part at a time (single gripper), the machines are specialized and can only carry out one type of operation (non-flexibility), and machines are without buffer facility. In this set-up, a blocking constraint is enforced: the robot has to be empty in order to pick-up a part, and any machine (except for the input and output buffers) has to be unloaded before it can be loaded again. [START_REF] Hall | A survey of machine scheduling problems with blocking and no-wait in process[END_REF] presents a survey of flow-shop problems with blocking constraints.

Other models allow to relax this blocking constraint, by using different types of robots (multi-gripper robot, robot with swapping ability), or adding machine buffers.

The following two sections describe the different models for processing policies and travel policies in robotic cells. They are largely extracted from the survey [START_REF] Brauner | Identical part production in cyclic robotic cells: Concepts, overview and open questions[END_REF].

Processing and pick-up criterion

The processing starts as soon as a part is loaded on a machine. The processing time represents the minimum time a part must remain on a machine. If all parts are different, p ij denotes the processing time of part j on machine M i . If one wants to produce one large batch of identical parts, the processing times of the parts on machine M i are p i = p ij . In the balanced case1 , all processing times are equal, i.e., p ij = p j , or, for the production of identical parts, p i = p for all i.

Once the part is finished, two policies may apply. In the no-wait case, the part must be removed immediately from the machine and transferred to the following machine. In the unbounded case (also denoted as free pick-up), the part can remain on the machine waiting for the robot.

A classical extension of those two cases is the so-called Hoist Scheduling Problem (HSP); in this case, the processing time is described by an interval, and the no-wait policy applies. This means that the time part j may remain on machine M i lays in the specified interval. This applies to chemical treatments were the machines correspond to chemical baths. The HSP is NP-hard even for identical parts and very simple (additive, as defined in the next section) configurations of cells (Crama and van de Klundert, 1997b).

CHAPTER 1. AN INTRODUCTION TO ROBOTIC CELLS

Loading and unloading times

During the loading of a part onto a machine from the robot or the unloading of a part from a machine onto the robot, both the machine and the robot are occupied. The time necessary to perform these operation is often assumed to be part-and machine-independant, and denoted by . [START_REF] Lehoux-Lebacque | Théories et applications en ordonnancement : contraintes de ressources et tâches agrégées en catégories[END_REF] showed that in bufferless robotic cells, loading and unloading times can be dismissed without loss of generality.

Note however that the problem of robotic cells with sequence-dependent loading times has been investigated recently (see e.g. [START_REF] Majumder | A new cuckoo search algorithm for 2-machine robotic cell scheduling problem with sequence-dependent setup times[END_REF]Laha, 2016, Zarandi et al., 2013).

Travel metric and layout

There are different classical metrics for the travel times of the robot depending on the physical configuration of the cell and on the characteristics of the robot. We denote by δ i,j , the travel time of the robot (empty or loaded) from M i to M j . It is natural, and in practice desirable, to assume that the travel times satisfy the classical properties of a metric:

• the travel time from a machine to itself is zero, that is, δ i,i = 0;

• the travel times satisfy the triangle inequality, that is, δ i,k + δ k,j ≥ δ i,j for all i, k and j;

• The travel times are symmetric, that is δ i,j = δ j,i for all i and j.

Travel times verifying those three assumptions are called general (or sometimes "euclidean", e.g. in [START_REF] Dawande | Sequencing and scheduling in robotic cells: Recent developments[END_REF]). Special configurations of cells have been studied in the literature.

For additive times, to travel between distant machines, the robot passes through all intermediate machines and its speed is constant. This metric is the most popular since, in practice, it is applicable if the machines are on a circle or on a line and if the cell is dense (the robot does not have time to speed up between distant machines). In this case, one has the triangle equality δ i,j = δ i,k + δ k,j = j-1 k=i δ k,k+1 for any i ≤ k < j. By symmetry, this also defines δ i,j for i > j. Some authors (e.g. [START_REF] Hall | Scheduling in robotic cells: Classification, two and three machine cells[END_REF], [START_REF] Logendran | Sequencing of robot activities and parts in two-machine robotic cells[END_REF]) consider an extension of this case having a constant gain γ when travelling between distant machines, i.e., δ i,j = j-1 k=i δ k,k+1 -(j -i -1)γ for i < j. We assume γ = 0. In the regular case, the machines are equidistant and we denote δ i,i+1 = δ. This constraint can be added to the additive constraint (as in the seminal paper by [START_REF] Sethi | Sequencing of parts and robot moves in a robotic cell[END_REF]).

For constant travel times (introduced in Dawande et al. ( 2002)), δ is the time for the robot to travel between any two distinct machines M i and M j : δ i,j = δ.

Finally, depending on the type of robot used, the machines and the input and output stations can be disposed in several ways. Two main configurations are used: on the one hand, linear or semi-circular layouts (Figure 1.1a), where the input and output buffers are separated and located respectively at each end of the line (Crama and van de Klundert, 1997a), and on the other hand, circular layouts (Figure 1.1b), where the machines are arranged in a circle, with the input and output buffers either occupying the same spot (M 0 = M m+1 ), or very close [START_REF] Jung | Approximations to optimal sequences in single-gripper and dual-gripper robotic cells with circular layouts[END_REF][START_REF] Rajapakshe | Quantifying the impact of layout on productivity: An analysis from robotic-cell manufacturing[END_REF]. In this case, the robot chooses the shortest path along the circle formed by the machines. Then, the travel times verify

δ i,j = min( j-1 k=i δ k,k+1 , m k=j δ k,k+1 + i-1 k=0 δ k,k+1
) for any i < j. This can be combined with the additive and regular constraints.

Throughput optimisation and cyclic scheduling

A possible optimization goal is to minimize the makespan of a lot (total completion time of the lot). Makespan optimization in robotic flow-shops is addressed for example by [START_REF] Carlier | An optimization-based heuristic for the robotic cell problem[END_REF], [START_REF] Hurink | Makespan minimization for flow-shop problems with transportation times and a single robot[END_REF], [START_REF] Kise | On an automated two-machine flowshop scheduling problem with infinite buffer[END_REF], [START_REF] Soukhal | Resolution of a scheduling problem in a flowshop robotic cell[END_REF], [START_REF] Yang | Flexible robotic manufacturing cell scheduling problem with multiple robots[END_REF].

However, for large-scale production, the maximization of the throughput rate of the cell, with infinite horizon, may be considered as the objective. In this context, it seems operationally relevant to prefer a cyclic programmation. This means that the robot repeats indefinitely the same move sequence, each iteration leaving the cell in the same state, with the same machines loaded, the same machines empty and the robot in the same place. Indeed, cyclic programmations are dominant (Dawande et al., 2005a), which means that, for any set of parameters, there always exists an optimal programmation which is cyclic. The elementary sequence is called a cycle.

Robot move sequences (and thus cycles) can be described using the concept of activities, defined by [START_REF] Sethi | Sequencing of parts and robot moves in a robotic cell[END_REF]. Activities are elementary robot moves defined as such: for i ∈ {0 . . . m}, activity A i refers to the following sequence of events:

1. The robot unloads a part from M i ; 2. The robot travels to M i+1 ; 3. The robot loads the part onto M i+1 .

In the classical model, a cycle is entirely specified by a sequence of activity. Cycles which produce exactly k parts are called k-cycles (or k unit cycles). Thus, 1-cycles are particular cycles which produce one part exactly: during one iteration, exactly one part enters the cell at M 0 , and one processed part leaves the cell at M m+1 .

Maximizing the throughput of the cell equates to minimizing its cycle time, or more accurately, its cycle time in regards to the number of part produced by one iteration (k for a k-cycle). The cycle time might not be the same for each repetition of the cycle, therefore we consider the long run average cycle time. More detail on the computation of the long run average cycle time and an example can be found in Chapter 2, page 32. [START_REF] Sethi | Sequencing of parts and robot moves in a robotic cell[END_REF] establish that in an m-machine cell, the number of 1-cycles is m!. Using the concept of activity, all the 1-cycles can be obtained by considering the permutations of the m activities A 1 . . . A m [START_REF] Sethi | Sequencing of parts and robot moves in a robotic cell[END_REF]. Formally, 1-cycles are of the form π = A 0 , A i 1 , A i 2 . . . A im where (i 1 , i 2 ...i m ) is a permutation of {1, 2...m}. More generally, k-cycles are characterized as the sequences of activity such that each activity occurs exactly k times, and between two consecutive occurrences (in a cyclic sense) of an activity A i with i / ∈ 0, m + 1, there is exactly one occurrence of the activities A i-1 and A i+1 (Crama and van de Klundert, 1999). Among 1-cycles, two common (and intuitive) permutations are the identity (or uphill) permutation

A 0 A 1 A 2 . . . A m ,

and the downhill permutation

A 0 A m A m-1 . . . A 1 .
They will be described in more detail in Chapter 2.

One-cycles are easy to describe and enumerate using the concept of activities, as they are exactly the permutations of the m activities [START_REF] Sethi | Sequencing of parts and robot moves in a robotic cell[END_REF]. They are also easier to implement operationally. As a consequence, it is convenient to restrict the possible move sequences to 1-cycles only (this problem is known as the best 1-cycle problem). But does this allow to find an optimal sequence? [START_REF] Sethi | Sequencing of parts and robot moves in a robotic cell[END_REF] formulate the 1-cycle conjecture: [START_REF] Sethi | Sequencing of parts and robot moves in a robotic cell[END_REF]). The set of 1-cycles is dominant (for any set of parameters, there always exists a 1-cycle which is optimal).

Conjecture 1.1 (1-cycle conjecture
This conjecture has been settled in some cases, which we expose later in Section 1.2 and Section 1.3.

For the case where multiple part types are to be produced, the cyclic production of a Minimal Part Set (MPS) is considered. A MPS is defined as a minimum cardinality set such that the relative proportion of each type of part is the same as in the overall demand [START_REF] Dawande | Throughput Optimization in Robotic Cells[END_REF]. A MPS-cycle is a cycle during which all the parts in a MPS are produced: all parts in the MPS enter the cell and all parts in the MPS exits the cell. The idea of 1-cycles can be extended to multiple part type production by considering Concatenated Robot Move (CRM) cycles: CRM-cycles are MPS-cycles consisting of the repetition of a same 1-cyclic sequence as many times as there are parts in the MPS.

When considering relations between cycles, we will use these meanings of "optimality" and "dominance":

• A cycle c is optimal for a given instance (or set of instances) if it performs at least as well as any possible cycle for this instance (or for each instance of the set).

• A cycle c is optimal within a set of cycles S for a given instance or set of instances, if it performs at least as well as any cycle in S on this instance or set of instances (in other words, it is optimal for the problem restricted to the cycles in S).

• A set of cycles S is dominant if, for every possible instance, an optimal cycle can be found in S.

• A set of cycles S is dominant over a set of cycles T , or S dominates T , if for every possible instance, an optimal cycle within T can be found in S.

• A cycle c dominates a cycle g (or g is dominated by c) for a given set of instances, if c performs at least as well as g for all these instances.

• A cycle c is non-dominated by a set of cycle S on a given set of instances if there exist an instance within this set for which c strictly outperforms every cycle in S.

Several synthetic efforts provide useful insights about cycling scheduling in robotic cells. Levner In the following, we present an overview of the existing work on robotic cells with no-wait condition (Section 1.2), cells with unbounded waiting times (freepickup) (Section 1.3), and finally, cells with flexibility (Section 1.4). In this last case, the allocation of operations to machines has to be decided, jointly with the robot move sequence and, if relevant, the part sequencing. We do not develop the more complex case of cells with interval or time window condition (HSP). Remember that in this configuration, the problem is NP-hard even in simple cases (Crama and van de Klundert, 1997b); existing literature focuses on Mixed Integer Programming (MIP) formulation, branch and bound and heuristic algorithms (see e.g. [START_REF] Kats | Minimizing the cycle time of multipleproduct processing networks with a fixed operation sequence, setups, and timewindow constraints[END_REF][START_REF] Phillips | Mathematical programming solution of a hoist scheduling program[END_REF][START_REF] Zhou | A mixed integer programming approach for multi-cyclic robotic flowshop scheduling with time window constraints[END_REF]. Unless otherwise CHAPTER 1. AN INTRODUCTION TO ROBOTIC CELLS specified, the work presented here deals with cyclic optimization. We also do not develop the case of hybrid robotic flow-shops with parallel machines at each stage ( (see e.g [START_REF] Elmi | Scheduling multiple parts in hybrid flow shop robotic cells served by a single robot[END_REF][START_REF] Geismar | Robotic cells with parallel machines: Throughput maximization in constant travel-time cells[END_REF][START_REF] Soukhal | Ordonnancement simultané des moyens de transformation et de transport[END_REF][START_REF] Zabihzadeh | Two meta-heuristic algorithms for flexible flow shop scheduling problem with robotic transportation and release time[END_REF].

No-Wait condition

Production constraints may require for the parts to be picked up immediately after the end of their processing [START_REF] Levner | An improved algorithm for cyclic flowshop scheduling in a robotic cell[END_REF]). This classical scheduling constraint can model, for example, the case where the processing stations are chemical baths which must last a precise amount of time [START_REF] Song | An algorithm for scheduling a chemical processing tank line[END_REF]). It is referred to as no-wait condition, constant processing times or zero-width processing time windows. Note that for a given instance and move cycle, there might not exist a schedule satisfying the no-wait constraint: contrary to the unbounded case, feasibility must be considered. In the case of identical part production, a schedule is completely specified by the input time of the parts from which the robot move sequence can be deduced [START_REF] Bibliography Agnetis | Scheduling no-wait robotic cells with two and three machines[END_REF].

This section presents major results on no-wait robotic cells. All the models considered have a linear layout (where the input and output buffer are separated, as in Figure 1.1a), although results given for 2-and 3-machine cells can also be applied to circular layout cells. [START_REF] Bibliography Agnetis | Scheduling no-wait robotic cells with two and three machines[END_REF] considers general production cycles for 2-machine cells producing multiple part-types, and 2-or 3-machine cells producing identical part types. Travel times are assumed to satisfy the triangle inequality. For identical part production, the author notes that the 2-machine no-wait case is similar to the 2-machine case with unbounded waiting times solved by [START_REF] Sethi | Sequencing of parts and robot moves in a robotic cell[END_REF]. For the 3-machine case, [START_REF] Bibliography Agnetis | Scheduling no-wait robotic cells with two and three machines[END_REF] shows that the optimal cycle is either a 1-cycle or a 2-cycle and he provides an algorithm to compute it in constant time, using a forbidden region approach which is not easily extensible to a higher number of machines. The author gives an example of a non-dominated 2-cycle thus proving false the 1-cycle conjecture.

Solved and open problems for small-dimension cells

For multiple part-types production, [START_REF] Bibliography Agnetis | Scheduling no-wait robotic cells with two and three machines[END_REF] shows that the 2-machine case may be reduced to a classical 2-machine no-wait flowshop problem and hence solved in O(n log n) using the Gilmore-Gomory algorithm [START_REF] Gilmore | Sequencing a one state-variable machine: A solvable case of the traveling salesman problem[END_REF] for special TSP cases, while the NP-hardness of the problem for 3 machines and more ensues of the NP-hardness of the corresponding classical no-wait flowshop problem [START_REF] Röck | The three-machine no-wait flow shop is np-complete[END_REF].

NO-WAIT CONDITION

9

Subsequently, [START_REF] Agnetis | Part sequencing in three machine no-wait robotic cells[END_REF] focus on multiple part-types production on 3-machine cells and consider only repetitions of the same 1-cyclic sequences (defined as CRM cycles by [START_REF] Sriskandarajah | Scheduling multiple parts in a robotic cell served by a dual-gripper robot[END_REF]). For each of the six possible cycles, they study both the feasibility and optimization aspects of the part sequencing problem. For two of these six cycles, both problems are polynomially solvable. For two others, even the feasibility problem is shown to be unary NP-complete (this is proven using a reduction from Numerical Matching with Target Sum). For the last two, the feasibility problem equates to a classical 2-machine flowshop problem and can thus be solved by Gilmore-Gomory algorithm, but the optimization problem is a special case of the Traveling Salesman Problem (TSP) which complexity status is still open.

Identical part production

In this section, we present works addressing identical part production in cells of arbitrary dimension, whether restricted to 1-cyclic schedules or more general 2cyclic or k-cyclic schedules. [START_REF] Levner | An improved algorithm for cyclic flowshop scheduling in a robotic cell[END_REF] and [START_REF] Kats | A strongly polynomial algorithm for no-wait cyclic robotic flowshop scheduling[END_REF] consider identical part production in m-machine cells, with general travel-times, and provide polynomial algorithms for finding the best 1-cycle in the no-wait case. [START_REF] Kats | A strongly polynomial algorithm for no-wait cyclic robotic flowshop scheduling[END_REF] provide an algorithm based on a forbidden intervals approach, running in O(m 4 log m), which also solves the more general problem of reentrant robotic cells (where the number of operations to be performed is greater than the number of machines, meaning that the part has to reenter the cell to complete its processing). [START_REF] Levner | An improved algorithm for cyclic flowshop scheduling in a robotic cell[END_REF] give an improved algorithm for the classical model, finding the best 1-cycle in O(m 3 log m).

1-cycles

As 1-cycles are generally not optimal (as noted e.g. by [START_REF] Bibliography Agnetis | Scheduling no-wait robotic cells with two and three machines[END_REF]), subsequent works focus on multi-cyclic schedules. [START_REF] Levner | An improved algorithm for cyclic flowshop scheduling in a robotic cell[END_REF]. The polynomiality of finding an optimal 2-cycle had been conjectured by [START_REF] Levner | A geometric algorithm for finding two-unit cyclic schedules in no-wait robotic flowshop[END_REF]. [START_REF] Che | A polynomial algorithm for 2-degree cyclic robot scheduling[END_REF] derive a O(m 8 log m) algorithm, subsequently improved by [START_REF] Chu | A faster polynomial algorithm for 2-cyclic robotic scheduling[END_REF] to O(m 5 log m). The authors' numerical experiments show that considering 2-cycles leads to a significant improvement of the optimal cycle time compared to considering only 1-cycles, which increases with the number of machines, and decreases when the time necessary to perform the robot CHAPTER 1. AN INTRODUCTION TO ROBOTIC CELLS moves increases. With m = 10 fixed, the experiments show that the improvement is smaller for very small ( d i,i+1 < 2 or very large d i,i+1 > 7 ) travel times. [START_REF] Kats | A polynomial algorithm for 2-cyclic robotic scheduling: A non-Euclidean case[END_REF] extend this results to the non-euclidean case where the travel times don't satisfy the triangle inequality. [START_REF] Kats | Multiple-part cyclic hoist scheduling using a sieve method[END_REF] study cycles of arbitrary degree but only instances with integer input data, and integer schedules. They show that the number of integer solutions for a given degree k is finite, and provide a sieve procedure performing an exhaustive search in order to output an optimal k cycle. The algorithm runs in O(km 3 m k ) and is therefore polynomial in m for a given k, but exponential in k.

2-cycles

Che et al. (2003) consider 2-cyclic robot move sequences in conditions similar to

k-cycles

Agnetis' conjecture

As stated in section 1.2.1, [START_REF] Bibliography Agnetis | Scheduling no-wait robotic cells with two and three machines[END_REF] proves that the optimal cycle for a 3machine cells is either a 1-cycle or a 2-cycle. The author conjectures that this may be extended to an arbitrary number of machines; formally, that an optimal cycle can be found within the set of k-cycles with k ≤ (m -1). [START_REF] Mangione | Ordonnancement des ateliers de traitement de surface pour une production cyclique et mono-produit[END_REF] explores the validity of this conjecture for the special case of regular balanced cells and proves it is true for 4-machine cells, by studying possible configurations of the cells state graph. For m-machine cells, [START_REF] Mangione | Optimal cycles for the robotic balanced no-wait flow shop[END_REF] states a conjecture on the structure of optimal cycles which, if proven, confirms Agnetis' conjecture, and proves it for some values of k and of the processing time p. Pavlov (2013) appears to prove the remaining cases for 5-machine cells2 .

To this day, Agnetis' conjecture is still open for no-wait robotic cells, even in the regular balanced case.

Multi-robot cells

More recent works consider cells with several robots. Robots can evolve on parallel tracks or on a single track. In the latter case, collision-avoidance constraints are added to the problem, while the former might be reduced to an extension of the single-robot problem coupled with an assignment problem. [START_REF] Kats | Cycle scheduling in a robotic production line[END_REF] extend the results from [START_REF] Kats | A strongly polynomial algorithm for no-wait cyclic robotic flowshop scheduling[END_REF] to the problem with several robots on parallel tracks, with robot-dependent travel-times, providing a O(m 3 log m) algorithm for finding the best 1-cycle.

In the single track case, collision-avoidance constraints change the structure of the problem. Considering identical parts, identical robots and 1-cyclic schedules only, [START_REF] Leung | An efficient algorithm for multi-hoist cyclic scheduling with fixed processing times[END_REF] compute the minimum number of robots necessary to achieve a given cycle time in O(m 2 ). Their algorithm operates by defining a partial order on robot moves based on the notion of conflicting moves, then finding the longest chain in the corresponding graph. Based on this, they suggest an algorithm for computing the minimum number of robots necessary to achieve any cycle time in O(m 5 ), and note that it is not strictly decreasing with the cycle time. Assuming similar hypothesis, [START_REF] Chu | Optimal scheduling of material handling devices in a PCB production line: problem formulation and a polynomial algorithm[END_REF] give a mathematical formulation of the problem and devise an algorithm which finds the best 1-cycle for a given number of robots R in O(m 6 R). [START_REF] Liu | An efficient optimal solution to the two-hoist no-wait cyclic scheduling problem[END_REF] Multi-cyclic production with several robots on parallel tracks are studied by Che andChu (2005, 2009), respectively with 2 robots and an arbitrary number of robots. The proposed algorithms run in polynomial time in m for a given degree k, but are exponential in k.

The case of several robots on a single track is addressed by [START_REF] Che | A polynomial algorithm for multi-robot 2-cyclic scheduling in a no-wait robotic cell[END_REF], who propose an algorithm for finding the best 2-cycle in O(m 7 ).

Unbounded waiting times

In this section we consider the case where the parts' pickup is not submitted to a time-window constraint. This is referred to as unbounded waiting times or free pickup criterion. Contrary to the no-wait case, once processed, a part might stay on a machine until the robot is free to pick it up. If there are no machine buffers, the machine is blocked until the part has been unloaded and transferred to the next machine. Models including machine buffers, robot buffers or robots with several gripper allow to release this constraint increasing the complexity of the problem. In the case of multiple part production, the problems to solve are the part sequencing and the robot moves scheduling. In the case of identical part production, contrary to the no-wait case, a schedule is not entirely specified by the input times of the parts: the robot moves sequence has to be determined. [START_REF] Sethi | Sequencing of parts and robot moves in a robotic cell[END_REF], [START_REF] Hall | Scheduling in robotic cells: Classification, two and three machine cells[END_REF] and [START_REF] Hall | Scheduling in robotic cells: Complexity and steady state analysis[END_REF] consider additive semicircular 2-and 3-machine cells with linear layout. The identical part production problem on 2-machine cells is solved by [START_REF] Sethi | Sequencing of parts and robot moves in a robotic cell[END_REF]: the authors show that the optimal robot move sequence is one of the two possible 1-cycles A 0 A 1 A 2 or A 0 A 2 A 1 . The proof relies on the fact that while the robot is transferring a part between the 2 machines, both machines are empty, and this does not depend on the configuration of the cell. It is therefore also valid for the circular case. For production of multiple parts on 2-machine cells, [START_REF] Sethi | Sequencing of parts and robot moves in a robotic cell[END_REF] study the part sequencing problem when the robot move sequence is set to either one of the two possible CRM sequence: the repetition of A 0 A 1 A 2 , or the repetition of A 0 A 2 A 1 , and show it can be solved using the Gilmore and Gomory algorithm [START_REF] Gilmore | Sequencing a one state-variable machine: A solvable case of the traveling salesman problem[END_REF]. However, [START_REF] Hall | Scheduling in robotic cells: Classification, two and three machine cells[END_REF] show that CRM cycles are not generally optimal, by giving a counter-example for the 2-machine case. In this case, finding an optimal robot move sequence consist in deciding which part are to be produced under which of the two possible sequence, and how to switch from one to another. The authors give a O(m 4 ) algorithm that outputs jointly the robot move schedule and the part sequencing leading to the optimal cycle time, using the Gilmore and Gomory algorithm as a subroutine, improved later on by [START_REF] Aneja | Scheduling of parts and robot activities in a two machine robotic cell[END_REF], who provide a O(m log m) algorithm. [START_REF] Sethi | Sequencing of parts and robot moves in a robotic cell[END_REF] define the 6 possible 1-cycles for 3-machine cells producing identical parts, derive their cycle time and provide a decision tree for determining the best one. However, for multiple part-type production, [START_REF] Hall | Scheduling in robotic cells: Complexity and steady state analysis[END_REF] show that for 2 of the 6 possible CRM-cycle, the part sequencing problem is unary NPcomplete, as well as the general part sequencing problem not restricted to any robot cycle (even for the regular case). For these two cycles, [START_REF] Chen | Sequencing of parts in robotic cells[END_REF] propose a branch-and bound algorithm (extensible to m machines), using the Gilmore and Gomory algorithm to provide a lower bound. [START_REF] Hall | Scheduling in robotic cells: Classification, two and three machine cells[END_REF] show that for the 4 other CRM-sequences the part sequencing problem is polynomially solvable and deduce special cases for which the best 1-cycle problem is polynomially solvable. [START_REF] Kamoun | Scheduling in robotic cells: Heuristics and cell design[END_REF] propose simple heuristics for some of the other cases. More recently, [START_REF] Zahrouni | Sequencing and scheduling in a threemachine robotic cell[END_REF] propose a constructive heuristic for the three-machine case not restricted to CRM cycles which outperform the latter in most of the tested instances. [START_REF] Kamalabadi | A new solution for the cyclic multiple-part type three-machine robotic cell problem based on the particle swarm meta-heuristic[END_REF] propose a metaheuristic approach using a swarm particle optimization algorithm and a formulation of the problem based on Petri nets.

Small scale cells

Steiner and Xue (2005) extend the results of [START_REF] Sethi | Sequencing of parts and robot moves in a robotic cell[END_REF] and [START_REF] Hall | Scheduling in robotic cells: Classification, two and three machine cells[END_REF] to the model of reentrant regular cells (as described for example in (Middendorf and Timkovsky, 2002)), showing that CRM cycle are not generally optimal for 2-machine reentrant cells, and that in 3-machine loop-reentrant cell (where the processing must be finalized on the first machine), the part sequencing problem is strongly NP-hard for two of the possible CRM-cycles, and for the general problem not restricted to any robot move sequence.

Multiple part types

As for cyclic production of multiple part types, [START_REF] Sriskandarajah | Scheduling large robotic cells without buffers[END_REF] extend the complexity results of [START_REF] Hall | Scheduling in robotic cells: Classification, two and three machine cells[END_REF] to m machine cells. The authors classify the m! possible CRM-cycles into four categories according to the structure and complexity of the associated part scheduling problem: trivial, polynomially solvable modeled as a special case of TSP, unary NP-hard modeled as a TSP, unary NP-hard without TSP structure. They show that only 2m -2 of the m! possible cycle fall in the first two categories, while for all the remaining CRMcycles, the part scheduling problem in NP-hard. [START_REF] Dawande | Throughput Optimization in Robotic Cells[END_REF] explains how to extend the heuristic proposed in [START_REF] Kamoun | Scheduling in robotic cells: Heuristics and cell design[END_REF] to the m-machine case.

Makespan optimization

Other works consider non-cyclic production, with the makespan of a given set of part as the objective function. [START_REF] Soukhal | Resolution of a scheduling problem in a flowshop robotic cell[END_REF] propose a Mixed Integer Linear Programming (MILP) model (for additive travel times); they derive a lower bound and propose a genetic algorithm. [START_REF] Carlier | An optimization-based heuristic for the robotic cell problem[END_REF] propose a decomposition of the problem into a flowshop problem (integrating transportation times and blocking problem) and a single machine problem with precedence constraints, both of which are solved using a branch and bound procedure. They also propose a genetic algorithm. [START_REF] Kharbeche | Exact methods for the robotic cell problem[END_REF] give a MILP formulation for the problem with general (euclidean) travel time, and new lower bounds. They describe a branch and bound algorithm, using a genetic algorithm to provide an initial upper bound.

Identical part production

In this section we present the works addressing identical part production in classical (single-gripper, bufferless) robotic cells. [START_REF] Brauner | Complexity of one-cycle robotic flow-shops[END_REF] show, by a reduction from a TSP problem, that with general (euclidean) travel time, the problem is strongly NP-hard. Geismar et al. (2005b) provides a 4-approximation. More recently, a metaheuristic approach is presented by [START_REF] Elmi | Multi-degree cyclic flow shop robotic cell scheduling problem: Ant colony optimization[END_REF] for solving the problem with multiple robots.

In the following, we expose the results concerning, on the one hand, cells with constant and linear additive travel time (which are quite similar), and on the other hand, cells with circular additive time (as in Figure 1.1b).

CHAPTER 1. AN INTRODUCTION TO ROBOTIC CELLS

Constant travel times and linear layout with additive travel times

Finding a best 1-cycle is proven to be polynomial in constant and linear additive cells respectively by [START_REF] Dawande | On throughput maximization in constant travel-time robotic cells[END_REF] and Crama and van de Klundert (1997a). Crama and van de Klundert (1997a) result relies on the dominance of pyramidal permutation over 1-cycles. A 1-cycle is said to be pyramidal if its sequence of activities, starting with A 0 , is strictly increasing, then strictly decreasing. Formally, a 1-cycle π = (A 0 , A i 1 , A i 2 . . . A im ) where (i 1 , i 2 ...i m ) is a permutation of {1, 2...m}, is pyramidal if there is a p such that 1 ≤ i 1 < . . . < i p = m and m > i p+1 > . . . > i m ≥ 1. Crama and van de Klundert (1997a) prove their dominance over other permutation and deduce a O(m 3 ) algorithm for finding the best 1-cycle.

We have seen that, for the production of multiple part types, CRM-sequences are not dominant even for 2 machines [START_REF] Hall | Scheduling in robotic cells: Classification, two and three machine cells[END_REF]). However, in the case of production of identical parts, [START_REF] Hall | Scheduling in robotic cells: Classification, two and three machine cells[END_REF] show that in 3-machine regular cells, 2-cyclic sequences are dominated by 1-cycles. This is extended to k-cycles by Crama and van de Klundert (1999), proving the 1-cycle conjecture for 3-machine additive cells. [START_REF] Brauner | On a conjecture about robotic cells: new simplified proof for the three-machine case[END_REF] propose a shorter and simpler proof of this result. However, the conjecture was proven false for 4-machines by [START_REF] Brauner | Cycles and permutations in robotic cells[END_REF], who provide a 3-cycle which performs better than any 1-cycle on a specified instance in a regular additive 4-machine cell. The conjecture formulated by [START_REF] Bibliography Agnetis | Scheduling no-wait robotic cells with two and three machines[END_REF] (for no-wait cells), stating that an optimal cycle can be found within the set of k-cycles with k ≤ m -1 was also proven false in 4-machine regular additive and constant cells by [START_REF] Brauner | A note on agnetis' conjecture for classical robotic cells[END_REF]. In the case of regular additive balanced cells, however, the 1-cycle conjecture is proven valid until 6 machines by [START_REF] Brauner | Cycles and permutations in robotic cells[END_REF]; [START_REF] Brauner | Identical part production in cyclic robotic cells: Concepts, overview and open questions[END_REF] claims the proof can be extended for m ≤ 15.

Thus, 1-cycles are generally not dominant, and the complexity of finding the best k-cycle with k ≥ 2 is still open, both in the constant and additive cases. However [START_REF] Geismar | Approximations to optimal k-unit cycles for single-gripper and dual-gripper robotic cells[END_REF][START_REF] Geismar | Approximation algorithms for k-unit cyclic solutions in robotic cells[END_REF][START_REF] Geismar | A (10/7)approximation algorithm for an optimum cyclic solution in additive travel-time robotic cells[END_REF] provide bounds on the performance of 1-cycles over k-cycles (and thus approximation algorithm with guaranteed performance). [START_REF] Geismar | Approximation algorithms for k-unit cyclic solutions in robotic cells[END_REF] expose how to construct in linear time a 1-cycle with a performance ratio of 1.5, both in the constant and regular additive case. [START_REF] Geismar | Approximations to optimal k-unit cycles for single-gripper and dual-gripper robotic cells[END_REF][START_REF] Geismar | A (10/7)approximation algorithm for an optimum cyclic solution in additive travel-time robotic cells[END_REF] improve this ratio respectively to 10 7 in the regular additive case, and 9 7 in the constant case, both ratios being tight. Finally, the complexity status of the best 1-cycle problem in the balanced case (where all processing times are equal) is not settled by the algorithm proposed by Crama and van de Klundert (1997a). Indeed, in this case, the input consists in only 3 or 4 numbers: the number of machines m, the processing times p, the travel time between consecutive machines (for the regular additive case) or between any pair of machines (for the constant case), and possibly the loading/unloading time .

UNBOUNDED WAITING TIMES

Thus, the algorithm of Crama and van de Klundert (1997a) is exponential with respect to the input size. [START_REF] Brauner | Ordonnancement dans des cellules robotisées[END_REF][START_REF] Brauner | Identical part production in cyclic robotic cells: Concepts, overview and open questions[END_REF]) address this issue. The author shows that the best k-cycle in the constant balanced case, and the best 1-cycle in the regular additive balanced case can be found in polynomial time. In the constant balanced case, the optimal k-cycle is one of the two simple permutations: the uphill cycle or the downhill cycle; so the 1-cycle conjecture is true in this case, for any number of machine.

Circular layout with additive travel times

Major results for classical linear cells rely on the dominance of pyramidal permutations over 1-cycles. However this no longer holds for cells with circular layout: a counter-example can easily be found (see for example [START_REF] Rajapakshe | Quantifying the impact of layout on productivity: An analysis from robotic-cell manufacturing[END_REF] or [START_REF] Brauner | Ordonnancement dans des cellules robotisées[END_REF]). Geismar et al. (2005a) note that in this case, the 1-cycle conjecture is still open, and no polynomial algorithm is known for finding the best 1-cycle.

The two machine case is solved, as the proof presented in [START_REF] Sethi | Sequencing of parts and robot moves in a robotic cell[END_REF] is also valid in the circular case. [START_REF] Brauner | Ordonnancement dans des cellules robotisées[END_REF] determines the dominant 1-cycles for 3 and 4 machines cells in the regular additive case. The author introduces the odd-even production cycle, which takes advantage of the cell's circular arrangement by making the robot circle the cell twice, serving even machines on the first round and odd machines on the second, and conjectures its properties for an m-machine regular balanced cells.

For cells with m ≥ 3, Rajapakshe et al. (2011) consider a circular layout with additive regular travel times and generic processing times. Note that the input and output buffers are not in the same place, but separated by δ. However we believe this difference does not qualitatively impact the results. The authors first prove the NP-hardness of the best 1-cycle problem for this layout, then seek to provide approximations in order to assess the performance of a circular layout as opposed to the linear one. They show the odd-even cycle provides a 2-approximation of the best 1-cycle, and provide a 5 3 approximation by introducing a class of cycles called loop cycles, formed by alternating uphill and downhill segments3 . For some cases, depending on the number of short, medium, and long processing times compared to the distance between consecutive machines, a 3 2 approximation or even an optimal 1-cycle is given. No specific results are derived for the balanced case, in particular, the complexity status of the best 1-cycle problem is still open.

As a follow up to this work, [START_REF] Jung | Approximations to optimal sequences in single-gripper and dual-gripper robotic cells with circular layouts[END_REF] extends these results to k-unit cycles. [START_REF] Foumani | Scheduling rotationally arranged robotic cells served by a multi-function robot[END_REF] suggest to replace circular m-machine cells where oddnumbered machines perform similar operation by a m-1 2 -machine cell served by a multifunction robot able to perform those operations. For 1, 2 and 3 machine cells, the author give the exact parameter for which this model allows to decrease the cycle-time. For m machines, they give a sufficient condition: the cycle time is improved if p i ≤ δ for all 1 ≤ i ≤ m. They also give a TSP-based formulation of the problem.

CHAPTER 1. AN INTRODUCTION TO ROBOTIC CELLS

Multi-function robot

Relaxing blocking constraints

Although the classical setup is generally studied on linear cells, models relaxing some of the blocking constraints under additive travel time assumption mostly consider circular layouts.

A way to release this constraint is the use of a dual gripper robot: the robot can handle two parts. The robot can then, for example, use one gripper to transport the part, keep one gripper empty to unload the next machine, then rotate its gripper to load it with the part. This kind of set up is perceived as much more complex than the single gripper one, as the number of possible cycles is much greater: [START_REF] Sethi | Scheduling in dual gripper robotic cells for productivity gains[END_REF] show there are 52 possible 1-cycles for the two machine case (as opposed to 2 cycles only for the single gripper case), 13 of which are non-dominated. [START_REF] Sriskandarajah | Scheduling multiple parts in a robotic cell served by a dual-gripper robot[END_REF] extend the study to the production of multiple part types, showing that for 6 of the 13 undominated cycles, the part sequencing problem is NP-hard. For those cases, [START_REF] Drobouchevitch | A note on scheduling multiple parts in two-machine dual gripper robotic cell: Heuristic algorithm and performance guarantee[END_REF] provide a heuristic with a 3 2 performance ratio. For the production of identical parts in m-machine cells, [START_REF] Sethi | Scheduling in dual gripper robotic cells for productivity gains[END_REF] shows that, if the gripper rotating time is smaller than the travel and processing times, then a very simple cycle which circles the cell once, stopping at each machine to unload then reload it is optimal within 1-cycles. [START_REF] Geismar | Throughput optimization in constant travel-time dual gripper robotic cells with parallel machines[END_REF] shows a similar result in the case of constant travel time, for which [START_REF] Geismar | Approximations to optimal k-unit cycles for single-gripper and dual-gripper robotic cells[END_REF], provide a linear 9 7 -approximation for the optimal multi-unit cycle. Another way to release the blocking constraint is to add input or output buffers at each machine. Drobouchevitch et al. ( 2010) study 1-cyclic production of identical parts in single gripper circular cells with input and output machine buffers. They show that this model allows no improvement compared to a single gripper cell with output machine buffers only. For buffers sufficiently close to the machines, they prove that 1-cycles are dominant. [START_REF] Drobouchevitch | Scheduling dual gripper robotic cell: One-unit cycles[END_REF] compare the performance of these two models. The study is limited to 1-cycles, and the authors consider both dual gripper cells with bufferless machines and single gripper cell with outputs buffers. The travel 1.3. UNBOUNDED WAITING TIMES times are additive and regular. First, they derive all active 1-cycles ("active" meaning that the robot doesn't carry a part without ever unloading it during a full cycle) and construct a polynomial algorithm for finding an optimal 1-cycle in the case where the gripper rotation time is less than the distance between two consecutive machines. Under this assumption, they show that a dual gripper cell performs at least as well as a single gripper cell with output buffers at each machine, and show an example where the improvement is strictly positive. The intuition is that although dual grippers and machine buffers serve the same purpose of temporarily storing parts to free the machines, the dual gripper solution is more time efficient because it potentially reduces the robot travel time.

Note that the equivalence of these two models for an arbitrary number of machines has later been shown by [START_REF] Dawande | Multiple part-type production in robotic cells: Equivalence of two real-world models[END_REF] for the production of multiple parts type, restricted to CRM cycles (which are formed by the repetition of 1-cycles), by establishing a bijection between the dominant CRM cycles for each model, based on the cycle time. [START_REF] Jung | Approximations to optimal sequences in single-gripper and dual-gripper robotic cells with circular layouts[END_REF] study regular additive circular cell with a dual gripper robot. As in [START_REF] Rajapakshe | Quantifying the impact of layout on productivity: An analysis from robotic-cell manufacturing[END_REF], the input and output stations are not at the same place, but separated by δ. Contrary to previous works, the study is not limited to 1-cycles: the authors seek to provide algorithms with performance guarantee for the problem of the optimal k-cycle. To this end, they introduce a class of 2-unit dual gripper cycles called epicyclic cycles providing a 3 2 -approximation, and an optimal k-cycle for some special cases. [START_REF] Geismar | Scheduling robotic cells served by a dual-arm robot[END_REF] introduce a new model, a circular robotic cell served by a dual armed robot. They study the cyclic scheduling for 2 and 3 machine cells and compare the performance with single or dual gripper single armed robot cell.

Jolai et al. (2012) study circularly configured cell where the robot has an additional ability: it can swap the part it holds with the part loaded on the machine. Thus, the robot can load a part on a non-empty machine (and unload the previous part at the same time), which is not possible in the single-gripper classical case. The author derive a formulation of the 1-cycles cycle time depending on the waiting time at the machines, and give a lower bound on the cycle time of any k-cycle.

Gundogdu and Gultekin (2016) consider identical-part production on a 2machine linear regular additive model with a self-buffered robot (where the machines are bufferless but the robot has a dedicated buffer). For a buffer of capacity one, they find the best 1-cycle; for a buffer of capacity 2, they give a

Flexibility and cost optimization

In flexible installations, the operations constituting a job can be performed in any order (operational flexibility), and any machine is capable of performing any type of operation (process flexibility). The change of operation type performed for a machine may usually generate a cost. In this model, the allocation of operations to machines must be solved jointly with the robot move sequence, which makes it closest to the open-shop model. Geismar et al. (2005a) consider a circular layout with input and output buffers at the same position, with regular additive travel times. In this study, the assignment of an operation type to a machine is decided before processing a lot, and cannot be changed until the end of the lot's processing. Therefore, once this assignment is decided, the setup is similar to a classical robotic cell. Note that this type of flexibility has no interest in the balanced case, where the processing times are equal for all operations. The authors provide a bound of the performance gain that can be achieved by changing the operation assignment for 3 and 4 machines, and prove that changing the assignment is never profitable for 2 machines. They note that the bound is the same for 3 and 4 machine cells, but are not sure it could be extended to cells with m ≥ 5.

In subsequent works, machines are considered to have the ability to switch operations very quickly by changing tools, so that several operations for a single part may be performed on the same machine, if the adequate tools are available. [START_REF] Akturk | Robotic cell scheduling with operational flexibility[END_REF] consider the case of identical part production on 2 machines; they show that the optimal cycle is either a 1-cycle or a 2-cycle (disproving the 1-cycle conjecture for this case). [START_REF] Gultekin | Cyclic scheduling of a robotic cell with tooling constraints[END_REF] extend the study to the case where the available tools are limited (tooling constraint): some operations can only be performed on the first machine, and some only on the second. [START_REF] Gultekin | Scheduling in a threemachine robotic flexible manufacturing cell[END_REF][START_REF] Gultekin | Scheduling in robotic cells: process flexibility and cell layout[END_REF][START_REF] Gultekin | Pure cycles in flexible robotic cells[END_REF]) consider identical part production in linear cells, without tooling constraint. They introduce pure cycles, a class of production cycles which take advantage of the operational and process flexibility: each part is loaded on a single machine where it will be entirely processed. [START_REF] Gultekin | Scheduling in a threemachine robotic flexible manufacturing cell[END_REF] study the 3-machine case and show that pure cycles dominate all classical 1-and 2-unit cycles except one. [START_REF] Gultekin | Scheduling in robotic cells: process flexibility and cell layout[END_REF] focus on a particular simple pure cycle where the robots loads every machines from 1 to m, then unloads them in the same order, evaluating its performance compared to classical robot move cycle. They also compare the performance of this cycle in linear and circular 2machine cells, showing that its cycle time is reduced in the circular layout. Finally, [START_REF] Gultekin | Pure cycles in flexible robotic cells[END_REF] show that pure cycles dominate classical flow shop cycles (thus further publications focus on this type of cycle). They also formulate the problem of finding the best pure cycle in an m machine cell as a TSP where some distances are decision variables. [START_REF] Gultekin | Pure cycles in twomachine dual-gripper robotic cells[END_REF] extend the study to dual-gripper cells: they define a framework to study pure cycles for cells with dual gripper robots; for the 2-machine case, they show that only 5 of them dominate the others. [START_REF] Jolai | Cyclic scheduling of a robotic flexible cell with load lock and swap[END_REF] and Foumani and Jenab (2013) look into the case of a robot with swap ability. [START_REF] Jolai | Cyclic scheduling of a robotic flexible cell with load lock and swap[END_REF] shows that in this case too, pure cycles dominate over classical robot move cycles, while Foumani and Jenab (2013) introduce "improved pure cycles", where some machines are left idle, showing that in some instances they perform better than standard pure cycles.

Most studies focus on identical part production. Multiple part type production is addressed by Batur 2012) consider a circular layout with regular additive time. The authors also assume that the total processing time is machine-independent. For an arbitrary number of machines, they give a lower bound on the cycle time of pure cycles, and study the dominance regions and performance limitations of 2 specific pure cycles. The 3-machine case is completely solved. They perform a similar analysis with controllable processing times and similar results: in this case too the 3-machine case is completely solved.

Scope of this work and notations

As exposed in Section 1.3.3, the classical robotic flowshop problems with additive time in a linear layout (Figure 1.1a) and in a circular layout (Figure 1.1b), though very similar in formulation, appear very different in structure and complexity. For the production of identical parts, with unbounded waiting times, finding the best 1-cycle of production has long been known4 to be of polynomial complexity in linear cells (Crama and van de Klundert, 1997a), while the exact same problem in circular cell [START_REF] Rajapakshe | Quantifying the impact of layout on productivity: An analysis from robotic-cell manufacturing[END_REF] was recently proven NP-hard. However, the existing proof (a reduction from 2-Partition) is rather technical, so that it does not make clear the intuition of the difference between the two models. The 1-cycle conjecture, closed for linear layouts (true for m ≤ 3 and false for m > 4) is still open for the circular layout. Though dual-gripper cells have been historically 20 CHAPTER 1. AN INTRODUCTION TO ROBOTIC CELLS studied in circular layouts, few work have considered this layout in the classical, single gripper setup. The authors who consider this case, appear to make a simplifying assumption on the cycle time of a crucial robot move cycle. Aside for the theoretical matter, this makes the comparative evaluation of different models in order to decide on the more appropriate structure and equipment for a cell more complicated.

This work aims to be a step towards a better understanding of cyclic optimization in robotic cells with circular layouts. For this purpose, we mostly focus on the special balanced case (where all processing times are equal) which is well understood in linear layouts [START_REF] Brauner | Ordonnancement dans des cellules robotisées[END_REF][START_REF] Brauner | Identical part production in cyclic robotic cells: Concepts, overview and open questions[END_REF], but largely open for m ≥ 3 in circular layouts. In particular, the complexity of finding the best 1-cycle is still open in circular regular balanced cells, as well as the 1-cycle conjecture (which is proven true for m ≤ 15 for the linear balanced configuration)

In the following, we consider cyclic production of identical parts in a circular robotic cell (as in Figure 1.1b), with a single gripper, no machine buffer, unbounded waiting times, and regular additive travel times. We use the following notations:

• m the number of machines,

• M 1 . . . M m the m machines,
• M 0 the input buffer (IN), and M m+1 the output buffer (OUT),

• δ the travel time between any two consecutive machines M i and M i+1 (both ways) with i ∈ {0, . . . , m}. As the input and output buffers are in the same place, the travel time between M 0 and M m+1 is 0.

• p i for i ∈ {1, . . . , m} the processing time on machine M i (in the non balanced case), and p the processing time on any machine in the balanced case.

Consistently with Lehoux-Lebacque (2007), and to simplify calculations, we assume the loading and unloading times to be zero. Thus, in the balanced case, an instance of the problem is specified by (m, δ, p), and in the non-balanced case by (m, δ, p 1 , . . . , p m ).

Our objective is the minimization of the long run average cycle length. Cycles are specified by their sequence of activities, denoted A i with i ∈ {0, . . . , m}. We use the following notation for cycles:

• π (for permutation) is used to denote a 1-cycle,
• c is used to denote a generic cycle (a k-cycle where k is not necessarily 1),

• For any cycle c, T c is the (long run average) cycle time of c. When useful, the cycle time may be expressed as a function of p and denoted T c (p). If c

SCOPE OF THIS WORK AND NOTATIONS

21 is a k-cycle, its cycle length is given by Tc k (obviously, the cycle length of a 1-cycle π is simply T π ).

Other useful notations will be introduced as need be; they are recapitulated page 125.

As the cell is circular, with regular additive travel times, the travel time between any two machines M i and M j is given by

δ i,j = min(|i -j|, m + 1 -|i -j|)δ (1.1)
Chapter 2 presents tools that will be used throughout this work to analyze production cycles in circular layouts; its reading is recommended before undertaking Chapter 3 and Chapter 4. Chapter 3 adresses the best 1-cycle problem and the 1-cycle conjecture in small cells. By deriving properties of interesting production cycles, we settle the best 1-cycle problem for m ≤ 8 and provide a counter-example to the 1-cycle conjecture for m = 6. In Chapter 4, we consider the best 1-cycle problem in large cells (any m > 8). We identify, define and study a new interesting family of cycles, which lead us to conjecture its dominance over 1-cycles (and thus the polynomiality of the best 1-cycle problem in circular regular balanced cells), proven for m ≤ 11. Chapter 5 is an opening toward a more practical problem, also combining scheduling and transportation. 5Chapter 2

Tools for analysis of production cycles in circular layouts

Notre tête est ronde pour permettre à la pensée de changer de direction.

Francis Picabia

This chapter presents tools that are used throughout this document to bound, visualize and compute cycle times. Section 2.1 expose classical lower bounds for the cycle time. Section 2.2 presents relevant cycles together with practical graphical representations. One of this cycle is specific to circular layouts and so far its cycle time was not fully understood: in Section 2.3, we give and prove a formulation of its cycle time. Finally, Section 2.4 presents a method and tool to numerically compute cycle times.

Lower bounds

In this section, we first present two classical lower bounds on the cycle time of any k-cycle, valid both for linear and circular layout. For each one, we give the formulation adapted to the regular case, and the formulation adapted to the regular balanced case.

Classical bounds

The following bound (LB M ) considers the cell from the machine's point of view. It conveys the minimum time between two loadings of the same machine.

CHAPTER 2. TOOLS FOR ANALYSIS IN CIRCULAR LAYOUTS

Proposition 2.1. LB M (Crama and van de Klundert, 1997a) In a regular cell, any k-cycle c satisfies

T c ≥ k(max i p i + 4δ) (2.1)
In the balanced case, this simplifies to

T c ≥ k(p + 4δ) (2.2)
The following bound (LB R ) considers the cell from the robot's point of view. It counts the minimum travel time of the robots refined by the respective position of consecutive activities.

Proposition 2.2. LB R [START_REF] Dawande | On throughput maximization in constant travel-time robotic cells[END_REF] In a regular cell, any k-cycle c satisfies

T c ≥ k((m + 1)δ + i∈{1,...,m} min(p i , δ)) (2.3)
In the balanced case, this simplifies to

T c ≥ k((m + 1)δ + m min(p, δ)) (2.4)
Each one of the (m+1) activities must be performed exactly k times: the loaded robot moves add up to a travel time of k(m + 1)δ. Additionally, any activity A i is either immediately followed by the subsequent activity A i+1 , in which case the robot must wait p time units at machine M i+1 for the part to be processed, or by any other activity, in which case the robot performs an empty move immediately after A i , adding at least δ to the travel time.

Minimum waiting time

We now introduce the following notations, for every cycle c:

• ∆ c is the total travel time of the robot,

• d i,l (c) is the travel time of the robot between the l-th loading of machine M i and its subsequent unloading (in a cyclic sense). For a 1-cycle, as each machine is loaded (and unloaded) exactly one time, the second index is unnecessary and we simply use the notation d i (π).

• d min (c) = min i,l (d i,l (c)) For example, consider the cycle c = A 0 A 3 A 2 A 4 A 1 , represented later on Fig- ure 2.1. One can verify that ∆ c = 13δ, d 1 = d 3 = 9δ, d 2 = 8δ d 4 = 4δ, thus d min (c) = 4δ.
The following lower bound is actually a lower bound on the cycle time of a given cycle, depending on the values ∆ and d min .

Proposition 2.3. For any cycle c, the cycle time verifies

T (c) ≥ ∆(c) + max(0, p -d min (c)) (2.5) Proof. It is easy to see that T (c) ≥ ∆(c). Let (i 0 , l 0 ) = arg min i,l (d i,l (c)).
Between the l 0 -th loading of M i 0 and its subsequent unloading, the robot travels d min , but there must be at least p units of time for the part to be processed. So, if p ≥ d min , somewhere between the loading and the unloading, the robot must wait (additionally to its travel time) at least p -d min units of time. Hence T (c) ≥ ∆(c) + max(0, p -d min (c))

Classical Cycles and Representation

In this section we introduce three relevant cycles in circular cells (Section 2.2.2).

To describe them, we rely on the two types of graphical representations of cycles that are exposed in Section 2.2.1.

Graphical representation

The first representation is classical and describes the movement of the robot within the cell during the unfolding of a cycle. The second one is new and specific to the balanced case: it allows to compare cycle times of different cycles while varying the cell's parameters.

Representation of the robot moves

The unfolding of a cycle in space and time can be graphically represented on a chronogram. The vertical axis represents the cell, each graduation standing for a machine, from the input buffer to the output buffer. Note that on a circular cell where the output and input buffer occupy the same location, the first and last graduation are virtually equivalent. The horizontal axis represents time. On this graph, loaded robot moves are represented by a solid line and empty robot moves are represented by a dashed line. When needed, we also represent parts being processed by a red solid line.

Representation of the cycle time in the balanced case

In the balanced case, a cell is characterized by three parameters, the number of machines m, the processing p and the travel time δ. Without loss of generality, we can consider that δ is one time unit (by dividing p and δ by δ). For a given m, and by setting δ to 1, we can look at cycle times and lower bounds as functions of p. Seen that way, the cycle time of any cycle is an increasing piecewise linear function.

In order to highlight the performances and optimality regions of cycles, the cycle time functions can be represented on a graph where the horizontal axis represents p and the vertical axis represents time. For example, Figure 2.2 shows lower bounds LB M (Equation (2.2)) and LB R (Equation (2.4)) on such a graph.

Some classical cycles

In this section, we present three classical 1-cycles. The first two, the identity cycle and downhill cycle were formalized and studied by [START_REF] Sethi | Sequencing of parts and robot moves in a robotic cell[END_REF]. We give their cycle time formulation adapted to circular regular cells. The third one, the odd-even cycle is only of interest in circular cells. It has for example been considered by Geismar et al. (2005a), [START_REF] Rajapakshe | Quantifying the impact of layout on productivity: An analysis from robotic-cell manufacturing[END_REF], who uses in their papers a lower bound as its cycle time: they only consider one iteration of the cycle, while deriving the precise cycle time requires to consider several consecutive iterations. This makes the cycle time derivation more complex than for the two former cycles: we give a formulation and proof in Section 2. For each of these three cycles, we give an execution example on instance I :

(m = 4, p = 3, δ = 1) (see respectively Figures 2.3, 2.

and 2.6).

Identity cycle

We call identity cycle (also named uphill permutation or forward cycle in the literature) the cycle π id = A 0 A 1 ...A m , represented on Figure 2.3. In this cycle, the robot circles the cell once, doesn't perform any empty move and waits at each machine during the full length of the processing. We have ∆ π id = (m + 1)δ and d i (π id ) = 0 for all i ∈ {1, . . . , m}, thus d min (π id ) = 0. The corresponding cycle time, respectively in the non-balanced and balanced case, is:

T π id = (m + 1)δ + i∈{1,...,m} p i (2.6) T π id = (m + 1)δ + mp (2.7)
Intuitively, this cycle is interesting for instances for which p is much smaller than δ. From the lower bound LB R (Proposition 2.2), one can derive the following classical result: Proposition 2.4. In a regular balanced cell, if p ≤ δ, then the identity cycle π id is optimal.

Downhill cycle

We call downhill cycle (also named reverse cycle) the cycle

π dh = A 0 A m A m-1 ...A 1 , represented on Figure 2.4.
We have ∆ π dh = 3(m + 1)δ and d i (π dh ) = (3m -1)δ for all i ∈ {1, . . . , m}, thus d min (π dh ) = (3m -1)δ. Its cycle time, respectively in the non-balanced and balanced case, is:

T π dh = 3(m + 1)δ + max i∈{1,...,m} (0, p i -(3m -1)δ) (2.8) T π dh = 3(m + 1)δ + max(0, p -(3m -1)δ) (2.9)
In this cycle, each spot is visited by the robot three times. Intuitively, this cycle is interesting for instances for which p is much larger than δ. From the lower bound LB M (Proposition 2.1), one can derive the following classical result:

Odd-Even cycle

In circular cells, a third 1-cycle of particular interest is the odd-even cycle, defined as such: For m even,

π oe = A 0 A 2 A 4 . . . A m A 1 A 3 A 5 . . . A m-1
And for m odd,

π oe = A 0 A 2 A 4 . . . A m-1 A 1 A 3 A 5 . . . A m .
In this cycle, the robot circles around the cell twice: the first time performing even activities (thus loading odd machines), the second time performing odd activities (thus loading even machines). Is overall travel time is ∆ πoe = 2(m + 1)δ and we have d i (π oe ) = (m + 1)δ for all i ∈ {1, . . . , m}, thus d min (π oe ) = (m + 1)δ. Note that contrary to π id and π dh , this cycle is not a pyramidal permutation as defined in (Crama and van de Klundert, 1997a), therefore it is dominated in linear cells.

Cycle time of the odd-even Cycle

In order to understand the cycle time of π oe , it is necessary to consider several iterations. In this section, we give and prove the formulation of its cycle time in the balanced case as well as lower and upper bounds for the non-balanced case.

Balanced case Proposition 2.6. The cycle time for the odd-even cycle is

T πoe = 2(m + 1)δ + 2α -1 α max(0, p -(m + 1)δ) with m =    2α if m even 2α -1 if m odd Proof.
Consider α consecutive iterations of π oe . The robot travels 2(m + 1)αδ, circling the cell 2α times. Let us follow the path of one same part in the cell. Each iteration is constituted by two loops around the cell. During the first loop of the first iteration, machine M 1 is loaded with A 0 . It is then unloaded during the second loop with A 1 . Between the loading and the unloading of M 1 , the robot travels (m+1)δ and the part must remain on M 1 at least p time units, so the robot must wait max(0, p -(m + 1)δ). Similarly, during any loop, the part is loaded on a machine, then unloaded and taken to the next machine during the next loop, and the robot must wait max(0, p -(m + 1)δ). If m is odd, the part exits the cell on the last loop. If m is even, it is loaded on M m during the last loop.

Eventually, for this one part, the robot must wait at least (2α -1) max(0, p -(m + 1)δ) over α iterations of the cycle. Therefore,

T πoe ≥ 2(m + 1)δ + 2α -1 α max(0, p -(m + 1)δ) (2.10)
Now, let us call w j i the waiting time of the robot at machine M j during the i-th iteration of cycle π oe , and

W i = (w i 1 , . . . , w i m ). Let a = p -(m + 1)δ. Case 1: m odd π oe = (A 0 A 2 A 4 . . . A m-1 A 1 A 3 A 5 . . . A m )
The waiting times at iteration i are:

         w i 2j = max(0, a - α k=1+j w i-1 2k-1 - j-1 k=1 w i 2k ) w i 2j-1 = max(0, a - α-1 k=j w i 2k - j-1 k=1 w i 2k-1 )
If a ≤ 0 then all waiting times are zero, and the cycle time is 2(m + 1)δ.

If not, we can easily check that the vector

W 0 = ( a α , . . . a α ) is a fixed point of W . The corresponding cycle time is 2(m + 1)δ + 2α-1 α a. Case 2: m even π oe = (A 0 A 2 A 4 . . . A m A 1 A 3 A 5 . . . A m-1 )
Similarly, the waiting times at iteration i are

         w i 2j = max(0, a - α k=1+j w i-1 2k-1 - j-1 k=1 w i 2k ) w i 2j-1 = max(0, a - α k=j w i 2k - j-1 k=1 w i 2k-1 )
If a ≤ 0 then W = 0, and the cycle time is 2(m + 1)δ.

If not, we can check that the vector W 0 = (0, a α , . . . a α ) is a fixed point of W . The corresponding cycle time is 2(m + 1)δ + 2α-1 α a

In both cases the lower bound (2.10) is tight, so the cycle time is:

T πoe = 2(m + 1)δ + 2α -1 α max(0, p -(m + 1)δ) (2.

Non balanced case

In the non-balanced case, one can derive in a similar way a lower and an upper bound for π oe 's cycle time, depending on p min = min

(i) T πoe ≥ 2(m + 1)δ + max 0, 2α-1 α (p min -(m + 1)δ) (ii) T πoe ≤ 2(m + 1)δ + max 0, 2α-1 α (p max -(m + 1)δ) Proof.
(i) The proof is similar to the balanced case, considering that the necessary waiting time between the loading and unloading of a part on any machine is at least p min -(m + 1)δ.

(ii) The waiting time needed between the loading and unloading of a part on any machine is at most p max -(m + 1)δ), which is ensured by the waiting times vector [START_REF] Brauner | Ordonnancement dans des cellules robotisées[END_REF] proved that for any cycle, independently of the initial state, the cell reaches a periodic steady state, after a finite number of cycle iterations. This

W max = pmax-(m+1)δ α , . . . pmax-(m+1)δ α for m odd or W max = 0, pmax-(m+1)δ α , . . . pmax-(m+1)δ α for m even.

Cycle time computation

CYCLE TIME COMPUTATION

33

means that there exists a number of iterations (a period) that leaves the cell in exactly the same state, as defined above. Note that if the minimum period is strictly greater than one, cycle time may differ between consecutive iterations. Therefore, to compute the long run average cycle time, it is necessary to consider a whole period.

For example, Figure 2.9 shows 4 consecutive iterations of π oe on instance J : (m = 4, p = 6, δ = 1) once reached a periodic steady state. Iterations 3 and 4 are identical to iterations 1 and 2, which shows the execution is 2-periodic. Looking at the first two iterations, we can see that they unfold differently: during the first one, the robot waits one time unit at machine M 2 and M 3 , while during the second one, waiting is only needed at M 4 . Consequently, the first iteration lasts 12 time units, while the second one lasts 11 time units. Looking at the duration of a single iteration leads to an over-or under-estimation of the long run cycle time: to get an accurate measure, it is necessary to consider the average execution time over 1 period, here 2 iterations, which gives the correct cycle time of 11.5. We developed a tool in Java allowing to simulate the behavior of the cell and therefore experimentally compute cycle times. The input consists in the size of the cell, travel times and processing times, either integer or fractional.

The state of the cell is represented by the position of the robot, and a vector of fractional values representing the state of the machines. If the value for a machine is non-negative, it represents the remaining processing time on this machine. If not, it means the machine is free. Given a cycle, a feasible initial state is automatically computed by loading the machines which need to be loaded with a remaining processing time of 0. To compute the cycle time, the program first performs several initialization iterations to ensure the cell is running in a periodic steady state (the number of initial iterations can be set by the user). The period is then calculated by monitoring the cell's state after each subsequent iteration and comparing it to the state it was in immediately after the initialization. The programs then outputs the average value of the cycle time over one period.

Conclusion

In this chapter, we presented tools that serves as a basis for studying cyclic production in circular cells, including lower bounds on the cycle time, graphical representations and three particular cycles.

We showed that for cycle which exploits the circular structure of the cell by circling it twice, as the odd-even cycle π oe , derivation of the cycle time formulation is not trivial as the cycle has to be considered over several iterations. This cycle structure is especially important in Chapter 4, where we study families of cycles formed by altering the odd-even cycle.

Chapter 3

Properties of 1-cycles and small cells analysis

The objective of this chapter is to settle properties for 1-cycles in order to find interesting production cycles. We first study the region of optimality within 1cycles of the three classical 1-cycles introduced in Chapter 2 (Section 3.1). Then, we establish necessary properties for the best 1-cycles (Section 3.2), which allow to conclude for small cells (m ≤ 8) in Section 3.3. The best 1-cycle problem for larger cells will be studied in Chapter 4. As the 2-machine case is solved [START_REF] Sethi | Sequencing of parts and robot moves in a robotic cell[END_REF], we consider m ≥ 3.

In regular additive linear balanced cells, the 1-cycle conjecture is valid for m < 16 [START_REF] Brauner | Identical part production in cyclic robotic cells: Concepts, overview and open questions[END_REF]. In regular additive circular balanced cell, for m = 6 we exhibit a 2-cycle that is strictly better than any 1-cycle for a given instance, thus disproving the 1-cycle conjecture for circular balanced cells (Section 3.4).

To make the proofs more readable, we use this notation for activities:

A i = A i mod (m+1)

Regions of optimality for the classical cycles

In this section, within the set of 1-cycle, we seek for the best ones. Here "optimality" is in the sense of optimality within 1-cycles. We consider the three classical cycles {π id , π dh , π oe } and describe characteristics of instances for which they are optimal. We use the lower bounds on the cycle time LB M and LB R described in Chapter 2 (page 23), to which we add a new lower bound (LB D ) specific to 1-cycles, by considering the direction of the robot:

Proposition 3.1. (LB D ) If p ≥ δ, and π is a 1-cycle with π = π id , then T π (p) ≥ 2(m + 1)δ (3.1)

CHAPTER 3. ONE-CYCLES AND SMALL CELLS ANALYSIS

Proof. Let π be a 1-cycle different from the identity cycle π id .

Case 1: If π contains a sequence A i A j with j = i+2 and j = i+1, then, following a reasoning similar to the one behind Proposition 2.2 page 24, we have

T π (p) ≥ (m + 1)δ + (m -1) min(p, δ) + 2δ ≥ 2(m + 1)δ
It takes the robot (m + 1)δ time units to perform all activities, then at least min(p, δ) between any pair of consecutive activities except for A i A j , and at least 2δ to travel from M i+1 to M j while performing A i A j .

Case 2: If not, then π contains at least a sequence A i A i+2 (as π = π id ), and every other 2-element sub-sequence in π can be written A j A j+1 or A j A j+2 . Then, we know that:

• The robot always travels in the same direction, forward: with m ≥ 3, the shortest circular path from a machine M j to M j+1 never requires to go backward.

• The robot travels at least twice between M i+1 and M i+2 . Once loaded, while performing activity A i+1 and once empty, while performing the sequence

A i A i+2 .
Hence the robot circles the cell at least twice:

T π (p) ≥ 2(m + 1)δ
The following proposition specifies the regions of optimality of {π id , π dh , π oe }.

Proposition 3.2.

(i) if p ≤ m+1 m δ, then the identity permutation π id dominates 1-cycles.

(ii) if (m+1) m δ ≤ p ≤ (m + 1)δ, then the odd-even cycle π oe dominates 1-cycles. (iii) if p ≥ (3m -1)δ, the downhill permutation π dh dominates 1-cycles (and even all k-cycles).

Proof. Recall that the the cycle times of π id , π oe and π dh are given by

T π id (p) = (m + 1)δ + mp T πoe (p) = 2(m + 1)δ + 2α -1 α max(0, p -(m + 1)δ) where α = m + 1 2 T π dh (p) = 3(m + 1)δ + max(0, p -(3m -1)δ)
Claim (iii) is a classical result that follows directly from Proposition 2.1. For p ≥ (3m -1)δ, T π dh (p) = p + 4δ, hence by Proposition 2.1 (LB M ), π dh dominates all k-cycles thus proving (iii).

For p ≤ δ, then from Proposition 2.2 (LB R ), for any k-cycle c, one has T c (p) ≥ k(m + 1)δ + mp = kT π id (p), hence π id is optimal.

For δ ≤ p ≤ m+1 m δ, we have

T π id (p) = (m + 1)δ + mp ≤ 2(m + 1)δ
and, from Proposition 3.1 (LB D ), for any 1-cycle π = π id :

T π (p) ≥ 2(m + 1)δ ≥ T π id (p) (3.3) which implies (i). Finally, for (m+1) m δ ≤ p ≤ (m + 1)δ, we have T πoe (p) = 2(m + 1)δ T π id (p) = (m + 1)δ + mp ≥ 2(m + 1)δ
and for any 1-cycle π = π id , from Proposition 3.1 (LB D ):

T π (p) ≥ 2(m + 1)δ ≥ T πoe (p)
which implies (ii).

Proposition 3.2 settles the case of p ≤ (m + 1)δ and p ≥ (3m -1)δ, as summarized by Figure 3.1. In this graphic, we can see that in their regions of optimality the corresponding cycles fit with a lower bound. Now remain the instances with (m + 1)δ < p < (3m -1)δ. This is the issue addressed in the next section.

Necessary properties of optimal 1-cycles

In this section, we assume that (m + 1)δ < p < (3m -1)δ since other cases are settled in Proposition 3.2. We establish some properties (Propositions 3.3 to 3.6) that a 1-cycle must satisfy in order to do strictly better than both the odd-even cycle and the downhill permutation. We will use these properties later on in Section 3.3 to determine the best 1-cycles for m ≤ 8.

Let π * be such a 1-cycle, thus verifying for some (m + 1)δ ≤ p ≤ (3m -1)δ,

T π * (p) < T πoe (p) T π * (p) < T π dh (p) = 3(m + 1)δ (3.4)
Unless otherwise specified, the following properties are valid for m ≥ 3. Propositions 3.3 to 3.4 are valid for m ≥ 5. Proof. First, π * contains at most one sub-sequence of two consecutive activities (except from the sequence A m A 0 ). Otherwise, as the robot waits p time units at each machine M i such that π * contains A i A i+1 and travels at least (m + 1)δ (performing all activities), we have T π * (p) ≥ (m + 1)δ + 2p ≥ 3(m + 1)δ = T π dh (p), which contradicts Equation (3.4).

CHAPTER 3. ONE-CYCLES AND SMALL CELLS ANALYSIS

p time LB M LB R LB D π id π dh π oe 2(m + 1)δ 3(m + 1)δ (3m -1)δ (m + 1)δ m+1 m δ π dh ?? π oe π id
Let us assume now that there exists exactly one i = m so that A i A i+1 is a sub-sequence of π * . The robot waits (m + 1)δ at machine M i+1 . It travels at least (m + 1)δ while loaded (performing the m + 1 activities), and (m -1)δ while empty (after performing each one of the activities A j , j / ∈ i, m, the robot travels at least δ to get to the next machine to unload). Thus, we already have

T * π (p) ≥ 2(m + 1)δ + (m -1)δ (3.5)
We show that the robot travels at least an additional 2δ, leading to

T * π (p) ≥ 3(m + 1)δ. Case 1: π * is of the form A 0 A 1 . . . A m .
In this case, for m ≥ 5, either π * contains the subsequence A m-1 A 2 , or there exist indices j, k / ∈ {m, 0, 1} so that A m-1 A j and A k A 2 are two distinct subsequences of π * . In both cases, the robot travels at least an additional 2δ compared to Equation (3.5).

Case 2: π * is of the form A 0 . . . A m-1 A m .
In this case, for m ≥ 5, either π * contains the subsequence A m-2 A 1 , or there exist indices j, k / ∈ {m -1, m, 0} so that A m-2 A j and A k A 1 are two distinct sub-sequences of π * . Again, in both cases, the robot travels at least an additional 2δ compared to Equation (3.5).

Case 3: π * is of the form A 0 . . . A i A i+1 . . . A m , with 1 ≤ i ≤ m -2.
In this case, either π * contains the subsequence A i-1 A i+2 , or there exist indices j, k / ∈ {i, i + 1} so that A i-1 A j and A k A i+2 are sub-sequences of π * . In the second case, the robot travels an additional 2δ. In the first case, π * can be written in one of the following ways:

π * = A 0 . . . A i A i+1 SA i-1 A i+2 . . . A m (3.6) π * = A 0 . . . A i-1 A i+2 SA i A i+1 . . . A m (3.7)
Where S is an activity sequence, including the empty sequence.

The robot already travels an additional δ while performing A i-1 A i+2 . In order to have no additional travel time, the sequence A i+1 SA i-1 in (3.6) or A i+2 SA i in (3.7) must be one of the following sequences (in the cyclic sense):

   A 0 A 2 A 4 . . . A m-1 or A 1 A 3 A 5 . . . A m if m is odd A 0 A 2 A 4 . . . A m A 1 A 3 A 5 . . . A m-1 if m is even
which is impossible as S cannot contain A 0 or A m . So, the robot travels at least an additionnal 2δ compared to Equation (3.5)

Case 4: π * is of the form . . . A i A i+1 . . . and π * does not contain A m A 0 .
In this case, there exist indices j, k / ∈ {i, i + 1} and l = 0 so that A i-1 A j , A k A i+2 and A m A l are subsequences of π * , with at least 2 of these subsequences distinct. In both cases, the robot travels at least an additional 2δ. Proof. First, we show that ∆ π * ≥ 2(m + 1)δ. This is a consequence of Proposition 3.3. As π * contains no sequence of the form A i A i+1 with i = m, there are two possibilities:

Case 1: There exists a sub-sequence A i A j with j = i + 2 in π * . Then the travel time of the robot is at least (m + 1)δ + mδ + δ = 2(m + 1)δ

Case 2: π * contains only subsequences of the form A i A i+2 and maybe A m A 0 .

Similarly to the proof of Proposition 3.1, we can say that the robot always travels forward, and circles the cell twice: ∆ π * ≥ 2(m + 1)δ. Now, let us show that the only cycle such that ∆ π * = 2(m + 1)δ is the odd-even cycle π oe . We already know that π * can have no sub-sequences

A i A i+1 except for A m A 0 .
Case 1: π * does not contain the sequence A m A 0 . Then all sub-sequences have to be of the form A i A i+2 : the only possible cycle is of the form

A 0 A 2 A 4 . . . A m A 1 A 3 . . . A m-1 , which is π oe if m is
T π * (p) ≥ 3(m + 1)δ = T π dh (p)
The following proposition links the total travel time of π * , ∆ π , with the minimum travel time between the loading and unloading of a machine d min (π * ). Recall from Proposition 2.3 page 25 that the cycle time of any cycle c is at least ∆ c + max(0, p -d min (c)). Note that this lower bound is a piece-wise linear function of p whose slope changes for p = d min (the slope is 0 for p ≤ d min and 1 otherwise).

Proposition 3.6. d min (π * ) > ∆ π -3α-2 2α-1 (m + 1)δ, where α = m+1 p time π dh πoe f lower bound on Tπ * (3m -1)δ (m + 1)δ ∆π * -3α-2 2α-1 (m + 1)δ ∆π * (a) d min (π * ) < ∆ π * -3α-2 2α-1 (m + 1)δ p time π dh πoe f lower bound on Tπ * (3m -1)δ (m + 1)δ ∆π * -3α-2 2α-1 (m + 1)δ ∆π * (b) d min (π * ) > ∆ π * -3α-2 2α-1 (m + 1)δ
f (p) = p + 3α -2 2α -1 (m + 1)δ (3.8) For (m + 1)δ ≤ p ≤ p * , T π dh (p) ≥ f (p) ≥ T πoe (p) For p * ≤ p ≤ (3m -1)δ, T πoe (p) ≥ f (p) ≥ T π dh (p) Suppose that d min (π * ) ≤ ∆ π * -3α-2 2α-1 (
T π * (p) ≥ ∆ π * + max(0, p -d min (π * )) (3.9) ≥ ∆ π * + max(0, p -∆ π * + 3α -2 2α -1 (m + 1)δ) (3.10)
For p ≤ ∆ π * -3α-2 2α-1 (m + 1)δ, we get

T π * (p) ≥ ∆ π * ≥ p + 3α -2 2α -1 (m + 1)δ = f (p)
and for p > ∆ π * -3α-2 2α-1 (m + 1)δ,

T π * (p) ≥ ∆ π * + p -∆ π * + 3α -2 2α -1 (m + 1)δ = p + 3α -2 2α -1 (m + 1)δ = f (p)
T π * ≥ f and thus π * is dominated by {π oe , π dh } for (m + 1)δ < p < (3m -1)δ So necessarily, d min (π * ) > ∆ π * -3α-2 2α-1 (m + 1)δ (this is the situation represented on Figure 3.2b).

Best 1-cycles for m ≤ 8

We know that 1-cycles are permutations of activities. Given a 1-cycle, it is easy to check if it complies with the conditions exposed in the previous section. Of course this can only be done for small numbers of machines as the number of 1-cycles is exponential (m!). In this section, we use these properties to prove the following theorem, establishing dominant sets over 1-cycles for m ≤ 8.

Theorem 3.1. Dominance within 1-cycle for m ≤ 8

For regular balanced cells with m = 3 or 6 ≤ m ≤ 8 the set {π id , π dh , π oe } dominates all 1-cycles.

For regular balanced cells with m = 4, the set {π id , π oe , π * 4 , π dh }, where

π * 4 = A 0 A 3 A 2 A 1 A 4 dominates all 1-cycles.
For regular balanced cells with m = 5, the set {π id , π oe , π * 5 , π dh }, where π * 5 = A 0 A 3 A 2 A 5 A 1 A 4 dominates all 1-cycles.

m ≤ 4

For m = 3 and m = 4, we use Proposition 3.5 and Proposition 3.6 to filter out cycles. Among the six possible cycles for m = 3, only π oe and π id satisfy both conditions, thus {π id , π dh , π oe } dominates 1-cycles. This confirms the result presented in [START_REF] Brauner | Ordonnancement dans des cellules robotisées[END_REF].

Thus the best 1-cycles for m = 3 are given by:

* 4 = A 0 A 3 A 2 A 1 A 4
• for p ≤ 4 3 δ, π id is optimal within 1-cycle;

• for 4 3 δ < p ≤ 20 3 δ, π oe is optimal within 1-cycles

• for p > 20 3 δ, π dh is optimal within 1-cycles.

Among the 24 possible 1-cycles for m = 4, π oe , π dh as well as another permutation π * 4 = A 0 A 3 A 2 A 1 A 4 , represented on Figure 3.3 satisfy both conditions. The best 1-cycle for m = 4 can be determined by comparing the cycle times of {π id , π dh , π oe } and π * 4 .

Proposition 3.7. Best 1-cycles for m=4

The best 1-cycles for m = 4 are given by:

• for p ≤ 5 4 δ, π id is optimal within 1-cycle;

• for 5 4 δ < p ≤ 7δ, π oe is optimal within 1-cycles

• for 7δ < p ≤ 10δ, π * 4 is optimal within 1-cycles

• for p ≥ 10δ , π dh is optimal within 1-cycles.

Proof. For p ≤ 5δ, and p ≥ 11δ, this is a direct consequence of Proposition 3.2. The characteristics of π * 4 are as follows: For p ≥ 10, from Equation (3.11b) and Equation (3.12), π * 4 is dominated by π dh . We can show that for p ≤ 10, the bound given by Equation (3.12) is tight. For p ≤ 8δ, no waiting time is necessary. For 8δ < p ≤ 9δ the bound is reached by waiting exactly p -8δ at machine M 1 ; for 9δ < p ≤ 10δ, it is reached by waiting exactly p -9δ at machine M 2 and 1δ at M 1 . We can easily verify that no other waiting time is necessary. Together with Equation (3.11a), we get the final result.

∆ π * 4 = 13δ, d 1 (π * 4 ) = d 4 (π * 4 ) = d min (π * 4 ) = 8δ and d 2 (π * 4 ) = d 3 (π * 4 ) = 9δ. For 5δ < p < 11δ,

m ≥ 5

For m ≥ 5, we can use Proposition 3.4, Proposition 3.5 and Proposition 3.6 to filter out cycles. Note that Proposition 3.4 and Proposition 3.6 imply Proposition 3.3: if ∆ π > 2(m + 1)δ, then the condition in Proposition 3.6 implies that if π is non-dominated by {π id , π dh , π oe }, d min (π) > 0. Thus no loading of a machine is immediately followed by its unloading, which means that π contains no sequence

A i A i+1 with i = m.
Thus, we seek cycles satisfying:

2(m + 1)δ <∆ π * < 3(m + 1)δ (3.13) d min (π * ) > ∆ π * - 3α -2 2α -1 (m + 1)δ (3.14)
For m = 5, only the cycle π * 5 = A 0 A 3 A 2 A 5 A 1 A 4 , represented on Figure 3.4 satisfies these conditions, as can be verified by simple enumeration of the 120 1-cycles.

Proposition 3.8. Best 1-cycles for m=5

The best 1-cycles for m = 5 are given by:

• for p ≤ 6 5 δ, π id is optimal within 1-cycles;

• for 6 5 δ < p ≤ 42 5 δ, π oe is optimal within 1-cycles;

• for 42 5 δ < p ≤ 12δ, π * 5 is optimal within 1-cycles;

• for p ≥ 12δ, π dh is optimal within 1-cycles. For p ≥ 12δ, from Equation (3.15b) and Equation (3.16), π * 5 is dominated by π dh . We can show that for p ≤ 12δ, the bound given by Equation (3.16) is tight: for p ≤ 10δ, no waiting time is necessary; for 10δ < p ≤ 12δ, the bound is reached by waiting exactly p -10δ at machine M 2 . We can easily verify that no other waiting time is necessary. From this and Equation (3.15a), we get the final result.

A COUNTER-EXAMPLE TO THE 1-CYCLE CONJECTURE

For 6 ≤ m ≤ 8, no 1-cycle satisfies the conditions (this can be verified by enumerating the m! possible 1-cycles), thus {π id , π dh , π oe } dominates 1-cycles. This completes the proof of Theorem 3.1.

For m > 8, this filtering does not seem sufficient to rule out all dominated 1-cycles. This case will be the topic of Chapter 4.

A counter-example to the 1-cycle conjecture

In [START_REF] Brauner | Identical part production in cyclic robotic cells: Concepts, overview and open questions[END_REF], the author claims that in linear balanced cells, the 1-cycle conjecture is valid at least for m < 16. We state, by the following theorem, that CHAPTER 3. ONE-CYCLES AND SMALL CELLS ANALYSIS in circular balanced cells it is false for m = 6. For m ≤ 5, it is still open but using the simulation tool presented in Chapter 2, we did not find any 2-cycle performing strictly better than the best 1-cycles. Theorem 3.2. In a regular balanced unbounded 6-machine cell with circular layout, the 2-cycle

Ĉ = (A 0 A 2 A 5 A 4 A 1 A 6 A 0 A 3 A 2 A 5 A 1 A 4 A 3 A 6 )
dominates all 1-cycles for the following instance:

δ = 1 = 0 p = 11 .
Proof. Let us consider a 6-machine circular cell, with p = 11, δ = 1, = 0. From Theorem 3.1, we know that the set {π id , π dh , π oe } dominates all 1-cycles.

For these parameters, one has T π id = 7 + 66 = 73 (3.17)

T πoe = 14 + 5 3 4 = 20 + 2 3 (3.18) T π dh = 21 (3.19)
We just need to show that T ( Ĉ)

k < T πoe = 20+ 2 3 .
An iteration of Ĉ is represented on Figure 3.5. During one iteration of Ĉ, the robot travels ∆ Ĉ = 39. We have d 6,1 = d 2,1 = 10, and for all other (i, k), d i,k ≥ 11. As the first unloading of M 6 takes place between the first loading of M 2 and its subsequent unloading, the robot only needs to wait one unit of time, before unloading M 6 (see Figure 3.5).

Thus, we have T Ĉ = 39 + 1 = 40

T Ĉ 2 = 20 < T (π oe )
In conclusion, Ĉ is strictly better than all 1-cycles on this instance. We proved Theorem 3.2, thus showing that the 1-cycle conjecture is false for 6 machines in circular balanced cells. The problem is still open for m ≤ 5 (although we think it is valid).

Conclusion

In this chapter, we focused on 1-cycles. Using the lower bounds and the cycle time of the odd-even cycle π oe derived in Chapter 2, we settled values of parameters p and δ for which one of the classical cycles {π id , π dh , π oe } is optimal. Together with necessary properties of optimal 1-cycles we were able to solve the best 1cycle problem for cells with up to 8 machines. However, we showed that the 1-cycle conjecture is false for circular balanced cells, by exhibiting a 2-cycle which performs strictly better than any 1-cycle for a given instance of 6 machines. The best k-cycle even for k ≤ 2 is still open for circular regular balanced cells with m ≥ 3.

The properties established in this chapter are not sufficient to conclude on the best 1-cycle problem for m ≥ 9. In the next chapter, we look into the structure of optimal 1-cycles for large cells.

Chapter 4

Dominant structures for large cells

Life was a lot less complex before you tried to explain.

Jasper Fforde, Shades of Grey

Introduction

In this chapter, we study the best 1-cycle problem in regular balanced cells with any number of machine m. One-cycles are not necessarily optimal among general cycles, even for cells with circular layout: an instance for which a 2-cycle is better than any 1-cycle is described in the previous chapter. Still, finding the best 1-cycle remains a problem of interest due to their operational convenience. Interestingly, the layout of the cell has an impact on this problem's complexity. While it has been shown polynomial in linear additive cells (Crama and van de Klundert, 1997a), this result, based on the dominance of pyramidal permutations, does not stand for circular layouts: Rajapakshe et al. (2011) showed that finding the best 1-cycle turns to be NP-hard in a circular additive cell, even assuming regularity (regularly spaced machines). Yet for the simpler model of circular regular balanced cell (where processing times are equals for all machines), the complexity of finding the best 1-cycle is still unknown. Studying structural properties of good cycles in this simpler case might lead to progress on this issue and to a better understanding of the difference of complexity between both layouts in the more general regular case.

For small-scale regular balanced cells (m ≤ 8), the best-1-cycle problem has been solved in the previous chapter. We showed in particular that for 6 ≤ m ≤ 8, 50 CHAPTER 4. DOMINANT STRUCTURES FOR LARGE CELLS the three classical cycles introduced in Chapter 2, {π id , π dh , π oe }, dominate 1-cycles (meaning that for any instance, one of these three cycles performs at least as well as any 1-cycle). However, the proof cannot be extended to larger cells. In this chapter, we are interested in cells with an arbitrarily large number of machine m, and thus assume m > 8.

Section 4.2 recalls the optimality regions of the classical cycles {π id , π dh , π oe }. In Section 4.3, we present observations resulting from numerical computation of cycle times for 9 ≤ m ≤ 14. Section 4.4 investigates general structural properties of cycles likely to dominate {π id , π dh , π oe }. In Section 4.5, we focus on a family of cycles generalizing observations in Section 4.3 and derive their cycle times. Section 4.6 compares this family to more general cycles obeying the dominant structure presented in Section 4.4. Based on this, in Section 4.7, we conjecture that the family presented in Section 4.5 dominates 1-cycles. This conjecture is proven valid for m ≤ 11 and holds up with numerical computation for m ≤ 14. If proven valid for any m, it would imply that the best 1-cycle problem in circular regular balanced cells is polynomial.

Region of optimality of the classical cycles

The three classical 1-cycles, namely the identity cycle (ii) if (m+1) m δ ≤ p ≤ (m + 1)δ, then the odd-even cycle π oe dominates 1-cycles; (iii) if p ≥ 3(m -1)δ, then the downhill permutation π d dominates 1-cycles. Thus, in this chapter, we only consider the remaining case, where (m + 1)δ < p < (3m -1)δ. Recall that for these values of p, cycle π id is dominated by π oe and need not be considered, while the cycle times of π dh and π oe are given by:

π id = A 0 A 1 . . . A m , the downhill cycle π dh = A 0 A m A m-1 . . . A 1 and the odd-even cycle π oe = A 0 A 2 A 4 . . . A 1 A 3 A 5 . . .
T π dh (p) = 3(m + 1)δ (4.1) T πoe (p) = 2(m + 1)δ + 2α -1 α (p -(m + 1)δ) with α = m + 1 2 (4.2)
Recall also that p * denotes the value of the processing time such that T πoe (p * ) = T π dh (p * ). Its value is p * = 3α-1 2α-1 (m + 1)δ. Over the considered interval, p * is 4.3. EXPERIMENTS 51 the smallest value for which min(T πoe , T π dh ) reaches its maximum (see Figure 4.1 to visualize this property). Potential best 1-cycles must be non-dominated by {π id , π dh , π oe }, meaning that there exists at least a value of p for which their cycle time is smaller than the cycle time of any member of {π id , π dh , π oe }. The following proposition further restricts the interval to consider to find such a value of p and to show that a cycle is non-dominated by {π id , π dh , π oe }, using this property of p * .

Experiments

Propositions 3.3 to 3.6 (pages 38 to 40) state that any cycle π dominating {π id , π dh , π oe } for some p in the considered region satisfies the following three structural properties:

∀i = m, A i A i+1 / ∈ π (4.3) 2(m + 1)δ < ∆ π < 3(m + 1)δ (4.4) d min (π) > ∆ π - 3α -2 2α -1 (m + 1)δ where α = m + 1 2 (4.5)
where ∆ π is the total travel time during one iteration of the cycle, and d min (π) is the minimum travel time between the loading and unloading of a same machine (d min = min For 6 ≤ m ≤ 8, no 1-cycle satisfies these conditions; however for m > 8, they do not rule out all 1-cycles. We call f iltered(m) the set of 1-cycles satisfying the conditions; Table 4.1 shows the number of such cycles for 9 ≤ m ≤ 14. For m ≥ 15, the total number of 1-cycles is too high for an exhaustive filtering. Using the simulation tools presented in Section 2.4, page 32, we numerically computed the cycle times of these cycles while varying the processing time p. This section presents an overview of the resulting observations. Although ergodicity of the cycle time is often assumed when studying robotic cells, it has not been formally proven in general. Thus, as the periodic steady state reached by the simulated cell depends on its initial state, so might the resulting mean cycle time, and these numerically computed values are only upper bounds on the cycle time. The following numerical observations should therefore be taken with caution: they only serve as a motivation for the subsequent formal study.

Performance

For each 9 ≤ m ≤ 14, some cycles of f iltered(m) appear to slightly dominate {π oe , π dh } in the neighborhood of p * , as can be seen for example in Figure 4.2 for 9 and 10 machines. Table 4.2 shows the computed performance ratio of {π oe , π dh } for p = p * , based on the computed cycle times of members of f iltered(m), at p * where it appears to be the worst. Note the higher ratio for m = 13.

Set of dominant 1-cycles

Many of the cycles in f iltered(m) are equivalent or strictly dominated by others within the considered area. Looking closer, it appears that few cycles (1 or 2) need to be added to the set {π id , π dh , π oe } to form a dominant set within 1-cycles. This is apparent on Figure 4.3, which shows computed cycle times for members of f iltered(m) in p * neighborhood. Table 4.3 shows, for 9 ≤ m ≤ 14, a possible dominant set and the numerical optimality regions, computed using a step of 0.01 for p. It seems that only one or two cycles need do be added to {π id , π dh , π oe } to form a dominant set. Note that the set is not unique, except for m = 13.

Structure of dominant 1-cycles

One-cycles which outperform {π id , π dh , π oe } are similar in structure. Like π oe , one iteration consists of 2 turns of the cell, but with additional backward sequences (two for 9 ≤ m ≤ 11 and m = 14, two or three for m = 12, three for m = 13). Examples are presented in

A 0 A 3 A 2 A 5 A 8 A 1 A 4 A 7 A 6 A 9 16.00 ≤ p ≤ 3m -1 π dh (a) m = 9 (p * ≈ 15.56) m + 1δ ≤ p ≤ 16.00 π oe 16.00 ≤ p ≤ 18.00 A 0 A 3 A 2 A 5 A 8 A 10 A 1 A 4 A 7 A 6 A 9 18.00 ≤ p ≤ 3m -1 π dh (b) m = 10 (p * ≈ 17.11)
m + 1δ ≤ p ≤ 18.00 π oe 18.00 ≤ p ≤ 18.66

A 0 A 3 A 2 A 5 A 8 A 10 A 1 A 4 A 7 A 6 A 9 A 11 18.67 ≤ p ≤ 3m -1 π dh (c) m = 11 (p * ≈ 18.55) m + 1 ≤ p ≤ 19.00 π oe 19.00 ≤ p ≤ 19.66 A 0 A 3 A 2 A 5 A 8 A 10 A 12 A 1 A 4 A 7 A 6 A 9 A 11 19.67 ≤ p ≤ 21.66 A 0 A 3 A 2 A 5 A 8 A 11 A 10 A 1 A 4 A 7 A 6 A 9 A 12 21.67 ≤ p ≤ 3m -1 π dh (d) m = 12 (p * ≈ 20.09) m + 1 ≤ p ≤ 20.46 π oe 20.47 ≤ p ≤ 23.33 A 0 A 3 A 2 A 5 A 8 A 11 A 10 A 13 A 1 A 4 A 7 A 6 A 9 A 12 * 23.34 ≤ p ≤ 3m -1 π dh (e) m = 13 (p * ≈ 21.54) (*unique) m + 1 ≤ p ≤ 22.0 π oe 22.0 ≤ p ≤ 23.20 A 0 A 3 A 2 A 5 A 8 A 10 A 12 A 14 A 1 A 4 A 7 A 6 A 9 A 11 A 13 23.20 ≤ p ≤ 3m -1 π dh (f) m = 14 (p * ≈ 23.08)

General structure of performant cycles

The experimental results obtained in Section 4.3 suggest that any cycle dominating {π id , π dh , π oe } consists in two forward turns around the cell, similarly to the oddeven cycle, altered by a number of backward sequences A i A i-h . We will call such alterations "waves", referring to their aspects on the cycle graphical representation.

In this section, we define formally such cycles and derive some of their properties.

Two turns...

In the following, unless otherwise specified, m > 8 and (m + 1)δ < p < (3m -1)δ and π refers to a 1-cycle dominating {π id , π dh , π oe } for some (m + 1)δ < p < (3m -1)δ. In this interval, cycle time values for π dh and π oe are given respectively by Equation (4.1) and Equation (4.2). Note that the cycle time of π oe satisfies:

T πoe (p) < 2p (4.6)
Remember (inequality (4.4)) that the total travel time (denoted by ∆ π ) over one iteration of cycle π must be comprised between two and three times the time necessary to circle the cell once:

2(m + 1)δ < ∆ π < 3(m + 1)δ (4.7)
This relation alone is not sufficient to conclude that the robot effectively circles the cell twice. This section aims at showing this is indeed the case; formally, that there is at least one spot where the robot passes exactly twice, both times while traveling in the forward direction.

We use the following notations: for any i ∈ {0, . . . , m}, m π (i) denotes the number of times the robot travels between M i and M i+1 in either direction (forward or backward) during one iteration of cycle π. Similarly, m + π (i) (respectively m - π (i)) denotes the number of times the robot travels forward (respectively backward) from M i and M i+1 . When there is no ambiguity as for the referenced cycle, we omit it and simply use m(i), m + (i) and m -(i).

Note that ∆ π = δ i∈{0,...,m} m π (i). Proof. First, we show that if m(i) = 1 for some i, then π is dominated by π oe or π dh . Case 1. i / ∈ {0, m}. Looking at π's sequence starting with A i , we consider cases depending on the respective positions of A i+1 and A i-1 .

Case 1.1. If A i+1 precedes A i-1 , then T π (p) ≥ 2p > T πoe : processing on machines M i+1 and M i do not overlap, and both require p time units (see Figure 4.5a).

Case 1.2. If A i-1 precedes A i+1 , then (see Figure 4.5b):

• Between the beginning of A i and the end of A i-1 , the robot cannot pass a second time between M i and M i+1 (otherwise m i ≥ 2), hence it has to travel forward between M i+1 and M i , thus circling the whole cell and traveling at least (m + 1)δ.

• Likewise, between the end of A i-1 and the beginning of A i+1 , the robot circles the cell backward, traveling at least mδ.

• Likewise, between the beginning of A i+1 and the beginning of the next iteration, the robot circles the cell forward, traveling at least mδ.

Moreover as the fastest path from M i to M i+1 is forward, and the robots must take the fastest path to join subsequent activities, at least one activity is performed between A i-1 and A i+1 , adding at least 2δ travel time compared to a straight backward route.

Finally, ∆ π ≥ (m + 1)δ + 2mδ + 2δ = 3(m + 1)δ, and π is dominated by π dh .

Case 2. i = 0. Looking at π's sequence starting with A 0 , we consider cases depending on the respective positions of A 1 and A m .

Case 2.1. A m precedes A 1 . This case is similar to Case 1.2; see Figure 4.5c. Case 2.2. A 1 precedes A m . Let A k be the highest activity (largest k) performed between A 0 and A 1 .

Case 2.2.1. k < m -2. Activities higher than A k occur after A 1 and therefore must be performed in decreasing order, otherwise T π (p) ≥ 2p ≥ T πoe (p) (see Figure 4.5d). We have m(0) = 1, m(j) ≥ 3 for 0 < j ≤ k + 1, m(j) ≥ 4 for k + 1 < j < m and m(m) ≥ 3 (see Figure 4.5e). Thus ∆ π ≥ 3(m + 1)δ, and π is dominated by π dh .

Case 2.2.2. k = m-2. Likewise, A m-1 and A m must be performed in decreasing order. m(0) = 1 and m(j) ≥ 3 for 0 < j ≤ m, which leads to ∆ π ≥ (3m + 1)δ. Additionally, as the fastest path from

M m-2 to M 1 is forward (m -2 -1 > m + 1 -(m -2 -1)
), at least one activity is performed between A m-2 and A 1 , adding at least 2δ travel time, leading to ∆ π ≥ 3(m + 1)δ (see Figure 4.5f). Thus π is dominated by π dh .

CHAPTER 4. DOMINANT STRUCTURES FOR LARGE CELLS

Case 2.2.3. k = m -1. We have m(0) = m(m) = 1 and m(j) ≥ 3 for 0 < j < m, thus ∆ π ≥ (3m -1)δ. If A 2 is after A m-1 (Figure 4.5g), then m(2) ≥ 4. Additionally, at least one activity is performed between A m-1 and A 2 , since otherwise the robot would have gone forward from M m to M 2 . This adds an additional 2δ, leading to ∆ π ≥ 3(m + 1)δ. On the other hand, if A 2 takes place before A m-1 , then, the robot travels at least 2mδ between the beginning of A 2 and the end of A 1 , and travels or waits at least p between A 1 and the next unloading of M 1 (see Figure 4.5h). The cycle time (calculated from the beginning of A 2 ) T π (p) is at least 2mδ + p. If p ≥ (m + 3)δ, then T π (p) ≥ 3(m + 1)δ and π is dominated by π dh . Otherwise, (m + 1)δ < p < (m + 3)δ: then, T π (p) ≥ 2p and π is dominated by π dh .

Case 3. i = m. This case is symmetrical to the case where i = 0.

Finally, if π dominates {π oe , π dh } for some p ∈ ](m + 1)δ, (3m -1)δ[, then for all i ∈ {0, . . . , m}, m π (i) ≥ 2. Moreover, inequality (4.7) implies that there exist j ∈ {0, . . . , m} such that m π (j) = 2 (otherwise, ∆ π ≥ 3(m + 1)δ).

Proposition 4.3. For i ∈ {0, . . . , m}, if m π (i) = 2, then m + π (i) = 2 and m - π (i) = 0.
Proof. For the sake in simplicity, we give the proof for i = 0, but it can be adapted to any i in {0, . . . , m}. Let us assume that m + (0) = 1 and m -(0) = 1. This means that cycle does not take advantage of the circular layout of the cell. We consider the cycle sequence starting with A 0 . It can be decomposed into two parts: the part between A 0 and A m , and the rest of the sequence following A m . For any j in {1, . . . , m}, m(j) = 2 only if the 3 following conditions are satisfied:

(i) A j is performed between A 0 and A m (ii) No activity A k with k < j is performed between A j and A m (iii) There is no pair of activities A k , A l such that k < j < l and A k and A l both take place after A m in that order.

In all other cases, m(j) ≥ 4:

• If condition (i) is not satisfied, then the robot travels at least twice forward between M j and M j+1 (once between A 0 and A m and once to perform A j , and twice backwards (once between A m and A j (to get to M j or a previous machine), and once after A j (to get back to the input station).

• Otherwise, if (ii) is not satisfied, the robot travels between M j and M j+1 at least once forward performing A j , once backward between A j and A k , once forward between A k and A m , and once backward after A m .

i -

1 i i + 1 p p (a) Case 1.1. i -1 i i + 1 (b) Case 1.2.
0 1 m -1 m -2 m (f) Case 2.2.2. 0 1 2 m m -1 (g) Case 2.2.3. (A 2 after A m-1 ) 0 1 2 m m -1 p 2mδ (h) Case 2.2.4.(A 2 before A m-1 )

3: cycle

A 0 A 2 . . . A m-2 A m A m-1 A m-3 . . . A 1 (here for m = 10)
• Otherwise, if (iii) is not satisfied, the robot travels between M j and M j+1 at least once forward performing A j , once backward between A m and A k , once forward between A k and A l , and once backward after A l .

As π does not contain any subsequence of consecutive activities, at most m+1 2 activities satisfy these conditions. If at most m+1 2 do so (in particular, this is the case if m is odd), then

T π (p) ≥ 2 m+1 2 δ + 4 m+1 2 δ ≥ 3(m + 1)δ and π is dominated by π dh .
Otherwise, the only possible cycle is π

= A 0 A 2 . . . A m-2 A m A m-1 A m-3 . . . A 1 (see Figure 4.6). Then we have T π ≥ 2 m+1 2 -1 δ + p + 4 m+1 2 -1 δ ≥ 3(m + 1
)δ (as p ≥ (m + 1)δ)), thus π is dominated by π dh . Definition 4.1. Consider i 0 ∈ {0, . . . , m} such that m + i 0 (π) = 2. The robot travels twice between M i 0 and M i 0 +1 : once loaded while performing A i 0 , and once empty. Starting an iteration of the cycle with A i 0 , we define all robot moves from A i 0 included, to the empty travel between M i 0 and M i 0 +1 excluded as constituting the first turn of the cycle. All subsequent moves form the second turn. Each turn entails at least (m + 1)δ units of travel time.

The following Proposition extends Equation (4.3): Proposition 4.4. Two activities A i and A i+1 cannot be performed during the same turn of π in increasing order.

Proof. Let i ∈ {0, m -1} such that A i and A i+1 take place during a same turn in increasing order. Then, T π (p) ≥ 2(m + 1)δ + p ≥ 3(m + 1)δ as p ≥ (m + 1)δ. Thus π is dominated by π dh . In the next two sections, we restrict ourselves to cycles satisfying Proposition 4.3, meaning that there is at least one spot in the cell which the robot crosses exactly twice, both times forward. Graphically, these cycles can be seen as two forward climbs (representing the two turns) altered by "waves" formed by backwards sequences of activities of type A i A i-h . We call h the size of the wave: for example A 6 A 5 is a wave of size 1, and A 7 A 4 a wave of size 3. Intuitively, these sequences, at the cost of an additional travel time, increase the amount of travel between the loading of some machines and their subsequent unloading, thus reducing the waiting time.

GENERAL STRUCTURE OF PERFORMANT CYCLES

Figure 4.7 shows how one wave of size h affects the travel time and waiting times. Compared to π oe , 2(h+1)δ is added to the total travel time by one wave of size h. Recall that d j is the time traveled by the robot between the loading and unloading of machine M j , j ∈ {1, . . . , m}. These values are also affected depending on when machine M j is loaded relatively to the sequence A i A i-h ("under" or "above" in Figure 4.7):

• if M j is loaded before performing A i A i-h , during the same turn ("under"), d j is increased by 2(h + 1)δ.

• if M j is loaded after performing A i A i-h , during the same turn ("above"), d j doesn't change.

• if M j is loaded "under" the sequence A i A i-h , during the other turn, d j doesn't change.

• if M j is loaded "above" the sequence A i A i-h , during the other turn, d j is increased by 2(h + 1)δ.

Number

Note that in order to increase d j by at least 2(h + 1)δ for all j ∈ {1, . . . , m}, it is necessary to add two waves, one on each turn, or one at each extremity of a turn. More generally, for m arbitrarily large, 2n waves of size h are required to increase d j by n(2(h + 1))δ for all j ∈ {1, . . . , m}, adding 4n(h + 1)δ to the total travel time.

Placement

Let i 1 < i 2 ∈ {0, . . . , m}. In order to increase each d j value by at least 2(h + 1)δ with only the sequences A i 1 A i 1 -h and A i 2 A i 2 -h , the indices i 1 and i 2 must verify:

i 2 -i 1 ≤ h + 3 (4.8)
Otherwise, d i 1 +3 is unchanged (see Figure 4.8): if A i 1 takes place on the first turn, then by Proposition 4.4, A i 1 +2 takes place on the first turn, after the first wave, and A i 1 +3 takes place on the second turn before the second wave. Thus the travel between the loading and unloading of M i 1 +3 doesn't contain any of the two waves and is not impacted.

i 1 -h i 1 i 1 + 1 i 1 + 2 i 1 + 3 i 2 -h i 2 (m + 1)δ

More generally, to increase every d j value by at least n(2(h + 1))δ using the sequences A

i 1 A i 1 -h , . . . , A i 2n A i 2n -h with i 1 < i 2 • • • < i 2n , Equation (4.8) must be verified by each pair (i k , i k+1 ) for 1 ≤ k ≤ 2n -1.

Notation

Here, we introduce notations to describe in a compact fashion cycles formed with waves of uniform size h.

For h = 1, the number and position of the waves is sufficient to specify the full activity sequence of the cycle, as by Proposition 4.4 no consecutive activities may take place on the same turn in increasing order, so the only consecutive activities taking place on the same turn are the wave sequences, all the others are alternated. We denote v(i 1 , i 2 , . . . , i n ), the cycle formed with the waves

A i 1 A i 1 -1 , A i 2 A i 2 -1 . . . A in A in-1 .
To build the full expression of the cycle, on can proceed as follows: starting with two empty turns, take the activities in increasing order starting with A 0 . Each activity A i is inserted sequentially into one of the two turns following these rules: if i ∈ {i 1 , . . . i n } then A i is inserted just before A i-1 , on the same turn, otherwise A i is appended to the other turn. For example, on a 10-machine cell, v(3,

7) = A 0 A 3 A 2 A 5 A 8 A 10 A 1 A 4 A 7 A 6 A 9 .
This cycle, represented in Figure 4.12, is studied with more detail in Section 4.5.

For h > 1, the specification of the waves is not sufficient to deduce the complete sequence: we denote by V h (i 1 , i 2 , . . . , i n ) the set of cycles containing waves

A i 1 A i 1 -h , A i 2 A i 2 -h , . . . , A in A in-h .

... And still waters

Graphically, the unfolding in the cell of the cycles considered in this chapter is made of "turbulence zones", where the robot moves are altered by the waves' backward sequences, and "still waters", where the robot behaves as when executing π oe , moving forward and serving one machine in two. Such a decomposition is represented on Figure 4.9, with two still water areas, surrounding one turbulence zone. For machines located in the still water areas, the distance traveled by the robot between the loading and unloading depends solely on the size and number of waves in the turbulence zone. More precisely, for machines in the lower still area loaded during the first turn, and machines in the upper still area loaded during the second turn, this value (d a , represented in blue) is identical, and determined by the waves carried on the first turn. Likewise, for machines in the lower still area loaded during the second turn and machines in the upper still area loaded during the first turn, this value (d b , represented in green) is identical, and determined by the waves carried on the second turn.

If both turns carry the same number and size of waves, then d a = d b , making the cycle structure in these still water areas similar to the one of π oe . In this section, we exploit this similarity to give a lower bound on the cycle time, more precisely on the waiting time.

Ŵ (n, d, p) = 2α(n) -1 α(n) max(0, p -d), where α(n) = n + 1 2
and for n = 0, Ŵ (n, d, p) = 0.

In particular, Ŵ m, (m + 1)δ, p = W πoe (p). More generally, Ŵ (n, d, p) would be the waiting time of a cycle similar to π oe on n machines, with d i = d for all i ∈ {0, . . . , m + 1}. Note that for a given d and p, the function Ŵ (n, d, p) is increasing in n while for a given n and p, Ŵ (n, d, p) is decreasing in d.

The following Proposition uses Ŵ to bound the cycle time of a cycle based on the part that is similar to the odd-even cycle. For convenience, we denote SE i,j (respectively SO i,j ) the ordered sequence of all activities A l with l even (respectively odd), i ≤ l ≤ j. For instance, SE 3,8 = A 4 A 6 A 8 .

Proposition 4.5. Let π be a 1-cycle verifying Proposition 4.3. (i) If there exists i, l, d such that

• π contains both sequences SE i,i+l and SO i,i+l , (ii) More generally, if there exists d, i 1 , i 2 , l 1 , l 2 , with i 2 > i 1 + l 1 , such that

• ∀j ∈ {i + 1, . . . i + l}, d j = d Then W π (p) ≥ Ŵ (l, d, p).
• π contains both sequences SE i 1 ,i 1 +l 1 and SO i 1 ,i 1 +l 1 • π contains both sequences SE i 2 ,i 2 +l 2 and SO i 2 ,i 2 +l 2 • ∀j ∈ {i 1 + 1, . . . i 1 + l 1 } ∪ {i 2 + 1, . . . i 2 + l 1 }, d j = d Then, W π (p) ≥ Ŵ (l 1 + l 2 -1, d, p)
Proof.

(i) Similarly to the proof of π oe 's cycle time, we consider α(l) iterations of the cycle, and follow the path of one part in the cell, from its loading on M i+1 (A i ) during the first iteration up to its unloading from M i+l with A i+l (if l odd), or from M i+l-1 (if l even). Figure 4.10 shows an example, respectively for l = 3 (Figure 4.10a) and l = 4 (Figure 4.10b). Between each consecutive loading and unloading of the same machine, the waiting time is at least max(0, p -d), leading to a total waiting time of at least (2α(l) -1) max(0, p -d) over α(l) iterations.

(ii) A i 2 and A i 2 +1 are not performed during the same turn, so one of them is performed during the same turn as A i 1 +l 1 . If it is A i 2 , the proof is similar to case (i) with l = l 1 + l 2 , following the path of one part from its loading on M i 1 +1 to its unloading from M i 1 +l 1 , then from the loading of M i 2 +1 to its unloading from M i 2 +l 2 (see Figure 4.11a). If not, the proof is similar to case (i) with l = l 1 +l 2 -1, following the path of one part from its loading on M i 1 +1 to its unloading from M i 1 +l 1 , then from the loading of M i 2 +2 to its unloading from M i 2 +l 2 (see Figure 4.11b).

0 i 1 + l 1
If the number/size of waves carried on each turn is different, the cycle might contain π oe -like sequences with alternating d i values (see Figure 4.9, with d a = d b ). Proposition 4.5(i) can be extended to this case: Proposition 4.6.

Let π be a 1-cycle verifying Proposition 4.3. If the following conditions are verified:

• π contains both sequences SE i,i+l and SO i,i+l ,

• ∀j ∈ {i + 1, . . . i + l} with j -i = 1 mod 2, d j = d a • ∀j ∈ {i + 1, . . . i + l} with j -i = 0 mod 2, d j = d b Then W π (p) ≥ max 0, p -d a , p -d b , p -d a + α(l)-1 α(l) (p -d b ) .
Proof. The proof is similar to the proof of Proposition 4.5(i). We follow the path of one part in the cell between A i and A i+l (if l odd) or A i+l-1 (if l even), over α(l) iterations of the cycle. The part is processed on α(l) machines for which d i = d a and α(l) -1 machines for which

d i = d b . If p ≥ max(d a ,

Wavelets (h = 1)

The observations reported in Section 4.3 on the simulations performed for 9 ≤ m ≤ 14 highlighted two types of cycles which outperform {π oe , π dh }, both containing only size-1 waves. The first type contains two waves, and outperforms {π oe , π dh } for every tested value of m. The second type contains 3 waves and appeared to be interesting only for m = 12 and m = 13. In this section, we formalize and generalize these experimental results by defining a new family of cycles, containing only evenly spaced size-1 waves. We study the properties of this family and its dominance over the classical cycles set {π id , π dh , π oe }. Section 4.5.1 presents a direct generalization of the 2-waves type for m machines, and a proof of its cycle time and dominance over {π oe , π dh }. In Section 4.5.2 this form is generalized to an arbitrary number of waves, either even or odd. In section Section 4.5.3, we compare these cycles.

Cycle π 2w

For any m ≥ 9, let us consider the cycle π 2w = v (3,7). More precisely, π 2w is defined as follows:

For m even,

π 2w = A 0 A 3 A 2 A 5 A 8 . . . A 2i . . . A m A 1 A 4 A 7 A 6 A 9 . . . A 2i+1 . . . A m-1
and for m odd,

π 2w = A 0 A 3 A 2 A 5 A 8 A 10 . . . A 2i . . . A m-1 A 1 A 4 A 7 A 6 A 9 A 11 . . . A 2i+1 . . . A m
Similarly to the odd-even cycle, this sequence consists of the robot circling the cell twice, loading one machine in two, but each of the two turns is altered by a backward sequence A i A i+1 . Figure 4.12 shows an example on a 10-machine cell. We call first turn the part of the cycle from A 0 to A m (respectively A m-1 ) for m even (respectively odd), and second turn the rest of the cycle.

Compared to π oe , each wave adds 4δ to the total travel time, but for all i ∈ {0, . . . , m + 1}, d i is increased by at least 4δ, hence we have The simulations described in Section 4.3 showed that for 10 ≤ m ≤ 14, cycle π 2w appears to dominate {π id , π dh , π oe } for some parameter values; by algebraically establishing its cycle time, we prove that this is indeed valid for any m ≥ 9.

∆ π 2w = 2(m + 1)δ + 8δ = 2(m + 5)δ

Proposition 4.7. Cycle time of π 2w

For (m + 1)δ ≤ p ≤ (m + 5)δ + 4 m+7 2 δ, the cycle time of π 2w is:

T π 2w (p) = 2(m + 5)δ + Ŵ (m -8, (m + 5)δ, p)
In particular, this is true for p * , since p * < (m + 5)δ + 4 m+7 The total travel time of π 2w is 2(m + 5)δ; we show that in the first case its waiting time is exactly Ŵ (m -8, (m + 5)δ, p).

• For j = 1 and j ∈ {9, . . . , m}, d j (π 2w ) = d min (π 2w ) = (m + 5)δ, and π 2w contains the four sequences SE 0,1 ; SO 0,1 ; SE 8,m and SO 8,m . As a consequence of Proposition 4.5:

W π 2w (p) ≥ Ŵ (m -8, (m + 5)δ, p)
• To show that W π 2w (p) ≤ Ŵ (m -8, (m + 5)δ, p), we provide a repartition of waiting times between machines so that the sum of the waiting times is Ŵ (m -8, (m + 5)δ, p), and no additional waiting time is necessary.

If p ≤ (m + 5)δ, then no waiting time is necessary.

WAVELETS (H = 1) 71

Let us consider p > (m + 5)δ. Between machines M 10 and M 1 (in a cyclic sense), the cycle behaves in a similar way to π oe on (m -8) machines with d min = (m + 5)δ. We place waiting times on these machines only, similarly to the waiting times of the corresponding odd-even cycle.

More precisely, waiting time are distributed this way for m even (w i being the waiting time at machine M i ):

w i =    0 for 1 ≤ i ≤ 9 p-(m+5)δ α(m-8)
for 10 ≤ i ≤ m and for m odd:

w i =    0 for 2 ≤ i ≤ 9 p-(m+5)δ α(m-8)
for i = 1 and 10 ≤ i ≤ m -The sum of all waiting times is:

2α(m -8) -1 α(m -8) (p -(m + 5)δ) = Ŵ (m -8, (m + 5)δ, p).
-For i = 1 or 10 ≤ i ≤ m: d i = (m + 5)δ, and between the loading and unloading of machine M i the robot waits α(m -8) times -For 2 ≤ i ≤ 9, if M i is loaded during the second turn:

d i = (m + 9)δ,
and between the loading and unloading of machine M i the robot waits α(m -8) -1 times

1 α(m-8) (p -(m + 5)δ).
For this waiting time to be sufficient, the following must be satisfied: In particular one can verify that T π 2w (p * ) < T πoe (p * ). Hence π 2w is not strictly dominated by {π oe , π dh }. In the next section, we introduce a more general family of cycle, including among others π oe and π 2w , and detail their dominance relationships depending on the values of p.

(m + 9)δ + 1 - 1 α(m -8) (p -(m + 5)δ) ≥ p

Generalization: (π nw ) n

In this section, we define and study π nw , a generalization of cycle π 2w formed by placing n waves alternately on each turn, spaced adequately to uniformly increase travel time between subsequent loading and unloading operations. Cycles π nw for various value of n and of the number of machines m are compared in Section 4.5.3, basically showing that cycles π nw with the highest possible values of n perform better.

Formally, for n ≥ 0 and m ≥ 4n -1, we define:

π nw = v(3, 7, . . . , 4i -1, . . . , 4n -1)
For example, π 4w = v (3,7,11,15). For 18 machines, its full expression is:

π 4w = A 0 A 3 A 2 A 5 A 8 A 11 A 10 A 13 A 16 A 18 A 1 A 4 A 7 A 6 A 9 A 12 A 15 A 14 A 17 . In particular, π 0w = π oe .
A representation of π nw for m even (respectively m odd) is shown on Figure 4.14 (respectively Figure 4.15). We call first turn the part of the cycle from A 0 until the robot reaches the output station and second turn the rest of the cycle. The total travel time of π nw is:

∆ πnw = 2(m + 2n + 1)δ
In particular, for m = 4n-1 one has ∆ πnw = 3(m+1)δ. Thus π nw is dominated by π dh for m = 4n -1. Consequently, in the following we only consider m ≥ 4n. As properties of π nw depend on the parity of n, we consider separately both cases; for n even we give an expression of the cycle time; for n odd, a lower bound on the cycle time, and an expression of the cycle time for the special cases m = 4n and m = 4n + 1.

For n even

For n even, π nw satisfies: For p > (m+2n+1)δ, the proof is similar to the one of Proposition 4.7. We use Proposition 4.5 to bound the waiting time, then we provide an adequate waiting time vector to show equality.

For m = 4n, by Proposition 4.5(i) with i = 0, l = 1, d = (m + 2n + 1)δ:

W πnw (p) ≥ Ŵ (1, (m + 2n + 1)δ, p).
For m ≥ 4n+1, by Proposition 4.5(ii) with i 1 = 0, i 2 = 4n, l 1 = 1, l 2 = m-4n, d = (m + 2n + 1)δ: W πnw (p) ≥ Ŵ (m -4n, (m + 2n + 1)δ, p).

WAVELETS (H = 1) 75

To prove the equality, we consider the following waiting time vectors:

w i =    0 for 2 ≤ i ≤ 4n p -(m + 2n + 1)δ for i = 1
for m = 4n

w i =    0 for 1 ≤ i ≤ 4n + 1 p-(m+2n+1)δ α(m-4n) for 4n + 2 ≤ i ≤ m for m ≥ 4n + 2, m even w i =    0 for 2 ≤ i ≤ 4n + 1 p-(m+2n+1)δ α(m-4n) for i = 1 or 4n + 2 ≤ i ≤ m for m ≥ 4n + 1, m odd
In each case, the sum of all waiting times is exactly:

Ŵ max(1, m -4n), (m + 2n + 1)δ, p .
Noticing that:

• for machines M i , 2 ≤ i ≤ 4n + 1, loaded during the first turn:

d i = (m + 2n + 1)δ,
• for machines M i , 2 ≤ i ≤ 4n + 1, loaded during the second turn:

d i = (m + 2n + 5)δ,
And using the same arguments as in Proposition 4.7, one can verify that these waiting times are sufficient for p ≤ (m + 2n + 1)δ + 4 m-4n+1 2 δ.

As (m + 2n + 1)δ + 4 m-4n+1 2 δ ≤ (3m -1)δ, Proposition 4.8 does not give the exact cycle time over the entire considered interval ](m + 1)δ, (3m -1)δ[. However, once the cycle time reaches 3(m + 1)δ, the corresponding cycle is dominated by π dh and need not be considered anymore. Let us define the value of p for which the lower bound given by Proposition 4.8 reaches 3(m + 1)δ: Definition 4.3. For n even, we call p * n the value of p such that

2(m + 2n + 1)δ + Ŵ max(1, m -4n), (m + 2n + 1)δ, p * n = T π dh (p * n ) = 3(m + 1)δ.
For m ≥ 4n + 1, its value is:

p * n = (m + 2n + 1)δ + α(m -4n) 2α(m -4n) -1 (m + 1 -4n)δ CHAPTER 4

. DOMINANT STRUCTURES FOR LARGE CELLS

The following corollary states that, for m ≥ 4n + 1, this value p * n falls within the interval for which the exact cycle time of π nw is given by Equation (4.11). This means that the exact cycle time is really known for the values of p for which it is worth knowing; it will be useful to compare π nw to other cycles. .

Proof
α(m -4n) 2α(m -4n) -1 (m + 1 -4n)δ ≤ (m + 1 -4n)δ ≤ 4 m + 4n -1 2 δ (4.13)
we get:

p * n = (m + 2n + 1)δ + α(m -4n) 2α(m -4n) -1 (m + 1 -4n)δ ≤ (m + 2n + 1)δ + 4 m + 4n -1 2 δ
hence the cycle time of π nw over ](m + 1)δ, p * n [ is given by Equation (4.11).

For n odd

Consider π nw with n odd. In this case, one more wave is carried on the first turn ( n-1 2 + 1 waves) than on the second one ( n-1 2 waves). As a consequence, machines in the upper still waters area whose processing takes place between the first and second turn have a smaller d i value than those active between the second and the first turn (see Figure 4.15). If m is large enough so that the cell contains both types of machine (m ≥ 4n + 2), then we have d min (π nw ) = (m + 2(n -1) + 1)δ, which is the same d min value as π (n-1)w , but with more total travel time. However, if m is small enough that there is no machine to load on the first turn after the last wave (m ≤ 4n + 1), then d min (π) = m + 2(n + 1) + 1. Remember from simulations presented in Section 4.3 that contrary to π 2w which appears to consistently dominate {π id , π dh , π oe } for some p for 9 ≤ m ≤ 14, the cycle π 3w appears to be interesting for m = 12 and m = 13 but not m = 14, suggesting that π nw with n odd may be dominated when m ≥ 4n + 2. The following proposition gives a lower bound of the cycle time for m ≥ 4n + 2, which will be used in Section 4.5.3 to show that it is indeed the case. For the case where m ≤ 4n+ 1, an exact expression of the cycle time is given later by Proposition 4.10 Proposition 4.9. Lower bound for the cycle time of π nw with n odd and m ≥ 4n+2 For m ≥ 4n + 2 and n odd, the cycle time of π nw verifies:

T πnw (p) ≥2(m + 2n + 1)δ + max 0, p -(m + 2n -1)δ, p -(m + 2n -1)δ + α(m -4n -1) -1 α(m -4n -1) p -(m + 2n + 3)δ (4.14)
Proof. For m ≥ 4n + 2, we have d min (π nw ) = (m + 2(n -1) + 1)δ. More precisely, for i > 4n + 1 and i even, d i = (m + 2(n -1) + 1), while for i > 4n + 1 and i odd, d i = (m + 2(n + 1) + 1) (see Figure 4.15).

CHAPTER 4. DOMINANT STRUCTURES FOR LARGE CELLS

Using Proposition 4.6 with i = 4n + 1, l = (m -4n -1), d a = (m + 2n -1)δ, d b = (m + 2n + 3)δ, we get:

W πnw (p) ≥ max 0, p -(m + 2n -1)δ, p -(m + 2n -1)δ + α(m -4n -1) -1 α(m -4n -1) p -(m + 2n + 3)δ
Using this bound on the cycle time, the following corollary precise a sufficient condition on p under which π nw is dominated by π dh : Corollary 4.2. For m ≥ 4n + 2 and n odd, if

p ≥ m + 2n + 1 + α(m -4n -1) 2α(m -4n -1) -1 (m + 1 -4n) - 2 2α(m -4n -1) -1 then T πnw (p) ≥ 3(m + 1)δ (and therefore π nw is dominated by π dh ).
Proof. Direct consequence of Equation (4.14).

Recall that for m ≤ 4n, π nw is dominated as its total travel time is greater than 3(m + 1)δ. For m = 4n and m = 4n + 1, the following proposition gives an expression of the cycle time.

T πnw (p) = 2(m + 2n + 1)δ + max 0, 2n n + 1 (p -(m + 2n + 3)δ) (4.15)
Proof. For m = 4n and m = 4n + 1, as no machine is loaded after performing A 4n-1 A 4n-2 during the same turn, d min (π nw ) = (m+2(n+1)+1)δ. More precisely,

d i = (3m -2)δ (if m = 4n) or d i = (3m -3)δ (if m = 4n + 1) for all i ∈ {3, 7
w i =    0 for i = 2 mod 4, i ∈ {1, . . . , m} 2(p-(m+2n+3)δ) n+1 for i = 2 mod 4, i ∈ {1, . . . , m}
The sum of all waiting times is 2n n+1 (p -(m + 2n + 3)δ), and during each processing, waiting is performed n+1 2 times, covering all the necessary waiting time.

Dominance relations within (π nw ) family

In this section, we draw the consequences of Propositions 4.8 to 4.10 in terms of dominance between members of (π nw ) 1≤n≤ m 4 , for any m > 8. We show that at most 2 of them (depending on the value of m), along with {π id , π dh , π oe }, are sufficient to dominate the entire family. As in the rest of the section, we only consider (m + 1)δ < p < (3m -1)δ, as other cases are already solved (see Section 4.2). We consider n ≥ 0 odd and m > 4n + 2. A lower bound on π nw is given by Equation (4.14).

• For (m + 1)δ < p ≤ (m + 2n -1)δ, one has T πnw (p) ≥ 2(m + 2n + 1)δ. Thus,

T πnw (p) -T πoe (p) ≥ 4nδ - 2α -1 α (p -(m + 1)δ) ≥ 4nδ - 2α -1 α 2nδ ≥ 0
and hence π nw is dominated by π oe .

• For (m + 2n -1)δ < p < (m + 2n + 3)δ,

T πnw (p) ≥ 2(m + 2n + 1)δ + p -(m + 2n -1)δ Thus, T πnw (p) -T πoe (p) ≥ 2n + 1 -α α p + α -1 α mδ + 3α -1 α δ
As p < (m + 2n + 3) and α > 1, we get

T πnw (p) -T πoe (p) ≥ 2n + 2 α ≥ 0
Here again, π nw is dominated by π oe .

• For p ≥ (m + 2n + 3)δ,

T πnw (p) ≥ 2(m+2n+1)δ+p-(m+2n-1)+ α(m -4n -1) -1 α(m -4n -1) p-(m+2n+3)δ
We can verify that

p * ≥ m + 2n + 1 + α(m -4n -1) 2α(m -4n -1) -1 (m + 1 -4n) - 2 2α(m -4n -1) -1 Therefore by Corollary 4.2, T πnw (p * ) ≥ 3(m + 1)δ = T πoe (p * ).
T πnw > T πoe for both p = m + 2n + 3 and p = p * , and the cycles T πnw and T πoe are both linear in p over [m + 2n + 3, p * ]. Thus, T πnw ≥ T πoe over the whole interval [m + 2n + 3, p * ].

Over [p * , (3m -1)δ], one has T πnw ≥ 3(m + 1)δ ≥ T π dh .
Thus, π nw is dominated by {π oe , π dh }.

WAVELETS (H = 1)

81 π nw and π (n+2)w with n even We consider n ≥ 0 even and m > 4(n + 2) (so that π nw and π (n+2)w are both defined and not necessarily dominated by {π oe , π dh }) and compare the cycle times of π nw and π (n+2)w .

• For p ≤ (m + 2n + 1)δ, there is no waiting time for any of the two cycles:

T πnw (p) = 2(m + 2n + 1)δ and T π (n+2)w (p) = 2(m + 2n + 5)δ, so T πnw (p) ≤ T π (n+2)w (p) and π nw dominates π (n+2)w .

• For (m + 2n + 1)δ < p ≤ (m + 2n + 5)δ, waiting is required only for cycle π nw .

The waiting time of π nw is 2α(m-4n)-1 α(m-4n) (p-(m+2n+1)δ). As p ≤ (m+2n+5) this waiting time is smaller than 8δ, which is the amount of extra travel time required by π (n+2)w ; thus, π nw dominates π (n+2)w .

• For (m+2n+5)δ < p ≤ p * n , waiting is required for both cycles. Noticing that, for any number β, one has 2β-1

β = 2 -1 β , and that α(m -4n) = α(m) -2n (similarly, α(m -4(n + 2)) = α(m) -2(n + 2)
), the cycle times difference simplifies to:

T πnw (p) -T π (n+2)w (p) = 4 (α(m) -2(n + 2))(α(m) -2n) (p -(m + α(m) + 1)δ)
Note that as m ≥ 4(n + 2), one has (m + α(m) + 1)δ ≥ (m + 2n + 5)δ, and that p * n+2 ≥ p * n . Thus, we can split the values of p in 4 domains according to the relative performance of the cycles π nw , π (n+2)w and π dh :

• for (m + 1)δ < p ≤ (m + α(m) + 1)δ we have T πnw ≤ T π (n+2)w < T π dh , hence π nw dominates π (n+2)w (and both dominate π dh ),

• for (m + α(m) + 1)δ < p < p * n , we have T π (n+2)w < T πnw < T π dh , hence π (n+2)w dominates π (n)w (and both dominate π dh ).

• for p * n ≤ p < p * n+2 , by Corollary 4.1, we have T π (n+2)w < T π dh ≤ T πnw , hence π (n+2)w dominates π (n)w (and π dh )

• for p ≥ p * n+2 , both π nw and π (n+2)w are dominated by T π dh Note that the threshold value of p from which π (n+2)w starts outperforming π nw does not depend on n, and that p * n is increasing in n. So, for a given m, we get that among all possible cycles π nw with n even, π oe (π 0w ) is the best one for (m + 1)δ < p < (m + α(m) + 1)δ, and π m-1

4 w (highest possible value of n) is the best one for (m + α(m) + 1)δ < p ≤ p * m-1 4
.

CHAPTER 4. DOMINANT STRUCTURES FOR LARGE CELLS

π nw and π (n-1)w with n odd and m = 4n

Consider n odd and m = 4n. By Proposition 4.10, for p ≤ ( 3 2 m + 3)δ, T πnw = (3m + 2)δ. In particular, p * ≤ ( 3 2 m + 3)δ thus T πnw (p * ) = (3m + 2)δ < 3(m + 1)δ = T πoe (p * ) = T π dh (p * ) so contrary to the case where m ≥ 4n + 1, the cycle π nw is not dominated by {π oe , π dh }. Let us now compare π nw to π (n-1)w ; as m = 4n, the cycle time of the latter, given by Proposition 4.8, simplifies to

T π (n-1)w (p) = (3m -2)δ + max 0, 3 2 p - 3 2 m -1 δ Thus, for p ≤ ( 3 2 m + 5 3 )δ, one has T π (n-1)w (p) ≤ T πnw (p), while for ( 3 2 m + 5 3 )δ ≤ p ≤ 3 2 m + 3)δ, one has T πnw (p) ≤ T π (n-1)w (p).
For p ≥ ( 3 2 m + 3)δ, by Corollary 4.1 the cycle π (n-1)w is dominated by π dh , so we do not consider it.

T πnw (p * ) = (3m + 1)δ < 3(m + 1)δ = T πoe (p * ) = T π dh (p * )
Let us compare π nw to π (n-1)w . As m = 4n + 1, the cycle time of the latter, given by Proposition 4.8, simplifies to

T π (n-1)w (p) = 3(m -1)δ + max 0, 5 3 p - 3 2 (m -1) δ
Thus, for p ≤ 3 2 (m + 1)δ, one has T π (n-1)w (p) ≤ T πnw (p), while for

3 2 (m + 1)δ ≤ p ≤ ( 3 2 m + 5 2 )δ, T πnw (p) ≤ T π (n-1)w (p). Note that 3 2 (m + 1)δ < (m + α + 1)δ. For p ≥ ( 3 2 m + 5
2 )δ, by Corollary 4.1, π (n-1)w is dominated by π dh , so we do not consider it.

Putting everything together

For n odd and m ≥ 4n + 2, or n even and m = 4n, the cycle π nw is dominated by {π oe , π dh }. In other cases, π nw outperforms both π oe and π dh for values of p close to p * . Using results of this section as well as Corollary 4.1 and Corollary 4.2, we can deduce the best 1-cycle among {π id , π dh , π oe } ∪ (π nw ) n for any instance 2 . For any given m, only 4 or 5 cycles are enough to cover all possible values of p; these results are summed up by Proposition 4.11. Proposition 4.11. For m > 8, the best 1-cycles within {π id , π dh , π oe } ∪ (π nw ) n≤ m 4 for (m + 1)δ ≤ p ≤ (3m -1)δ are given by the following:

• If m = 4 mod 8 (matches the case n odd and m = 4n)

(m + 1)δ ≤ p ≤ ( 3 2 m + 1)δ π oe ( 3 2 m + 1)δ ≤ p ≤ ( 3 2 m + 5 3 )δ π ( m 4 -1)w ( 3 2 m + 5 3 )δ ≤ p ≤ ( 3 2 m + 7 2 + 2 m )δ π ( m 4 )w ( 3 2 m + 7 2 + 2 m )δ ≤ p ≤ (3m -1)δ π dh (by Corollary 4.3)
• If m = 5 mod 8 (matches the case n odd and m = 4n + 1)

(m + 1)δ ≤ p ≤ 3 2 (m + 1)δ π oe ( 3 2 m + 1 -1 2m )δ ≤ p ≤ ( 3 2 m + 7 2 + 4 m-1 )δ π ( m-1 4 )w ( 3 2 m + 7 2 + 4 m-1 )δ ≤ p ≤ (3m -1)δ π dh (by Corollary 4.3) • Else (m + 1)δ ≤ p ≤ (m + α + 1)δ π oe (m + α + 1)δ ≤ p ≤ p * 2 m-1 8 π (2 m-1 8 )w p * 2 m-1 8 ≤ p ≤ (3m -1)δ π dh (by Corollary 4.1) with α = m+1 2 and p * 2 m-1 8 = (m + 4 m-1 8 + 1)δ + α-4 m-1 8 2α-8 m-1 8 -1 (m + 1 -8 m-1 8 )δ.
Notice that 2 m-1

8
is the largest possible even number n such that m ≥ 4n + 1.

In particular for 9 ≤ m ≤ 14, this is consistent with the observations presented in Table 4.3, which indicated {π id , π oe , π dh , π 2w } as a dominant set for 9 ≤ m ≤ 11 and m = 14, respectively {π id , π dh , π oe , π 2w , π 3w } for m = 12 and {π id , π dh , π oe , π 3w } for m = 13.

Smooth Sea or Heavy Swell ?

In Section 4.5, we presented a family of cycle, (π nw ), formed using regularly disposed size-1 waves (sequences A i A i-1 ). Intuitively, the waves reduce the waiting

CHAPTER 4. DOMINANT STRUCTURES FOR LARGE CELLS i i -1 i -2 Figure 4.17: Sequence A i A i-2
time by increasing the travel time occurring between the loading and unloading of machines (d i ) (and thus the necessary waiting time) at the cost of an overall increase of the total travel time. The regular spacing of the waves means that d i values are affected uniformly, which makes sense in balanced cells, where all machines have the same processing time. We showed that the trade-off between augmentation of the travel time and reduction of the waiting time is adequate for members of this family to outperform {π id , π dh , π oe } for specific values of p. Moreover, for 9 ≤ m ≤ 15, simulations suggest that a dominant set within 1-cycles can be formed using only {π id , π dh , π oe } and a couple of cycles from (π nw ).

Could cycles similar in structure, but formed with larger waves (sequences A i A i-h with h > 1), become interesting for larger value of m? Size-2 waves can be easily dismissed by the following proposition: Proposition 4.12. Any cycle containing a size-2 wave (sequence

A i A i-2 ) is dom- inated by π oe .
Proof. If a cycle contains the sequence A i A i-2 , then activity A i-1 is comprised between A i-2 and A i in a cyclic sense (see Figure 4.17). Therefore, the cycle time is at least 2p (at least p between A i-2 and A i-1 and at least p between A i-1 and A i ), which is larger than the cycle time of π oe .

However, this proof cannot be extended for h > 3. In this section, we use the bound defined by Proposition 4.5 to show that cycles formed similarly to members of (π nw ) with waves of size h > 3 are dominated.

Remember from Section 4.4 that potentially interesting cycles are formed by two turns and a number of waves, and may as such be decomposed in turbulence zones and still waters areas, which are similar in structure to the odd-even cycle (see Figure 4.9). Proposition 4.5 uses this decomposition to formulate a bound on the waiting time of a given cycle, Ŵ (l, d, p). This bound depends on the size of the still waters areas (l) and the time travelled between the loading and unloadings of machines located in this area (d). Basically, if two cycles space out successive 4.6. SMOOTH SEA OR HEAVY SWELL ?

85 m + 1 + 2(h + 1) m + 1 + 2(h + 1) m + 1 + 2(h + 1) m + 1 + 2(h + 1) 0 m + 1 l 1 h + 1 ≤ 2 h + 1 l 2 Figure 4.18: Representation of a cycle in V h (i 0 , i 1 )
loadings and unloadings similarly (same value for d), then the one with the largest still water area (largest value of l), has the largest bound on its waiting time.

For cycles π nw with n even, this bound is tight (Proposition 4.8). Thus π nw performs at least as well as any cycle sharing the same value for d and l, and better for cycles sharing the same value for d and a larger value for l. For example, π 2w = v(3, 6) performs at least as well as v (5,8) and better than v (3,5) or v (5,7).

In the following, using this bound on the waiting time, we show that cycles formed with an even number of size-h waves with h > 2, satisfying Equation (4.8) for every consecutive pair of waves, are always dominated by a member of (π nw ).

To better understand the idea, we first consider cycles with only 2 waves, for h = 3 and h = 4. We show that such cycles are dominated by π 4w . Then, we apply the same reasoning to cycles with an arbitrary even number of waves of size h, respectively for h odd and h even.

First, recall that for cycles π nw with n even we have:

W πnw (p) = Ŵ (m -4n)δ, (m + 2n + 1)δ, p (4.16)
Let π ∈ V h (i 0 , i 1 ) with h > 2 so that i 1 -i 0 -h ∈ {1, 2}. The cycle π is defined for m ≥ i 1 + h; however it is dominated by π dh for m ≤ 2(h + 1). Indeed, the total travel time of π is ∆ π = 2(m+1)δ+4(h+1), which is greater than T π dh = 3(m+1)δ if m ≤ 2(h + 1). Thus, we only consider the case where m > 2(h + 1). For all machines M i with i ≤ i 0 -h or i ≥ i 1 , d i = (m + 1)δ + 2(h + 1)δ (see Figure 4.18). Then, by Proposition 4.5, we have:

W π (p) ≥ Ŵ (m -2(h + 3))δ, (m + 1 + 2(h + 1))δ, p (4.17) h = 3 For h = 3, consider π ∈ V 3 (i 0 , i 1 ) so that i 1 -i 0 -3 ∈ {0, 2}.
Let us compare π with π 4w , the cycle formed by four size-one waves. We assume m ≥ 16

(otherwise π is dominated by π dh ), thus π 4w is defined. The travel time is identical for both cycles ∆ π (p) = ∆ π 4w (p) = 2(m + 1)δ + 16δ. The additional spacing between loading and unloading for machines in the still waters areas is the same for both cycles, but the the size of these areas is larger for π nw (same value for d, larger value for l). Formally, by Equation (4.17), the waiting time of π satisfies

W π (p) ≥ Ŵ (m -12)δ, (m + 9)δ, p
while by Equation (4.16), the waiting time of π 4w is exactly

W π 4w (p) = Ŵ (m -16)δ, (m + 9)δ, p thus, as Ŵ (l, d, p) is increasing in l, W π (p) ≥ W π 4w (p). Finally π is dominated by π 4w . h=4 Now for h = 4, consider π ∈ V 4 (i 0 , i 1 ) so that i 1 -i 0 -4 ∈ {0, 2}. Its travel time is T π (p) = 2(m + 1)δ + 20δ
. This case is more complicated than the previous one, as there is no cycle in the (π nw ) family as easily comparable to π: π 4w has less overall travel time, but also adds less travel between subsequent loadings and unloadings, while π 6w adds more travel between subsequent loadings and unloadings, but also has more overall travel time.

To show that π is indeed dominated by π 4w , we show that the potential increase in waiting time is compensated by the gain in overall travel time.

By Equation (4.17), the waiting time of π satisfies

W π (p) ≥ Ŵ (m -14)δ, (m + 11)δ, p
As Ŵ (l, d, p) is increasing in l, we get

W π (p) ≥ Ŵ (m -16)δ, (m + 11)δ, p
By expanding the expression of Ŵ , we get

W π (p) -W π 4w (p) ≥ Ŵ (m -16)δ, (m + 11)δ, p -Ŵ (m -14)δ, (m + 9)δ, p ≥ -2 2α(m -16) -1 α(m -16) δ ≥ -4δ
As ∆ π -∆ π 4w = 4δ, T π -T π 4w ≥ 0 and π is dominated by π 4w . We can extend this reasoning to the case of n wave of arbitrary size h > 2 with n even; this is the following proposition: Proposition 4.13. Let h > 2, n even, and

i 0 < i 1 < • • • < i n-1 ∈ {0, . . . , m + 1} so that for each q ∈ 1, n -1 , i q -i q-1 -h ∈ {0, 2}. Let π ∈ V h (i 0 , . . . , i n-1 ).
If m < 2n(h + 1)δ then π is dominated by π dh ; otherwise, π is dominated by π (n h+1 2 )w .

Proof. The travel time of π is ∆ π = 2(m + 1)δ + 2n(h + 1). If m < 2n(h + 1)δ, then ∆ π ≥ 3(m + 1)δ, thus π is dominated by π dh . Now, we assume m ≥ 2n(h + 1)δ. The cycle π (n h+1

2

)w is then defined. Its travel and waiting time, depending on the parity of h are given respectively by:

∆ π ( n h+1 2 ) w = 2(m + 1)δ + 2n(h + 1)δ for h odd (4.18) ∆ π ( n h+1 2 ) w = 2(m + 1)δ + 2nhδ for h even (4.19) W π ( n h+1 2 ) w = Ŵ (m -2n(h + 1))δ, (m + n(h + 1) + 1)δ, p) for h odd (4.20) W π ( n h+1 2 ) w = Ŵ (m -2nh)δ, (m + nh + 1)δ, p for h even (4.21)
For all machines M i with i ≤ i 0 -h or i ≥ i n-1 , one has d i = (m+1)δ+2(h+1)δ. Then, by Proposition 4.5, we have:

W π (p) ≥ Ŵ (m -n(h + 3))δ, (m + 1 + n(h + 1))δ, p (4.22)
For h odd, ∆ π = ∆ π ( n h+1

2

) w . Let us compare the waiting time of both cycles.

As h > 2, we have (m -n(h + 3))δ < (m -2n(h + 1))δ, thus as Ŵ (l, d, p) is increasing in l, W π ≥ W π ( n h+1

2

) w , and π is dominated by π (n h+1 2 )w . For n even, one has ∆ π -∆ π ( n h+1

2

) w = 2nδ. Let us show that W π -W π ( n h+1 2 ) w ≥ -2nδ. As h > 2, one has (m-n(h+3))δ < (m-2n(h+1))δ.
Thus as Ŵ (l, d, p) is increasing in l, one has:

W π (p) ≥ Ŵ ((m -2nh)δ, 2(m + 1 + n(h + 1))δ, p).
From this, expanding the expression of Ŵ , we get (with β = α(m -2nh)):

W π -W π ( n h+1 2 ) w ≥ - 2β -1 β nδ ≥ -2nδ Thus T π -T π ( n h+1
2

) w ≥ 0 and π is dominated by π (n h+1 2 )w .

A conjecture on the best 1-cycle problem

In Section 4.5, we defined and studied a family of 1-cycles, (π nw ). The sequence of these cycles is formed of two forward turns around the cell, regularly altered by backwards sequences (waves) A i A i-1 , disposed regularly so as to increase d i values at each machine without creating discrepancies. We showed that cycles in this family outperforms the three classical cycles {π id , π dh , π oe } for adequate instances. In Section 4.6, we consider cycles with the same regular structure, but with larger waves For m small enough (m ≤ 11), the number and size of possible waves of 1-cycles can be completely described with rather few conditions. Thus, in this case, we can conclude on the validity of the conjecture. From m > 12, the conditions are more tricky to describe. Proof. The case for m ≤ 8 has been settled in Chapter 3, so we consider 8 ≤ m ≤ 11.

(A i A i-h with h ≥ 2),
Let π be a 1-cycle such that for some p ∈ ](m + 1)δ, 3(m + 1)δ[, T π (p) < min(T πoe (p), T π dh (p)). The travel time of π must be strictly less than 3(m + 1)δ. As π cannot contain any size-two waves, π can contain either 1 size-1 wave (then ∆ π = (2(m + 1) + 4)δ), 2 size-1 waves (∆ π = (2(m + 1) + 8)δ), 1 size-3 wave (∆ π = (2(m + 1) + 8)δ).

Case 1: π contains 1 size-1 wave (there exists i such that π = v(i)). The lower bound of π 1w , given by Equation (4.14) also applies to π, thus we can apply the same reasoning to show that π is as well, dominated by {π oe , π dh }.

Case 2: π contains 1 size-3 wave (there exists i such that π ∈ V 3 (i)).

We Case 3: π contains 2 size-1 wave (there exists i, j such that π = V 1 (i, j)).

If j -i-1 ∈ {0, 2}, then by Proposition 4.5 W π (p) ≥ Ŵ (m-8, (m+5)δ, p) = W π 2w , thus π is dominated by π 2w . Otherwise, we have d min (π) = (m + 1)δ, thus T π (p) ≥ 2(m + 1)δ + 8δ + (p -(m + 1))δ: similarly to Case 2, π is dominated by {π oe , π dh }.

If Conjecture 4.1 is valid, then the best 1-cycles for m ≥ 8 are given by Proposition 4.11. As an instance of the problem is given by (m, p, δ), this would make the best 1-cycle problem solvable in linear time (thus polynomial).

Another interesting consequence would be the performance ratio of the classical cycles {π id , π dh , π oe } within 1-cycles. Compared to cycles in the family (π nw ), these three cycles are easy to describe and understand by an human operator, whereas π nw cycles do not seem to greatly improve the cycle time. Let R be the performance ratio of {π id , π dh , π oe } within {π id , π dh , π oe } ∪ (π nw ):

R = min(T π dh , T πoe , T π id ) min n (T π dh , T πoe , T π id , T πnw ) (4.23)
As the slope of π oe is 2 and the slope of any cycle π nw is at most 2, this ratio is worst for p = p * , where T πoe (p) = T π (p) = 3(m + 1)δ.

Conclusion

In this chapter, we addressed the best 1-cycle problem in arbitrarily large cells (m > 8, the case m ≤ 8 being settled in Chapter 3). Though known to be NP-hard for circular regular cells, the complexity of this problem is still open in the balanced case. Observations of simulations up to m ≤ 14 showed that 1-cycles non-dominated by {π id , π dh , π oe } appear to follow a constrained structure, which we subsequently investigated. We first showed that non-dominated cycles necessarily take advantage of the circular configuration, in a similar way to the odd-even cycle π oe : during one iteration, the robot circles the cell twice, forward, with scattered backward sequences ("waves") along the way which allow to decrease the waiting time at some machines while increasing the overall travel time. This leaves the question of the size, number, and placement of the waves in order to optimize the trade-off between waiting and travel time. Generalizing our observations, we were able to define and fully study a family of cycles, (π nw ) whose members outperform the classical cycles {π id , π dh , π oe } under the right conditions, formed with small, regularly disposed waves. We also showed that similar cycles formed using larger waves are dominated.

This led us to conjecture on the dominance of this family, alongside with the classical cycles {π id , π dh , π oe }, over 1-cycles. If proven true, this would allow to settle the best 1-cycle problem in circular regular balanced cell in polynomial time. The main step to prove this conjecture for any m would be to rule out cycles with unevenly disposed waves (formally, not satisfying Equation (4.8)), or unevenly combining several wave sizes; however, for small enough cells, the low number of possibilities allows to settle it completely, thus describing the optimal 1-cycles for m ≤ 11 machine circular regular balanced robotic cells.

Chapter 5 A Greedy Approach for a Rolling Stock Management Problem using Multi-Interval Constraint Propagation -ROADEF/EURO Challenge 2014

This chapter, a joint work with Hugo Joudrier, presents our contribution to the ROADEF/Challenge 2014. The competition gathered 37 teams from 20 countries for an industrial problem proposed by the french railway transportation company. We won the first prize in the junior category (see Figure 5.1) and ended up fourth in the overall ranking 1 . This chapter reproduces the resulting paper, published in Annals of Operation Research in June 2017 [START_REF] Joudrier | A greedy approach for a rolling stock management problem using multi-interval constraint propagation[END_REF]. Other contributions to the competition include [START_REF] Buljubašić | Two-phase heuristic for sncf rolling stock problem[END_REF][START_REF] Catusse | Roadef Challenge 2014: A Modeling Approach, Rolling stock unit management on railway sites[END_REF][START_REF] Geiger | Multi-attribute assignment of trains to departures in rolling stock management[END_REF].

Introduction

In this chapter, we present our approach of the Rolling Stock Unit Management problem presented in the ROADEF/EURO Challenge 2014 [START_REF] Ramond | Trains don't vanish ! ROADEF EURO 2014 Challenge Problem Description[END_REF]. This problem combines in a single formulation various sub-problems of rolling stock management, such as assignment of trains to departures, platform assignment, routing inside the station, planning of maintenance operations... We propose a greedy algorithm to build an initial solution, allowing an incomplete coverage of arrivals and departures. This solution could serve as a basis for an optimization algorithm. Compared to the proposed problem, we make some simplifications by forbidding maintenance, junction and disjunction operations (note that train convoys might be used as such), which limits the number of coverable departures. Our solution is based on a greedy progressive assignment algorithm to assign arrivals (and corresponding trains) to departures, and a routing algorithm using multi-interval constraint propagation to prevent conflicts with already scheduled trains while keeping as much flexibility as possible.

The rest of this chapter is organized as follows: Section 5.2 presents a simplified model of the rolling stock management problem presented in the ROADEF/EURO Challenge 2014. Section 5.3 describes the pre-processing phase and the model used to represent the structure of the station. Section 5.4 details the multiinterval routing algorithm, while Section 5.5 describes the general assignment procedure. Note that the assignment problem is not treated as a whole, separately from the routing problem, but progressively. Finally Section 5.6 presents an overview of the results and some perspectives. In the following, we will use the concepts and notations introduced by Ramond and Nicolas (2014) (available at https://hal.archives-ouvertes.fr/hal-01057324/file/Challenge_ sujet_phaseFinale_140224.pdf).

Simplified model

The original formulation, as presented by [START_REF] Ramond | Trains don't vanish ! ROADEF EURO 2014 Challenge Problem Description[END_REF], aimed at treating the rolling stock management problem as a whole, integrating constraints and costs of various nature. Focusing mainly on the routing constraints, we chose The original industrial problem consists in handling trains within a station over a biweekly planning horizon, by deciding their route and schedule inside the station, and assigning them to compatible departures. A station is composed of resources of several types (track-groups, single tracks and yards for parking, maintenance facilities for performing maintenance, platforms for arrival and departures), linked by gates. Routing of the trains inside the station must respect the length and capacity of the resources, as well as the trains' order on the resources and train/resource compatibility constraints. To be allowed to circulate, trains must be submitted to regular maintenance. Therefore, a train might be assigned to a departure only if it has enough time and mileage left before a maintenance is required for the journey. Maintenance operations can be performed in the stations on appropriate resources, at a cost. Some arrivals (joint arrivals) are composed of several trains joined together; likewise, some departures (joint departures) must be satisfied by several joint trains. Convoys of several joint trains might be formed (respectively separated) by performing junction and disjunction operations.

The two main simplifications that were made are described below. Their main consequence is to avoid modifying characteristics of the trains in the solution.

• Not performing maintenance operations. This choice simplifies the assignment decision process: the compatibility of a given train with a given departure depends only on the instance data (including the time / distance remaining before maintenance), and not on the choice to perform maintenance on it.

• Not performing junction nor disjunction operations. That way, trains can be treated as immutable convoys from their arrivals to their departure. A convoy might be formed of a single train, or of several trains coming from a joint-arrival, which might then satisfy a joint-departure.

In this section we first extend the notations defined by Ramond and Nicolas (2014). Then, we use these new notations to formalize our simplified model.

Definitions Definition : Convoys

A convoy v is defined by a set of trains t in T . We note V the set of all the convoys.

V := P (T ) (5.1) where P is the power set operator. The length and size of a convoy v in V can be accessed with:

size(v) = #v (5.2) length(v) = t∈v length(t) (5.3)
We also define V + , the set of convoys actually used in the solution.

Definitions : About arrivals and departures

As our model treats convoys and not individual trains, joint arrivals (respectively joint departures) can be treated as one single arrival (respectively departure). Thus, we work with a set of extended arrivals (respectively departures), defined in this section. An element of this set is either a unitary arrival (an arrival which is not a member of a joint arrival), or a joint arrival (a set of arrivals joint together, treated as a single element).

Let U arr be the set of unitary arrival in opposition with J arr the set of jointarrivals (and similarly the set of unitary departures). Similarly, a value Comp(v, a) ∈ {0, 1} is defined to express compatibility between a convoy v ∈ V and an arrival a ∈ ExtArr.

Similarly, for each convoy v ∈ V and resource r ∈ R, Comp(v, r) ∈ {0, 1} expresses the compatibility of all trains of v with the resource r.

Definition : Connectors

Connectors are couples of gates, representing transition between resources. Using this concept, we can model the station as a directed graph.

The set of connectors noted CO is defined by

CO = (g, g ) ∈ G r × G r neigh g = g neigh g = g (5.8)
Then a connector co ∈ CO is a couple of gates (g, g ) such that a convoy can leave the resource r (g ∈ G r ) by the gate g to enter the resource r by g (g ∈ G r ).

It is important to note that the connector (g, g ) is not equivalent to the connector (g , g). The first one means an exit by g and an entry by g whereas the second one means an exit by g and an entry by g.

The train station can then be modeled by a directed graph G(V, E) where the vertices represent connectors and the arcs represent resources (Figure 5.3). This allows to represent reverse and non-reverse resources 2 . Some values are associated with each edge of the graph G such as the minT rT ime and the maxT rT ime which are the minimal and the maximal traveling time to go from a connector to an other one through a resource. These parameter values aggregate several parameters from the original problem formulation, depending on the resources type, such as trT ime for trackgroups, maxDwellT ime for platforms, revT ime for the reverse operations on single tracks, platform, yards... where t i in sched p is paired with co i in p, meaning that at t i the connector co i is used to leave resource r i-1 and resource r i .

Decision Variables

Arrival and Departure assignments

A convoy may come from an arrival (all trains composing the convoy enter the system as elements of this arrival), and be assigned to a departure (all trains composing the convoy leave the system satisfying elements of this departure).

∀v ∈ V, ∀a ∈ ExtArr, from(v, a) ∈ {0, 1} ∀d ∈ ExtDep, assigned(v, d) ∈ {0, 1} (5.12)

Paths and schedules of convoys

A convoy v in V may be routed, thus associated with a path path(v) which is paired with a schedule sched(v), of size n v .

path(v) = (co 0 , r 0 , co 1 , r 1 , co 2 . . . co n-2 , r n-2 , co n-1 , r n-1 , co nv ) (5.13) sched(v) = (t 0 , t 1 , t 2 . . . t n-2 , t n-1 , t nv )
(5.14)

Constraints

Convoys paired with Arrivals and Departures

Recall that V + is the set of all convoys scheduled in the solution. Let v be a convoy in V. If v is scheduled in the solution then v is paired with an arrival a in ExtArr and a departure d in ExtDep.

v ∈ V + ⇒ a∈ExtArr f rom(v, a) = 1 d∈ExtDep assigned(v, d) = 1 (5.15)
Otherwise, v is not an element of V + and there is no arrival nor departure assigned to it.

v ∈ V + ⇒ ∀a ∈ ExtArr, f rom(v, a) = 0 ∀d ∈ ExtDep, assigned(v, d) = 0 (5.16)
This means the convoy enters the station via the first connector of the path, and leaves it via the last connector of the path. Let us now consider the i-th connector co i , composed of two gates g out and g in . By definition of connectors, neighg out = g in and neigh(g in ) = g out . Additionally, for the path to be valid, each resource must be consistent with the adjacent connectors:

r gout = r i-1
(5.24) r g in = r i (5.25)

A convoy v cannot use an incompatible resource r:

∀r ∈ R, Comp(v, r i ) = 0 ⇒ r i ∈ path(v) (5.26)
Since v is a convoy of the solution, it is assigned to an arrival a in ExtArr as well as a departure d in ExtDep. Then the path followed by the convoy v must begin with the arrival sequence arrSeq a (Eq. 5.27) and end with the departure sequence depSeq d (Eq. 5.28). arrSeq a = (tg a 0 , . . . , tg a n 1 ) (5.27)

depSeq d = (tg d 0 , . . . , tg d n 2 ) (5.28)
The arrival (resp. departure) sequence is composed by n 1 + 1 (resp. n 2 + 1) track-groups.

∀r i ∈ path(v),    i ≤ n 1 ⇒ r i = tg a i n v -n 2 -1 ≤ i ⇒ r i = tg d j with j = n v -n 2 -1 + i (5.29)
Since the arrival and the departure must take place on a platform, we have:

r n 1 +1 ∈ P and r nv-n 2 -2 ∈ P (5.30)

Valid schedule

Let v ∈ V + be a convoy of the solution. The schedule sched(v) must respect the delay imposed by the graph G to go from one connector to another through a resource.

∀t i , t i+1 ∈ sched(v), minT rT ime(co i , co i+1 ) ≤ t i+1 -t i t i+1 -t i ≤ maxT rT ime(co i , co i+1 ) ( 5

Objective function

The original problem featured two optimization criteria assembled in a weighted sum: maximization of the covered arrival and departures, and minimization of performance costs (platform usage costs, preferred reuse of trains, etc.). We focused on the maximization of covered arrival and departures (while of course limited by our choices to disregard maintenance, junction and disjunction operations). With the formalism defined in this section, maximizing arrivals and departures coverage comes down to maximizing the number of trains used in the solution: Let gc1, gc2 be two group connectors and c a category. First, we compute the shortest path to reach gc2 from gc1. Then we note minT rT ime c (gc1, gc2) the lower time bound and maxT rT ime c (gc1, gc2) the upper time bound to travel from the input connector gc1 to the output connector gc2 on the path found compatible with category c.

Routing Procedure

This section deals with the effective scheduling and routing of a train along a given group-level path. To schedule a train, the routing procedure considers the resource group-level path computed during the pre-processing phase, then tries to schedule the train at the resource-level, taking into account resource capacities, maximum lengths, minimal and maximal transition time, and conflicts with already scheduled trains. This is done by constraint propagation on multi-interval variables. Section 5.4.1 introduce the notion of multi-interval variables in this context, and Section 5.4.2 details the routing procedure.

Multi-interval variables

We use constraint propagation [START_REF] Benhamou | Continuous and interval constraints[END_REF]) on hull and boxes (ILOG, 1999) using multi-intervals variables to filter solutions of the Path CHAPTER 5. A ROLLING STOCK MANAGEMENT PROBLEM Scheduling problem. First we introduce the notion of time interval IH (Eq. 5.40) in the planning horizons H, as defined by [START_REF] Moore | Interval Analysis[END_REF]:

IH :=    [h, h] (h, h) ∈ H 2 h ≤ h    (5.40) We note [h] the interval [h, h]. Let [h 1 ], [h 2 ]
be two intervals, we define the set operations ∩, ∪:

[h 1 ] ∩ [h 2 ] = [max(h 1 , h 2 ), min(h 1 , h 2 )] [h 1 ] ∪ [h 2 ] = [min(h 1 , h 2 ), max(h 1 , h 2 )] (5.41)
A large number of interval arithmetic libraries exist, see [START_REF] Knüppel | Profil/bias-a fast interval library[END_REF][START_REF] Lerch | Filib++, a fast interval library supporting containment computations[END_REF].

A generalization of IH is the power set P(IH). We call MIH = P(IH) the set of all the time multi-intervals in the planning horizon. Let mi 1 and mi 2 be two elements of MIH, the multi-interval intersection is defined as below:

mi 1 ∩ mi 2 = i 1 ∈mi 1 i 2 ∈mi 2 i 1 ∩ i 2 (5.42)
We introduce the operators lo and up on intervals and multi-intervals, which represent the lower and upper bounds of these quantities (see Figure 5.6 for an example). Mathematical comparison operators can be defined to deal with intervals and multi-intervals. Let x be an interval or a multi-interval quantity. Then the comparison of x with a real value y implies conditions over the bounds of x.

x ≤ y ⇔ up(x) ≤ y (5.44) y ≤ x ⇔ y ≤ lo(x)

(5.45)

The inequality constraints are used to reduce the domain of the values through a set of methods called contractors [START_REF] Chabert | Contractor programming[END_REF]. Atomic and metacontractors can be considered as basic elements of a new paradigm called contractor programming in order to perform efficient global optimization algorithm [START_REF] Ninin | Global optimization based on contractor programming: an overview of the ibex library[END_REF] exploiting the properties of groups of constraints. In the next section we present a contraction method for the Path Scheduling Problem previously introduced. The idea behind the routing procedure, described in the next section, is to consider scheduling variables as two types of multi-interval variables, transition variables t i and usage variables u i . That way, for a given convoy's schedule, the multi-interval variable u i represents the time intervals during which the corresponding resource of the convoy's path r i is available for the convoy (with respect, amongst other, to length and capacity constraints). Similarly, the multi-interval variable t i represents the time intervals during which the convoy may exit the previous resource and enter resource r i through connector co i (with respect to other convoy's transitions).

ROUTING PROCEDURE

The path and schedule definition presented in the simplified model are extended accordingly, by adding to the schedule usage time variables u i in bijection with the resources r i in the path:

path(v) = (co 0 , r 0 , co 1 , r 1 , co 2 . . . co n-2 , r n-2 , co n-1 , r n-1 , co n ) (5.46) sched(v) = (t 0 , u 0 , t 1 , u 1 , t 2 . . . t n-2 , u n-2 , t n-1 , u n-1 , t n ) (5.47)
The procedure consists in refining those multi-intervals by constraint propagation.

However, propagating constraints on multi-intervals variables is very expensive. Computing speed may be increased using lazy evaluation [START_REF] Madsen | Lazy propagation: a junction tree inference algorithm based on lazy evaluation[END_REF]. Laziness is especially used and developed in functional programming languages [START_REF] Johnsson | Efficient compilation of lazy evaluation[END_REF]) such as Haskell [START_REF] Hudak | A history of haskell: being lazy with class[END_REF]. It consists into a set of methods in order to limit the number of computations by non-evaluating quantities which are not required. This approach is not yet fully implemented in our solution, so there is still room for progress and potential speed-up.

Definition : H r,l,s

Let r be in R, and l, s in N. We define the set H r,l,s as all the instants t in the planning horizons H such that the resource can be used by a convoy of size s with a total length l.

H r,l,s =          t ∈ H v∈V + (use(v, t, r) × size(v)) ≤ capa(r) -s v∈V + (use(v, t, r) × length(v)) ≤ length(r) -l         
(5.48)

Algorithm

In this section, we detail the procedure used to route and schedule a convoy along a group-level path (Algorithm 1).

Let us consider a m-sized convoy, of total length l, and a group-level path GlobalP ath. GlobalP ath is formalized as an alternating list of connector-groups and resource-groups (gco 0 , gr 0 , . . . , gco 1 , gr n-1 , gco n ).

The procedure returns, if possible, a resource-level path (formalized as an alternating list of connectors and resources (co 0 , r 0 , . . . , co 1 , r n-1 , co n ) and a matching schedule. A Schedule is an alternate list of transition multi-interval variables, and usage multi-interval variables (t 0 , u 0 , . . . , t n-1 , u n-1 , t n ). t i represents the available intervals for transition between resources r i-1 and r i on connector co i , and u i the available intervals for usage of resource r i .

Schedule is initialized using InitialSchedule. In practice, we initialize all multi-interval variables to the full planning horizon, except for the transitions corresponding to the arrival and departure of the convoy, which are reduced to the arrival (respectively departure) time (see Figure 5.7a).

Algorithm (Alg. 1) consists of an iteration over every path path := (co 0 , r 1 , . . . , r n-1 , co n ) enclosed in the GlobalP ath. Each iteration is divided in 2 steps (FilterResourceUsagePath, and FilterConnectorPath), described below.

Algorithm 1 : Routing Input: convoy Input: globalP ath := (gco 0 , gr 0 , . . . , gco 1 , gr n-1 , gco n ) Input: initSchedule := (t 0 , u 0 , . . . , t n-1 , u n-1 , t n )

1: for all path = (co 0 , r 0 , . . . , co n-1 ,r n-1 , co n ) ∈ globalP ath do 2:

schedule ← FilterResourceUsagePath(convoy, path, initSchedule) where u max k is the minimal multi-interval containing H r k ,l,m . This constraint (Eq. 5.49) represents the limitation in term of length and/or capacity of the resource (Figure 5.7a, 5.7b).

lo(t k ) ≤ u k ≤ up(t k+1 ) (5.50)
This constraint (Eq. 5.50) translates the fact that the convoy cannot occupy the resource before entering it and after exiting it (Figure 5.7b, 5.7c).

minTrTime r k (co k , co k+1 ) ≤ lo(t k+1 ) -lo(t k ) up(t k+1 ) -up(t k ) ≤ maxTrTime r k (co k , co k+1 ) (5.51)
These two constraints (Eq. 5.51) express the relation between the enter time t k and the exit time t k+1 depending on the minimal and maximal usage time of the resource r k (Figure 5.7c, 5.7d).

∀u ∈ u k , {u} ∩ t k = ∅ ∧ {u} ∩ t k+1 = ∅ (5.52)
This constraint (Eq. 5.52) means that the resource r k is able to welcome the convoy from its entrance to its exit (Figure 5.7d, 5.7e).

t k ⊆ u k t k+1 ⊆ u k (5.53)
This constraint (Eq. 5.53) means that the convoy can enter and exit the resource r k only when r k is able to receive it (Figure 5.7e, 5.7f).

2. Similarly, procedure FilterConnectorPath contracts the multi-interval variables (t 0 , u 1 , . . . , u n-1 , t n ) associated with path by computing for each resource r k the conflicts of enter time t k-1 and exit times t k+1 with already scheduled convoys occupying r k and propagating the associated constraints. This step also propagates again, when necessary, some of the previous constraints (Eq. 5.51, 5.52).

After both filtering procedures, if schedule is non-empty (which means it is possible to schedule the train along path), the algorithm returns, if not, it moves on to the next path. Finally, the train is scheduled according to an "earliest possible time" strategy within the allowed time intervals : each transition multi-interval is contracted to its lower bound, and usage multi-intervals are contracted accordingly. Note that the malleability of the structure leaves the possibility of implementing other strategies to avoid conflict with subsequent train schedules or optimize the enter and exit time on each resource to reduce penalty.

Example of propagation (Fig 5.7)

Figure 5.7 illustrates an example of propagation. Each line represents a multiinterval variable; lines labeled "Exit/Enter" are transition variables, and lines labeled with a resource name are usage variables.

Initially (Figure 5.7a), none of the variables are restricted, except for the transitions corresponding to the arrival and departure (first and last "Exit/Enter"), which are restricted to the exact arrival and departure times. Then, in Figure 5.7b the usage of resource Y ard1 is restricted according to the imposed consumptions listed in Table 5.2. In Figure 5.7c, usage of resources P latf orm1 and T rackGroup1 are restricted according to the preceding "Exit/enter" transition variables: the convoy cannot use a resource before it enters it. Then, the transition variables are restricted to allow sufficient time between the entry and the exit on each resource (Figure 5.7d).

Let us now focus on resource Y ard1: the last interval of its usage variable doesn't intersect with the following transition variable, so the yard cannot be used during this interval. It is thus removed in Figure 5.7e. The enter and exit transitions are adjusted accordingly in Figure 5.7f, as the convoy may not enter or exit the yard at a given instant if it is not available for use.

Figure 5.7g shows the result once a similar propagation has been performed on P latf orm1 and P latf orm2.

Greedy Assignment Algorithm

The problem is complex due to the routing problem in the station. Resource usage is crucial and we should avoid to engorge one resource of the station. This idea leads to the strategy of the greedy algorithm we present in this section. We call immediate arrivals-departure arrivals immediately followed by a departure on the same platform. In this case, the convoy only has to be routed through the arrival sequence and departure sequence, so the path is set except for the platform, and the convoy occupies few resources.

If a departure is not an immediate departure, the convoy has to be routed to a parking spot and parked between its arrival and its departure. We chose to park on yards only.

Our objective is the maximization of covered arrivals and departures as stated in Section 2. However, to comply with the multi-criteria objective of the original problem and limit penalties, considerations on trains reuses, preferred platform and platform usage penalties are implemented in the solution.

The algorithm is composed of three main steps.

1. First, we try to schedule immediate arrivals-departures while considering train reuses as hard constraints.

2. Then, we relax these constraints and try to schedule immediate arrivalsdepartures.

3. Finally, we try to schedule remaining trains from the arrival to departure with a parking phase (on yards only) in-between, first considering train reuses as hard constraints, then relaxing these constraints.

To improve coverage of joint departures without performing junctions nor disjunctions, each of these three main assignment phase follows the three steps described below.

(i) Try and assign joint arrivals to joint departures. Both departures and arrivals are taken in decreasing order of convoy size. Between a given joint arrival and a given joint departure, simple dynamic programming allows to compute an assignment maximizing the number of arrivals and departures satisfied, while respecting compatibility and trains order. When at least some members of a joint arrival/departure have been assigned, all the other members are locked and cannot be used in the subsequent assignment steps.

(ii) Try and assign unitary arrivals to unitary departures.

GREEDY ASSIGNMENT ALGORITHM

111

(iii) Try and assign members from remaining joint arrivals to remaining unitary departures (joint or not) and symmetrically remaining unitary arrivals to members of remaining joint departures. When one member is assigned, the other members are locked.

Formally, these sub-steps are described by Alg. 2, using the following definitions:

• J + arr (respectively J + dep ) the set of joint arrivals (respectively departures) used in the solution,

J + arr = {a ∈ J arr |∃j = jointArr a , ∃a ∈ jaList j , a ∈ A + } J + dep = {d ∈ J dep |∃j = jointDep d , ∃d ∈ jdList j , d ∈ D + } • A + (respectively D +
) the set of unitary arrivals (arrivals which are not members of any joint arrival) used in the solution,

A + = {a ∈ A|arrT rain a ∈ T + } ∪ J + arr D + = {d ∈ D|depT rain d ∈ T + } ∪ J + dep
• by complement, the sets of joint / unitary arrivals (respectively departures) not used in the solution:

A -= A -A + , D -= D -D + , J - arr = J arr -J + arr , J - dep = J dep -J + dep .

Algorithm 2 Assignment Greedy Algorithm

Step

1: Assign(J - arr , J - dep ) 2: Assign(A --J - arr , D --J - dep ) 3: Assign(A -, D -)
Non-assigned departures and compatible arrivals are taken in increasing order. Each time, the Routing procedure is used to schedule the corresponding convoy. This continues until an arrival with a feasible routing has been found (then the arrival is assigned to the departure), or until there is no more fit arrivals (then the departure remains unsatisfied).

To limit the number of infeasible attempts, arrivals and departures are filtered, taking into account compatibility characteristics such as category and remaining time/distance before maintenance, but also existence of a path between two arrival/departure sequences and time between arrival and departure. The routing algorithm (Alg. 1) is used inside the greedy subroutine Assign (Alg. 2). The latter consists in a serie of attempts, iterating on the arrivals and the departures sets. For each couple arrival/departure, a compatible convoy is selected and a resource group-level path (computed during the pre-processing phase) is selected to link the arrival sequence with the departure sequence. Thus, the routing algorithm is applied to this convoy and global path. If the process fails to provide a valid resource-level path (Alg. 1, line 10), we move on to the next compatible couple. Otherwise, the convoy is scheduled along the path, thus the arrival and the departure are respectively removed from the available arrivals and the available departures sets. Figure 5.8: Greedy Algorithm : example Figure 5.8 shows a simplified example on an instance with three arrivals and four departures. A departure is compatible with an arrival if they are represented using the same shape (disc, square) and if the arrival takes place before the departure on the time line. On Figure 5.8, a line from an arrival to a departure is an attempt to route and schedule a convoy through the station from the arrival to the departure. A red dotted line is a failure while a solid green line is a success. Here, the couple arr1/dep1 is compatible and is succesfully routed and scheduled. The couple arr2/dep2 is compatible but the routing procedure fails, so the next compatible couple arr2/dep3 is considered. The routing procedure successfully returns a valid schedule, so arr2 and dep3 are assigned to each other, and the convoy is routed and scheduled. The last arrival, arr3, does not have any compatible departure, so no routing attempt is made.

In order to limit platform assignment penalties, when scheduling a convoy from an arrival to a departure, the preferred platform is tried in priority. To limit the platform usage penalties, we limit the time that a train can spend on a platform. For immediate departures, this amount of time is computed using the ideal dwell times of the departure and the arrival, and the costs defined in parameters, in order to ensure that the platform usage cost for this train does not exceed the U ncov penalty for not covering the arrival. We filter the arrivals verifying this condition. For arrivals and departures separated by a parking phase, we ensure during the routing phase that the ideal dwell times are exactly respected.

Results and Conclusions

The experiments were performed on a computer featuring an Intel Core 2 Duo E8400 3.00GHz CPU with 4Go RAM, running Xubuntu 64 bits. Table 5.3 presents the results obtained on instance set B, provided by the challenge organizers. The execution was stopped after 10 minutes of running time. Table 5.3 reports the results obtained when stopping after the first two stages of the algorithm (which means allowing only immediate departures), and the results obtained after full execution of the algorithm (which allows parking during the last stage). In each case, we give the number and proportion of covered departures. We also give, for information purposes, the value of the objective function used in the original formulation of the ROADEF Challenge problem (Ramond and Nicolas, 2014), which aggregates various performance costs as well as penalties for uncovered departures and arrivals. However, within our simplified model, the number of covered departures alone is a more pertinent indicator. The solutions provided within the allowed time cover 20% to 40% of departures (and as much arrivals). Of course, this is very few and not suited for a practical application. Although, considering the complexity of the problem and the size of the search space, it is actually quite reasonable for a simple greedy assignment algorithm. Moreover, given that our approach does not allow maintenance, junction and disjunction operations, the number of departures which can be covered is limited. This suggests that the routing algorithm itself is quite powerful, and that paired with a more advanced assignment optimization algorithm, it could lead to interesting results.

From Table 5.3, one can notice that most covered departures are "immediate departures", which are departures following directly the arrival on the same platform, assigned during the first two stages of the algorithm. The next stage, allowing trains to change platforms between arrival and departure by transiting through yards, gains only a few percent and is time consuming. Thus, considering only immediate departures seems a suitable approach to compute rather quickly an initial solution.

When considering immediate departures, the path and timing is already precisely defined by the arrival and departure sequences. In this case, the Routing procedure only serves to determine the feasibility of this path and timing for a given couple arrival/departure and select a platform, given the current state of the solution and avoiding conflict with other trains. When allowing parking, additional decisions must be made, namely the selection of the parking yard and the duration of stay. Thus, in this case the exploration performed by the Routing procedure is heavier and more time consuming.

Total execution times appear shorter for instances with few departures and arrivals (B7, B8, B10), as less routing attempts need to be made. The comparatively high execution time for instance B10 might result of the high proportion of joint departures and arrivals in this instance, as members of a joint arrival or departure may be tentatively routed several time, as convoys and as unitary trains.

The most interesting point in the solution exposed is without any doubt the association of the three-level routing algorithm with the greedy algorithm. Indeed, the multi-interval constraint propagation is flexible, efficient and return a set of possible range-value to enter and exit from each resource, allowing to find nontrivial routes within the range of possibilities.

Note that as a canonical path between any pair of resources is computed during the preprocessing phase, trains traveling with a given origin and destination are always routed along the same path. Choosing among a set of preferred paths, or computing on the fly alternative paths forbidding certain resources could be useful to avoid engorgement.

However the solution we propose here is robust, and the optimizer always return a feasible solution. An important aspect of the greedy algorithm is the ability to build a correct solution really fast on all the instances and to build a better solution if more time is available.

A simple optimization process could merely consist of choosing a random train, then removing it from the solution and finally try to build another schedule. Rather than just choosing randomly, one could select the train which generates the most conflicts: each time the algorithm tries and fails to schedule a train, the conflict value of the trains which prevented the scheduling is incremented ; at the end, the train with the highest conflict value is removed from the solution. This could be used as the basis for a local search optimization procedure.

Chapter 6 Conclusion

I don't need you to agree with me. I'll go away happy with a little bit of doubt. Doubt is good. It's an emotion we can build on. Perhaps if we feed it with curiosity it will blossom into something useful, like suspicion -and action.

Jasper Fforde, Shades of Grey

This work presented two takes on problems mixing scheduling and transportation.

In the first (and main) part of this work, we studied, from a theoretical viewpoint, cyclic production of identical parts in robotic cells. This model allows to take into account handling resources in the form of a robotic arm handling parts between machines. Of the two main possible arrangements of the cell, linear and circular, the latter is less understood and appears to be more complex. Our goal was to improve the understanding of the circular configuration, by focusing on the special case of regular balanced cell, where the problem description is particularly compact (3 numbers). Some of the results appeared in the proceedings of the 8th IFAC Conference on Manufacturing Modelling, Management & Control [START_REF] Thiard | Good Production Cycles for Circular Robotic Cells[END_REF].

We considered two classical problems of robotic cells, still open for this configuration: the dominance of the one-part production cycles (1-cycle conjecture) over all production cycles, and finding the best 1-cycle (NP-hard for circular cells, but still open in the balanced case).

We derived the exact expression of cycle time of a crucial 1-cycle specific to circular cells, the odd-even cycle, which was not correctly understood until now, highlighting the specificity of its structure. Lower and upper bounds of its cycle 118 CHAPTER 6. CONCLUSION time can be deduced for the non-balanced case, although in this case the full algebraic expression is yet to determine. In the balanced case, this expression allowed us to delimit parameters regions where the best 1-cycle is one of three classical cycles: the aforementioned odd-even cycle, and two cycles also used in linear cells, the identity cycle and downhill cycle.

By studying simple structural properties of performant cycles in the remaining parameters regions, we were able to completely settle the best 1-cycle problem for small cells (up to 8 machines). We were also able to exhibit a 2-cycle outperforming 1-cycles on a given instance of a 6 machine circular balanced cell, thus proving false the 1-cycle conjecture in this case (interestingly, the same conjecture is on the contrary valid for the linear counterpart of this configuration). The 1-cycle conjecture is still open for smaller circular cell: although we did not find, by numeric computation, any 2-cycle outperforming 1-cycles for 3 ≤ m ≤ 5 machines, a formal proof of this is still needed, still leaving the question of higher degree cycles.

For larger cells (more than 8 machines), numeric simulations of remaining 1cycles led us to define and fully study a new, easy to describe, family of cycles formed by specific alterations of the odd-even cycle, whose members outperform the classical cycles in some instances. Studying variations of this structure led us to a conjecture on the dominance of this family, along with classical cycles, over 1-cycles, which we settled for up to 11 machines. If proven valid, this conjecture would allow to settle the best 1-cycle problem on circular regular balanced in polynomial time.

The cyclic structures developed in this work could also be applied to improving approximation for non-balanced circular cell: for instance, the current approximation algorithm uses a combination of the identity and downhill sequences, which is efficient for a mix of short and long tasks; combining the odd-even and downhill structure seems a better fit for a mix of medium and long tasks.

The methods developed and the family of cycles derived in this document could also be extended to other layouts close to the circular one or with similar properties.

The last part of this work is devoted to a practical rolling stock management problem, proposed within the scope of the EURO/ROADEF Challenge 2014. The contribution presented, published in Annals of Operation Research [START_REF] Joudrier | A greedy approach for a rolling stock management problem using multi-interval constraint propagation[END_REF], is a joint work with Hugo Joudrier. The goal is to manage trains within a station; to achieve this, the original formulation mixes several problems and constraints of routing, scheduling and resources assignment. By simplifying the formulation, we were able to propose a flexible routing algorithm based on multi-interval constraint propagation. Coupled with a greedy assignment algorithm, it allows to quickly compute a feasible solution, which can serve as basis for further optimization.

Conclusion (Français)

Dans ce travail, nous avons présenté deux types de problèmes mêlant ordonnancement et transport.

La majeure partie de ce travail était dédiée à une approche théorique de la production cyclique de pièces identiques dans les cellules robotisées. Ce modèle permet de prendre en compte le transport de pièces au sein d'un atelier de production par le biais d'un bras robotisé, chargé de déplacer les pièces d'une machine à l'autre. Parmi les deux principales dispositions physiques de l'atelier, linéaire ou circulaire, la seconde est moins bien comprise et semble plus complexe. Notre objectif était donc d'approfondir la compréhension de la configuration circulaire : pour y parvenir nous nous sommes concentré•e•s sur le cas particulier de cellules régulières et équilibrées, dans lequel la description d'une instance est particulièrement compacte (3 nombres). Certains de nos résultats apparaissent dans les actes de la conférence IFAC MIM 2016 [START_REF] Thiard | Good Production Cycles for Circular Robotic Cells[END_REF].

Nous nous sommes intéressé•e•s à deux problèmes classiques des cellules robotisées, toujours ouverts pour la configuration choisie : la dominance des cycles de production d'une pièce (conjecture des 1-cycles) sur l'ensemble des cycles de production, et la recherche des meilleurs 1-cycles (NP-difficile dans les cellules circulaires, mais de complexité inconnue dans le cas équilibré).

Nous avons développé l'expression algébrique du temps de cycle du cycle pairimpair, un cycle classique crucial, propre aux cellules circulaires et jusqu'ici incorrectement compris, en mettant en évidence sa structure spécifique. Dans le cas non équilibré, nous pouvons en déduire des bornes inférieures et supérieures du temps de cycle, mais l'expression exacte reste à déterminer. Dans le cas équilibré, cette expression nous a permis de préciser des intervalles de paramètres ou le meilleur cycle est l'un de trois cycles classiques : le cycle pair-impair mentionné ci-dessus et deux cycles de base également pertinents dans les cellules linéaires, le cycle identité et le cycle descendant.

Pour les intervalles restants, l'étude de simples propriétés structurelles des cycles performants nous ont permis de fermer complètement le problème du meilleur 1-cycle pour les petites cellules circulaires équilibrées (jusqu'à huit machines). Nous avons également identifié un 2-cycle strictement plus performant que 120 CHAPTER 6. CONCLUSION le meilleur 1-cycles sur certaines instances pour une cellule de 6 machines, réfutant ainsi la conjecture des 1-cycles dans ce cas (à noter que cette conjecture est en revanche valide pour la configuration linéaire correspondante). La conjecture des 1-cycles est toujours ouverte pour de plus petites cellules circulaires : bien que les simulations numériques n'aient mis en évidence aucun 2-cycle plus performant que les 1-cycles pour des cellules de 3 à 5 machines, il manque encore une preuve formelle, ainsi que la question des cycles d'ordre supérieur à deux.

Pour des cellules arbitrairement grandes (plus de huit machines), la simulation des 1-cycles restants nous a mené vers la définition et l'étude complète d'une nouvelle famille de cycles, facile à décrire, dont les membres sont plus performants que les cycles classiques sur certaines instances. L'étude de variations de cette structure nous a conduit à la formulation d'une conjecture sur la dominance de cette famille, associée aux cycles classiques, sur l'ensemble des 1-cycles. La preuve de cette conjecture permettrait de résoudre le problème du meilleur 1-cycle en temps polynomial.

Les structures de cycles développées dans ce travail pourraient également permettre une meilleure approximation pour les cellules ciculaires non-équilibrées : par exemple, l'algorithme actuel utilise une combinaison des séquences montantes (identité) et descendantes, qui est efficace lorsques les tâches sont de durées courtes et longues ; combiner les séquences paire-impaires et descendantes semble une meilleure approche dans le cas ou les taches sont de durées moyennes et longues.

La dernière partie de ce travail était dédiée à un problème pratique de gestion ferroviaire, proposé dans le cadre du Challenge EURO/ROADEF 2014. La contribution présentée, publiée dans Annals of Operation Research [START_REF] Joudrier | A greedy approach for a rolling stock management problem using multi-interval constraint propagation[END_REF], est un travail commun avec Hugo Joudrier. Le but était de gérer les train au sein d'une gare ; à cette fin, la formulation originale mêlait divers problèmes et contraintes de routage, ordonnancement et affectation de ressources. En simplifiant la formulation, nous avons pu proposer un algorithme de routage souple, basé sur de la propagation de contraintes multi-intervalles. Associé à un algorithme d'affectation glouton, celui-ci permet de calculer une première solution réalisable qui peut servir de base à une optimisation. 122 CHAPTER 6. CONCLUSION

Notations

These are the notations used throughout Chapters 1 to 4 (robotic cells). For each notation, we give the page where it is first introduced and defined.

Chapter 5 is independent and uses its own set of notations (please refer to the chapter itself or to Ramond and Nicolas (2014)1 ).

A i for i ∈ {0 . . . m}, activity A i , i.e. the elementary sequence of moves where the robot unloads a part from machine M i , travels to machine M i+1 and loads the part on to machine M i+1 . 5

α m+1 2
, where m is the number of machine. 30 α(n) for any n ∈ N , n+1 SE i,j the ordered sequence of all activities A l with l even, i ≤ l ≤ j. 66 SO i,j the ordered sequence of all activities A l with l odd, i ≤ l ≤ j. 66 Notations 125 T c the long run average cycle time of the specified cycle c. When useful, the cycle time may be expressed as a function of p and denoted T c (p). If c is a k-cycle, its cycle length is given by Tc k (obviously, the cycle length of a 1-cycle π is simply T π ). 20 v(i 1 , i 2 , . . . , i n ) the cycle defined by the n waves of size 1:

A i 1 A i 1 -1 , A i 2 A i 2 -1
. . . A in A in-1 . 65

V h (i 1 , i 2 , . . . , i n ) the set of cycles containing the n waves of size h:

A i 1 A i 1 -h , A i 2 A i 2 -

Out

Figure 1 . 1 :

 11 Figure 1.1: Three-machine robotic cells

  et al. (2010) present an overview of the complexity status of cyclic scheduling problem, including robotic cyclic scheduling. Dawande et al. (2007) have written a book on throughput optimization in robotic cells both with single and dual gripper robots. Crama et al. (2000) present a survey on bufferless robotic cells and Brauner (2008) on the cyclic production of identical part in classical robotic cells. Bagchi et al. (2006) present a survey of TSP-based approaches for contemporary flow-shop problems, including the robotic flow-shop model.

  and Jiang and Liu (2007) consider a more general problem where the part flow does not necessarily coincide with the order of the machines in the cell, respectively with 2 robots and an arbitrary number of robots, and solve it in polynomial time (respectively O(m 4 logm) and O(m 6 R), where R is the number of robots). These algorithms are based on the identification of threshold cycle times where the feasibility condition changes. Che et al. (2012) solve the problem in O(m 5 ) for any number of robots on the more general model of reentrant cells, although contrary to Jiang and Liu (2007), they do not enforce the upkeep of a safe distance between the robots.

  et al. (2012) in 2-machine cells. Like Gultekin et al. (2009) they model the problem as a generalized form of TSP, and propose a heuristic. The problem of minimizing jointly the cycle time and the manufacturing costs is studied by Gultekin et al. (2008, 2010) and Yildiz et al. (2012). The flexibility of the machines allow to vary their parameters (such as their speed) to adjust the processing times, with associated costs: thus processing times may be considered as decision variables. Gultekin et al. (2008) study this problem in 2 and 3-machine linear cells, determining sets of non-dominated cycles. Gultekin et al. (2010) provides a Mixed Integer Non-Linear Model (MINLP) for the 2-machine case. Yildiz et al. (

Figure 2 .Figure 2 . 1 :

 221 Figure 2.1: One iteration of cycle (A 0 A 3 A 2 A 4 A 1 ) on instance (m = 4, p = 5, δ = 1).

Figure 2 . 2 :

 22 Figure 2.2: For m = 6, δ = 1, lower bounds LB M (Equation (2.2)) and LB R (Equation (2.4)) on the cycle time of 1-cycles, as functions of p.

CHAPTER 2 .Figure 2 . 3 :

 223 Figure 2.3: One iteration of π id on instance I = (m = 4, p = 3, δ = 1)

Figure 2 . 4 :Proposition 2 . 5 .

 2425 Figure 2.4: One iteration of π dh on instance I = (m = 4, p = 3, δ = 1)

Figure 2 .Figure 2 . 5 :

 225 Figure 2.5 shows the cycle times of π id and π dh as function of p, as well as lower bounds from LB M and LB R , highlighting their regions of optimality.

CHAPTER 2 .Figure 2 . 6 :

 226 Figure 2.6: One iteration of π oe on instance I = (m = 4, p = 3, δ = 1)

Figure 2 .Figure 2 . 7 :

 227 Figure 2.7: Two consecutive iterations of cycle π oe in a 4-machine cell.

  i∈{1,...,m} p i and p max = max i∈{1,...,m} p i Proposition 2.7.

1

 1

Figure 2 . 9 :

 29 Figure 2.9: Two periods (four iterations) of π oe operating in periodic steady state on instance J : (m = 4, p = 6, δ = 1)

Figure 3 . 1 :

 31 Figure 3.1: Lower bounds and cycle times of π id , π oe and π dh , showing their regions of optimality

  In all cases, we have T π * (p) ≥ (m + 1)δ + (m + 1)δ + (m -1)δ + 2δ = 3(m + 1)δ, thus any cycle containing a sequence of the form A i A i+1 with i = m is dominated by π dh . 40 CHAPTER 3. ONE-CYCLES AND SMALL CELLS ANALYSIS Proposition 3.4. If m ≥ 5, the travel time ∆ π * associated with π * verifies ∆ π * > 2(m + 1)δ.

Figure 3 . 2 :

 32 Figure 3.2: Illustration of the proof of Proposition 3.6, representing cycle times of π oe , π dh , f (Equation (3.8)) and the lower bound on the cycle time T π * given by Proposition 2.3.

  m+1)δ. This is the situation schematized CHAPTER 3. ONE-CYCLES AND SMALL CELLS ANALYSIS on Figure 3.2a. By Proposition 2.3,

Figure 3 . 3 :

 33 Figure 3.3: Cycle π * 4 = A 0 A 3 A 2 A 1 A 4

Figure 3 . 4 :

 34 Figure 3.4: Cycle π* 5 = A 0 A 3 A 2 A 5 A 1 A 4

Figure 3 . 5 :

 35 Figure 3.5: An iteration of C, for p = 11 and δ = 1

  have been introduced in Chapter 2, page 26. Some regions of optimality of these cycle have been established in Chapter 2, page 28 and Chapter 3, page 36:(i) if p ≤ m+1m δ, then the identity permutation π id dominates 1-cycles;

Proposition 4 . 1 .

 41 If a cycle c is non-dominated by {π oe , π dh } over ](m + 1)δ, (3m -1)δ[ then it is non-dominated by {π oe , π dh } over ](m + 1)δ, p * ]. Proof. This is a direct consequence of the cycle time being an increasing function of the processing time and min(T πoe (p), T π dh (p)) reaching its maximum in p * . Consider p ∈ ](m + 1)δ, (3m -1)δ[ such that T c (p) < min{T πoe (p), T π dh (p)}. If p > p * , then T c (p * ) ≤ T c (p) < min(T πoe (p), T π dh (p)) ≤ 3(m + 1)δ = min (T πoe (p * ), T π dh (p * )) and hence T c (p * ) < min (T πoe (p * ), T π dh (p * )).

Figure 4 .

 4 Figure 4.1 summarizes the results presented in this section. This diagram shows the cycle times of {π id , π dh , π oe } and the lower bounds presented in Chapter 2 (LB M , LB R ) and Chapter 3 (LB D ), outlining parameters regions for which the optimal cycle is known, and the remaining region p ∈ ](m + 1)δ, (3m -1)δ[ which we focus on in this chapter. We are looking for potential optimal cycles other than {π id , π dh , π oe }, thus dominating {π oe , π dh } for some value of p: Proposition 4.1 indicates that the cycle times of such cycles necessarily take some values in the hatched area shown on Figure 4.1.

Figure 4 . 1 :

 41 Figure 4.1: Cycle times and known regions of optimality of {π id , π dh , π oe }.

m 9 10

 10 11 12 13 14 #f iltered(m) 26 23 32 41 63 63 Table 4.1: number of cycles in f iltered(m) for 9 ≤ m ≤ 14

  dh (p * ) Tπ(p * ) 1.015 1.028 1.005 1.026 1.050 1.005 Table4.2: Performance ratio of {π oe , π dh } for δ = 1, p = p * , using the computed cycle times of cycles in f iltered(m).

Figure 4 . 4 .

 44 These sequences add to the total travel time but also increases the time travelled between the loading and unloading of any machine (increasing d min to d min = (m + 5)δ for 9 ≤ m ≤ 11 and m = 14; d min = (m+5)δ or d min = (m+9)δ for m = 12; d min = (m+9)δ for m = 13). When several cycles appear to be equivalent, the relative placement of the backward sequences is the same. 54 CHAPTER 4. DOMINANT STRUCTURES FOR LARGE CELLS

Figure 4 . 2 :

 42 Figure 4.2: π dh , π oe and computed cycle times of all members of f iltered(m) as functions of p. The step used for p is 0.1. Notice that many cycles have the same cycle times.

m + 1

 1 ≤ p ≤ 15.00 π oe 15.00 ≤ p ≤ 16.00

Figure 4 . 3 :

 43 Figure 4.3: π oe , π dh and computed cycle times of all members of f iltered(m) as functions of p, zoomed around p * . The step used for p is 0.1.

Figure 4 . 4 :

 44 Figure 4.4: Some 1-cycles which outperform {π id , π dh , π oe } in the neighborhood of p * . For 12 machines, note that the two cycle presented are not equivalent: one has two backward sequences and the other has three.

Proposition 4 . 2 . 2 4. 4 .

 4224 Let π be a 1-cycle such that T π (p) < min(T πoe (p), T π dh (p)) for some p ∈ ](m + 1)δ, 3(m + 1)δ[. Then: ∀i ∈ {0, . . . , m} m π (i) ≥ 2 and ∃j ∈ {0, . . . , m} m π (j) = GENERAL STRUCTURE OF PERFORMANT CYCLES 59

  Case 2.2.1. (decreasing order after k)

Figure 4 . 5 :

 45 Figure 4.5: For the proof of Proposition 4.2.

Figure 4 . 7 :

 47 Figure 4.7: One wave

Figure 4 .

 4 Figure 4.8: Placement.

FromFigure 4 . 9 :

 49 Figure 4.9: Decomposition of a cycle in still waters and turbulences

Figure 4 . 10 :

 410 Figure 4.10: Proposition 4.5 (i): example for l = 3 and l = 4. Two iterations are represented.During each of the three intervals represented in red, at most d unit of travel time occur, and p time units must have gone by in order for the part to be available. Thus at least max(0, p -d) units of waiting time are necessary. On average,3 2 max(0, p -d) units of waiting time by iteration are necessary.

i 1

 1 A i1+l1 and A i2 on the same turn 0 A i1+l1 and A i2+1 on the same turn

Figure 4 . 11 :

 411 Figure 4.11: Proposition 4.5 (ii)

  d b ), this leads to a total waiting time of at least α(l)(p -d a ) + (α(l) -1)(p -d b ).

Figure 4 . 12 :

 412 Figure 4.12: cycle π 2w on a 10-machine cell.

2 δ

 2 As the cycle time is increasing in p, for p > (m + 5)δ + 4 m+7 2 δ: T π 2w (p) ≥ 2(m + 5)δ + Ŵ (m -8, (m + 5)δ, p) Proof.

Figures 4 .

 4 Figures 4.13aand 4.13b show an example respectively for m = 11 and m = 12.

1 α(m- 8 )

 18 (p -(m + 5)δ), so no additional waiting time is necessary. -For 2 ≤ i ≤ 9, if M i is loaded during the first turn: d i ≥ (m + 5)δ, and between the loading and unloading of machine M i the robot waits α(m -8) times 1 α(m-8) (p -(m + 5)δ), so no additional waiting time is necessary.

Figure 4 . 13 : 2 ,

 4132 Figure 4.13: Waiting times during one iteration of π 2w . The value α(m -8) is denoted β.

d

  min (π nw ) = (m + 2n + 1)δ Proposition 4.8 gives an expression for π nw cycle time, generalizing Proposition 4.7.CHAPTER 4. DOMINANT STRUCTURES FOR LARGE CELLS

Figure 4 . 14 : 4 . 8 . 2 δ

 414482 Figure 4.14: Representation of π nw , with n even

Corollary 4. 1 .

 1 For m ≥ 4n + 1 and n even, the cycle time of π nw satisfies: For (m + 1)δ < p ≤ p * n , T πnw (p) = 2(m + 2n + 1)δ + Ŵ max(1, m -4n), (m + 2n + 1)δ, p ≤ 3(m + 1)δ For p ≥ p * n , T πnw (p) ≥ 3(m + 1)δ.

Figure 4 .

 4 Figure 4.15: Representation of π nw , with n odd.

Proposition 4 . 10 .

 410 Cycle time of π nw with n odd and m ≤ 4n + 1 For m = 4n and for m = 4n + 1, for (m + 1)δ ≤ p ≤ (3m -1)δ, the cycle time of π nw is given by 1 :

  , . . . , 4n -1}, and d i = (m + 2(n + 1) + 1)δ for all others machines M i . The processing of a same part on the n machines M 2 , M 4 , . . . , M 4i-1 , . . . M 4n-1 requires n+1 2 iterations of the cycle, thus T πnw ≥ 2(m+2n+1)δ + 2n n+1 (p-(m+2n+ 3)δ). An example for m = 13 and n = 3 is shown on Figure 4.16. The equality can be proven by considering the following waiting time vector (represented by the hatched aeras on Figure 4.16):

2 pFigure 4 . 16 :Corollary 4 . 3 .

 241643 Figure 4.16: Cycle time of π nw for n odd and m = 4n + 1: example for m = 13 and n = 3.

π

  nw with n even and m = 4n For n even, m = 4n, one has ∆ πnw = 2( 3 2 m + 1)δ and d min (π nw ) = ( 3 2 m + 1)δ. Thus, π nw does not verify Equation (4.5) and is therefore dominated by {π oe , π dh }. 80 CHAPTER 4. DOMINANT STRUCTURES FOR LARGE CELLS π nw with n odd and m ≥ 4n + 2

π

  nw and π (n-1)w with n odd and m = 4n + 1 Consider n odd and m = 4n + 1. For p ≤ ( 3 2 m + 5 2 )δ, by Proposition 4.10, T πnw = (3m + 1)δ. In particular,

Proposition 4 . 14 .

 414 Conjecture 4.1 is valid for m ≤ 11.

  have d min (π) = (m + 1)δ and ∆ π = 2(m + 1)δ + 6δ, thus T π (p) ≥ 2(m + 1)δ + 6δ + (p -(m + 1))δ. Using this bound and the cycle time of π oe , we get that if T π (p) < T πoe (p), then p > (m+1)δ +8 α α-1 δ. We can verify that for m ≤ 11, p * < (m + 1)δ + 8 α α-1 δ, thus T π (p) ≥ T πoe (p) ≥ T π dh (p) for p ≤ p * which contradicts Proposition 4.1. Thus π is dominated by {π oe , π dh }.

Figure 4 .

 4 19 shows the computed ratio at p * for 9 ≤ m ≤ 200, using Proposition 4.11 and the expression of the cycle time given by Proposition 4.8. We can verify algebrically that, if R m denotes the ratio at p * for m machines, each one of the sub-sequences (R m ) m=i mod 8 converges linearly towards 1, and thus the sequence (R m ) converges towards 1.

Figure 4 . 19 :

 419 Figure 4.19: Performance ratio R of {π id , π dh , π oe } within {π id , π dh , π oe } ∪ (π nw ) n for p = p * , as a function of the number of machines m.

1Figure 5 . 1 :

 51 Figure 5.1: That was hard to fit in the luggage compartment.

Figure 5 . 2 :

 52 Figure 5.2: Example instance: railway station

U

  arr := {a ∈ A | ∀B ∈ J arr , a ∈ B} (5.4) U dep := {d ∈ D | ∀B ∈ J dep , d ∈ B} (5.5) Now, we use the sets J arr and U arr to build a new set ExtArr called set of all extended arrivals (and the set ExtDep with J dep and U dep ). ExtArr := J arr ∪ {{a} | a ∈ U arr } (5.6) ExtDep := J dep ∪ {{d} | d ∈ U dep } (5.7) Definitions : compatibility For each convoy v ∈ V and departure in d ∈ ExtDep, a value Comp(v, d) ∈ {0, 1} is defined. If Comp(v, d) = 1, v and d are said to be compatible. This value takes into account several parameters of the initial formulation such as size, categories, time and distance remaining before maintenance, and so on.

4 ) 1 • v 2 =

 412 Let us consider the following instance: the sets of arrivals A = {a 1 . . . a 5 } and departures D = {d 1 . . . d 6 }; The sets J arr = {{a 2 , a 3 , a 4 }} and J dep = {{d 4 , d 5 , d 6 }}. Then ExtArr = {ea 1 = {a 1 }, ea 2 = {a 2 , a 3 , a 4 }, ea 3 = {a 5 }} ExtDep = {ed 1 = {d 1 }, ed 2 = {d 2 }, ed 3 = {d 3 }, ed 4 = {d 4 , d 5 , d 6 }} The convoys v 1 and v 2 where • v 1 = {t 1 }, with f rom(v 1 , ea 1 ) = 1 and assigned(v 1 , ed 2 ) = {t 2 , t 3 }, with f rom(v 2 , ea2) = 1 and assigned(v 2 , ed 4 ) = 1 are represented on the Figure 5.4.

Figure 5 . 4 :

 54 Figure 5.4: Convoys with provenance and assignment to departures.

Figure 5 . 5 :

 55 Figure 5.5: Resource Aggregation

Figure 5 . 6 :

 56 Figure 5.6: Example of a multi-interval, with its lower and upper bounds.

  Propagation Eq. 5.49 (c) Propagation Eq. 5.50 (d) Propagation Eq. 5.51 (e) Propagation Eq. 5.52 (f) Propagation Eq. 5.53 (g) Constraint Propagation Result

Figure 5 . 7 :

 57 Figure 5.7: Multi-Interval Filtering on the example instance, from Arr1 to Dep1 (see Table 5.1) with the consumptions indicated in Table 5.2.

  arrT ime a + minT rT ime cat Ta (P a , P d ) ≤ depT ime d (5.54) 112 CHAPTER 5. A ROLLING STOCK MANAGEMENT PROBLEM

2 . 66 c

 266 denotes a generic cycle. 20 δ the travel time between any two consecutive machines M i and M i+1 (both ways) with i ∈ {0, . . . , m}. 20 ∆ c the total travel time of the robot during one iteration of the specified cycle c. 24 d i (π) the travel time of the robot between the loading of machine M i and its subsequent unloading (in a cyclic sense) for the specified 1-cycle π. 24 d i,l (c) the travel time of the robot between the l-th loading of machine M i and its subsequent unloading (in a cyclic sense) for the specified cycle c. 24 d min (c) minimum value of d i,l : min i,l d i,l (c), or for a 1-cycle, min i∈{1,...,m} d i (c). 24 m the number of machines. 20 124 Notations M 0 the input buffer. 20 M m+1 the output buffer. 20 M 1 . . . M m the m machines. 20 m(i) the number of times the robot travels between machines M i and M i+1 in either direction (forward or backward). 58 m -(i) the number of times the robot travels backward between machines M i and M i+1 . 58 m + (i) the number of times the robot travels forward between machines M i and M i+1 during one iteration. 58 p i for i ∈ {1, . . . , m}, the processing time on machine M i (in the non balanced case). 20 p the processing time on any machine M 1 . . . M m (in the balanced case). 20 p * the value of parameter p for which π dh and π oe have the same cycle time (T πoe (p * ) = T π dh (p * ) = 3(m + 1)δ. Its expression is p * = 3α-1 2α-1 (m + 1)δ. 41 p * n for n even, the value of parameter p for which π nw and π dh have the same cycle time (T πnw (p * ) = T π dh (p * ) = 3(m + 1)δ). Its expression is p * = (m + 2n + 1)δ + α(m-4n) 2α(m-4n)-1 (m + 1 -4n)δ. 75 π denotes a 1-cycle. 20 π dh the downhill cycle A 0 A m A m-1 ...A 1 . 28 π id the identity cycle A 0 A 1 . . . A m . 27 π oe the odd-even cycle A 0 A 2 A 4 . . . A 1 A 3 A 5 . . . . 29 π 2w the cycle defined by π 2w = v(3, 7), which expands to π nw = A 0 A 3 A 2 A 5 A 8 . . . A 2i . . . A 1 A 4 A 7 A 6 A 9 . . . A 2i+1 ; special case of π nw . 69 π nw for n ∈ N , the cycle defined by π nw = v(3, 7, . . . , 4i -1, . . . , 4n -1); generalization of π 2w . 73

  h , . . . , A in A in-h . 65 W c (p) the long run average total waiting time of the robot for the specified cycle c, depending on p. The cycle time of c can be decomposed asT c (p) = ∆ c (p) + W c (p). 65 Ŵ (n, d, p) for any n > 0, p ≥ 0, d ≥ 0, Ŵ (n, d, p) = 2α(n)-1 α(n) max(0, p -d).By convention, Ŵ (0, d, p) = 0. 66 w i the waiting time of the robot at machine M i of the cycle. 71w ji the waiting time of the robot at machine M j during the i-the iteration of the cycle (when several consecutive iterations are considered).. 31

  the cycle time of π oe and π dh are given by

	CHAPTER 3. ONE-CYCLES AND SMALL CELLS ANALYSIS
	By Proposition 2.3, we have
	T π * 4 (p) ≥ 13δ + max(0, p -8δ)	(3.12)
	T πoe (p) =	3 2	p +	5 2	δ	(3.11a)
	T π dh (p) = 15δ	(3.11b)

Table 4 . 3

 43

	56	CHAPTER 4. DOMINANT STRUCTURES FOR LARGE CELLS

: Best 1-cycle depending on p, for 9 ≤ m ≤ 14 and δ = 1. * δ = 1, m = 11

  and show that they are dominated by cycles in (π nw ): this suggests that larger waves are not interesting to form dominant cycles. This leads us to conjecture, consistently with the observations presented in Section 4.3, that considering only {π id , π dh , π oe } and (π nw ) is enough to find a best 1-cycles for any instance: Conjecture 4.1. {π id , π dh , π oe } ∪ (π nw ) n≤ m 4 is a dominant set within 1-cycles Remark 4.1. If Conjecture 4.1 is valid, then the best 1-cycles for m ≥ 8 are given by Proposition 4.11.

  Refinement of the multi-interval scheduling variables (t 0 , u 0 , . . . , t n-1 , u n-1 , t n ) associated with the path p by filtering on each resource r k , taking into account capacity, length and usage time constraints (Method Filter-ResourceUsagePath) using the following contractors. An example of this step is unfolded (Figure5.7) on the simplified instance represented on Figure 5.2, using the parameters given in Tables 5.1 and 5.2, with the parameters minResT ime = 00 : 02 : 00 and revT ime = 00 : 05 : 00.

	3: 4: 5: 6: 7: 8: 9: end for if (schedule) = ∅ then schedule ← FilterConnectorPath(convoy, path, schedule) if (schedule) = ∅ then return (path, schedule) end if end if 10: return (∅, ∅) 1. u k ⊆ u max k	(5.49)

Table 5 .

 5 1) with the consumptions indicated in Table 5.2.

	110	CHAPTER 5. A ROLLING STOCK MANAGEMENT PROBLEM

Table 5 .

 5 3: Summary of the results on set instance B. The first 3 columns present the results for the algorithm limited to immediate departures only, the last 3 when subsequently allowing an intermediate parking phase in yards between arrival and departure. For each case, we give the execution time in seconds, the value of the ROADEF Challenge objective function and the proportion of covered departures. "t/o" means that the execution has reached the timeout, set to 10 minutes.

		immediate departures only	with parking phase (complete algorithm)
		t (s) objective covered dep	t (s) objective covered dep
	B1	24 1812600 35% (443/1235)	t/o 1749000 38% (474/1235)
	B2	23 1682080 39% (490/1235)	t/o 1656180 40% (503/1235)
	B3	21 1711330 38% (472/1235)	t/o 1665330 40% (495/1235)
	B4	71 2578160 36% (649/1780)	t/o 2561360 36% (657/1780)
	B5	136 3190890 34% (747/2153)	t/o 3155790 35% (764/2153)
	B6	72 2584130 36% (645/1780)	t/o 2559330 36% (657/1780)
	B7	2	456112 34% (105/304)	68	420112 40% (123/304)
	B8	2	473484 31% (96/304)	83	439884 37% (113/304)
	B9	72 2978598 29% (590/1967)	t/o 2858098 32% (649/1967)
	B10 < 1	364594 18% (36/196)	226	321794 29% (57/196)
	B11	3 1984144 16% (190/1122)	t/o 1858544 22% (250/1122)
	B12	1 1031864 16% (94/570)	t/o	982164 20% (118/570)

Si, si, Hadrien, tu es bien un permanent.

Même si pour rédiger ce manuscrit, il a fallu se passer de \faeries...

Also called proportionate flowshop.

Due to a lack of Russian reading skills, this statement relies heavily on blind trust in automated translation tools.

The authors appear to use a lower bound instead of the cycle time for the aforementioned odd-even cycle. In Chapter 2 we derive another expression of the cycle time.

4 -approximation algorithm for a case where the loading time of the buffer is small enough (smaller than the travel time between consecutive machines). For buffer of infinite capacity, they study a particular class of cycles. They compare their model with the dual-gripper and swap model via a computational study.

To anyone who suddenly felt not so young anymore reading this sentence, my apologies.

Although not exactly with the same exact meaning.

Mutatis mutandis, this example also works for linear cells (consider p = 9, for example). However, note that π oe is not a pyramidal permutation.[START_REF] Brauner | Ordonnancement dans des cellules robotisées[END_REF] conjectures that pyramidal permutations (which dominate 1-cycles in linear cells, but not in circular cells) are stable, meaning that no matter the initial state, the steady state of these cycles has a period of 1. The author proves this property for linear cells

with 2, 3 and 4 machines.

Note that in this case

2n n+1 = 2α(n)-1 α(n) .

But not among all 1-cycles (yet)! (For spoilers, jump to Conjecture 4.1.)

All resources have two (opposite) sides. On reverse resources, convoys are allowed to enter and exit on the same side, whereas this is forbidden on non-reverse resources.

Trains of the same category share similar characteristics (such as length).Some resources may only be compatible with some trains categories[START_REF] Ramond | Trains don't vanish ! ROADEF EURO 2014 Challenge Problem Description[END_REF].

https://hal.archives-ouvertes.fr/hal-01057324/file/Challenge_sujet_ phaseFinale_140224.pdf

Remerciements

p := (co 0 , r 0 , co 1 , r 1 , co 2 . . . co n-2 , r n-2 , co n-1 , r n-1 , co n )

(5.9)

The size of the path p is accessible via size(p) and returns the number of resources crossed along the path. size((co 0 , r 0 , co 1 , r 1 , co 2 . . . co n-2 , r n-2 , co n-1 , r n-1 , co n )) = n (5.10)

An n-sized path going through resources r 0 . . . r n-1 requires n + 1 connectors co 0 . . . co n .

Schedule of a path

The schedule of a path p, noted sched p , is a tuple of instants t in the horizon H which are in bijection with the connectors of the path. These values describe the time of transition from a resource to the other. Let p be a path composed by n resources (Eq. 5.9). Then a schedule for p is defined by

A convoy v cannot be assigned to an incompatible arrival a or departure d. In other words :

Usage of resources

The usage in term of capacity and length has to be respected. Let v be a convoy, with the schedule sched(v) associated to the path path(v). For each convoy v in V + and each instant t in H, we define use(v, t) the resource r in R used by the convoy v at t.

Then we define the value use(v, t, r), which is 1 if and only if the resource r is used at time t in the schedule sched(v) of the path path(v) associated to the convoy v.

Length and capacity constraints

Valid path

Let v be a convoy in V + , and path(v) the associated path, of size n v . To be valid, the path, defined as in (Eq. 5.13), followed by v must satisfy the following constraints.

The arrival time arrT ime a and departure time depT ime d must be respected. We assume the arrival sequence is composed by n 1 + 1 track-groups and the departure sequence by n 2 + 1 track-groups.

Conflicts between convoys

On single resources

) their respective paths, and

the respectively associated schedules.

If a same single resource (platform, single track or maintenance facility) belongs to both path, the associated entry times must be different :

Moreover, depending on the entry and exit connectors of both convoys, the following constraints on their entry and exit times must be enforced to preserve the order of the convoys on the resource (without loss of generality, we assume t i 1 < t 2 j ) :

On track groups On track groups, a specific conflict constraint applies, depending on the respective order of the entry and exit gates of both convoys. Though this constraint was implemented in the final solution, we do not reproduce it here for the sake of simplicity. One can refer to Ramond and Nicolas (2014).

At most one convoy assigned per extended arrival and departure

∀a ∈ ExtArr,

Data Structures and Pre-processing

In the remainder of the chapter, we will use the instance represented on Figure 5.2 as an example.

A maximum amount of convoys needs to be scheduled using the graph G previously defined. In order to reduce the cost of the routing phase by avoiding redundant treatment of very similar paths, we need a simplified structure with a higher aggregation level.

The simplification consists of aggregating resources in groups (Figure 5.5) of resources sharing the same characteristics and neighborhood [START_REF] Rogers | Aggregation and disaggregation techniques and methodology in optimization[END_REF]. We define the set RG of resources groups such that each resource r ∈ R is contained in one group rg ∈ RG with the following properties:

where type is defined as follow:

The goal of this process is to break the systematic and redundant treatment of similar resources while allowing for a more global reasoning.

Once the simplification is done, we can define a new graph G ((V , E )), more global, enclosing the graph G where vertices are groups connectors GCO and arcs are resources groups RG. These two graphs represent the station with different levels of granularity: the level which needs to be used depends on the step of the algorithm.

To simplify further the routing phase, we choose to consider the shortest path as the preferred path between two resources depending on the category 3 . Thus, shortest paths between any two groups of resources, or rather group connectors, are computed during the pre-processing phase using Floyd-Warshall algorithm [START_REF] Floyd | Algorithm 97: shortest path[END_REF]. During the process, a matrix of minimal and maximal travel time along this path is computed. Each resource r ∈ R can be considered to have a minimum and a maximum usage time. For any track-group k, the minimum bound is equal to the maximum one: trT ime k . The other resources have a minimum bound equal

List of Figures

LIST OF TABLES BIBLIOGRAPHY

Résumé 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 (1cycle) 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é 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.

Mots-clefs Ordonnancement, Flow-shop, Cellule robotisée, Ressource de transport, Production cyclique, Gestion de matériel ferroviaire Abstract 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.