Faculté des sciences et techniques de l'ingénieur STI, Section de microtechnique, Institut de microtechnique IMT (Laboratoire de production microtechnique 1 LPM1)

From car traffic to production flows : a guided tour through solvable stochastic transport processes

Filliger, Roger ; Hongler, Max-Olivier (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2005 ; no 3247.

Add to personal list
    Summary
    The purpose of this thesis is to show on explicit examples how various theoretical concepts, ranging from statistical mechanics to stochastic control and from traffic theory to queuing systems, can be transferred to transport processes, encountered in particular in manufacturing systems, with benefic implications for their dynamical understanding, optimization and control. The thesis collects several articles where such implications are exposed [38]-[43]. We start with the observation that car traffic and production flows share several common dynamical properties (chapter 3). The main reason for the similarities are the presence of non-linear interactions in both settings. In traffic theory the interactions are between competing cars and originate from a trade off between safe and fast driving. They directly influence the speed of the cars. In production flow engineering the interactions are between cooperating work-cells forming the manufacturing system. They govern the production policy and hence the throughput of the manufacturing system. We exploit this analogy in case of a serial production line where the influence on the production rate of a work-cell is determined by the contents of its adjacent buffers (fig. 0.1) and derive a dictionary between the two fields. As a first result, this analogy allows the recognition of free-flow and jamming-flow regimes —well studied in traffic theory — in the context of production lines. Fig. 0.1. Above: Sketch of a serial production line composed of N machines Mi with production rates vi and N -1 buffers Bi with buffer content yi. Below: Sketch of a one-lane traffic system composed of N cars with velocities vi and headways xi. Dynamical similarities between cars and work-cells: the production rates and the car velocities, depend both on their environment e.g., the content of the next nearest buffers vi = vi(yi-1, yi) resp. the distances to the next nearest cars vi = vi(xi-1, xi). Applying a linear stability analysis to a given stationary flow regime, we draw a flow diagram which defines the boundary between the free and the jammed regime as a function of the control parameters. The relevant conclusions include the introduction of a dimensionless performance parameter, an enlightening connection between transient and stationary performance measures for production lines, a discussion of both the bull-whip effect and the stabilizing effect of pull production controls in serial production lines. The traffic models used in the analogy with serial production lines are socalled optimal-velocity car following models which assume that the velocity of a car is adapted to a distance dependent optimal velocity which reflects the safety requirements of two neighboring cars. This optimal velocity is chosen in an ad hoc fashion by traffic engineers and is not related to a cost functional which defines "optimality" via a minimization procedure. Here we calculate in the context of serial production lines the "optimal velocity" (i.e., the optimal production control) based on a specific cost functional. We solve in chapter 4 an optimal control problem for the production rates where the cost structure penalizes the entrance of the buffer content into a boundary state. We show that the optimal control is of four thresholds type and give the optimal position of the thresholds. The optimal control problem, explicitly discussed for a serial two-stage production line, can not be solved analytically for longer lines. This forces us to look in chapter 5 for other ways to describe relations between the throughput and the work in process of production flows. The analogous quantities in traffic theory — flow of cars and car density — are related in the so-called fundamental diagram (fig. 0.2). It encodes in a single graph the functional relation between the flow of cars and the car-density. Inspired by the micro-macro paradigm of mechanical statistics, we derive from a mesoscopic level the fundamental diagram introduced by Greenshields in 1931. The study is based on the Boltzmann equations introduced by Ruijgrok and Wu, which we derive from a space discrete interacting particle system. The fundamental kinetic features of the microscopic model are migration, reaction and collisions of particles. Performing the hydrodynamic limit of the model, we have that the macroscopic density distribution ρ is governed by the Burgers equation and that the macroscopic flow J is proportional to the logistic equation. Fig. 0.2. Generic form of the density-flow relation in one-lane car traffic. Another property of production flows shared with cars in traffic is the simple fact that the circulating items have spatial extensions. This is of foremost importance especially when multiplexing structures are present in the production line and/or the traffic network. The distribution of items flowing out of a merge structure into a single collecting flow definitely depends on the physical size of the circulating items. In chapter 6 we will study a discrete materials flow merge system connected to a downstream station (fig. 0.3). The outflow process from the merge as a function of the the items extensions is given. Fig. 0.3. Merging of N streams of items into a buffer B. A conveyor transports the items from B to M. The spatial extensions of the items are crucial for the outflow. The mentioned discrete velocities Boltzmann equations of Ruijgrok and Wu are related to random evolutions. They are particularly well adapted to model the dynamics of failure prone machines switching between their states (e.g., between "on" and "off"). For the inhomogeneous two-states case (i.e., when the switching rates depend on the environment), we show in chapter 7 that the probability density and the associated probability current are in a supersymmetric relation — a algebraic structure well known in quantum mechanics. The quest to optimize throughput in stochastic manufacturing systems and vehicles flow in traffic systems can be unified through the following question: Given the initial distribution of items (of workload or cars) how do I have to influence the noisy dynamics in order to efficiently transport the items involved (workpieces or cars) to a given final distribution? This point of view seems natural to us and is directly related to a problem addressed by E. Schrödinger in 1931. He asks for a Markov diffusion process satisfying given initial and final conditions and which minimizes some energy functional. Based on this, we propose in chapter 8 an efficiency measure relevant for a large class of diffusion-mediated transport processes.
    Zusammenfassung
    Die vorliegende Arbeit hat zum Ziel dynamische Vorgänge in stochastischen Transportprozessen zu beschreiben, wie sie speziell in Massenproduktionsprozessen auftreten, wo dynamische Vorgänge entscheiden auf Kontrollund Optimierungsmöglichkeiten einwirken. Sie zeigt an explizit ausgearbeiteten Beispielen wie Konzepte der statistischen Mechanik, der Kontroll- und Warteschlangentheorie sowie der theoretischen Verkehrsdynamik zum besseren Verständnis solcher Vorgänge beitragen können. Die Arbeit umfasst mehrere Forschungsartikel die sich in diesem Sinne mit entsprechenden theoretischen Konzepten beschäftigen [38, 39, 42, 40, 44, 41, 43]. Wir beginnen mit der Bemerkung, dass verschiedene dynamische Phänomene wie sie im Strassenverkehr auftreten, ihr Analogon in Produktionsprozessen finden (Kapitel 3). Die dynamischen Analogien sind auf Ähnlichkeiten in den nichtlinearen Interaktionen zwischen den Prozessteilnehmer zurückzuführen. In Verkehrssystemen sind diese Interaktionen auf die sich lokal konkurrierenden Verkehrsteilnehmer beschränkt, die zwischen schnellem und sicherem Fahren optimieren. Dieses Verhalten ist bestimmend für die Geschwindigkeiten der einzelnen Verkehrsteilnehmer. In Produktionsprozessen werden die Interaktionen zwischen den kooperierenden Arbeitszellen lokalisiert, die als Ganzes den Prozess definieren. Sie beeinflussen in entscheidendem Masse die Produktionsstrategie und dadurch die globale Produktionskapazität des Prozesses. Wir bedienen uns dieser Analogie im Fall einer mit Bufferzonen ausgestatteten seriellen Produktionslinie, bei der die Produktionsraten einer Arbeitszelle durch den Lagerbestand der nächstliegenden Bufferzonen determiniert ist (Fig. 0.1). Ein erstes aus dieser Analogie sich ergebendes Resultat für Produktionsprozesse ist die Unterscheidung zwischen laminarem Produktionsfluss und turbulentem Produktionsfluss. Es sind dies Phasenzustände für Materialflüsse die in Verkehrssystemen seit langem intensiv studiert werden. Eine lineare Stabilitätsanalyse ermöglicht die explizite Berechnung eines Phasendiagramms in Abhängigkeit der Kontrollparameter. Eine dimensionslose dynamische Kennzahl ähnlich der Reynoldszahl wird eingeführt, der so genannte "bull-whip" Effekt wird angesprochen und der stabilisierende Effekt einer "Pull"-Produktionsstrategie wird disskutiert. Fig. 0.1. Above: Sketch of a serial production line composed of N machines Mi with production rates vi and N -1 buffers Bi with buffer content yi. Below: Sketch of a one-lane traffic system composed of N cars with velocities vi and headways xi. Dynamical similarities between cars and work-cells: the production rates and the car velocities, depend both on their environment e.g., the content of the next nearest buffers vi = vi(yi-1, yi) resp. the distances to the next nearest cars vi = vi(xi-1, xi). Die zur Beschreibung von seriellen Produktionsprozessen geeigneten Verkehrsmodelle sind so genannte "optimale Geschwindigkeit Fahrzeugfolgemodelle". Die optimalen Geschwindigkeiten sich folgender Fahrzeuge sind in aller Regel phänomenologisch angesetzte und von den Distanzen zu den nächsten Fahrzeugen abhängige Funktionen, die die Sicherheitsbedürfnisse der Lenker mit einbeziehen. Die Bezeichnung "optimal" wird von Verkehrsingenieuren nicht an eine Kostenfunktion gekoppelt und bezieht sich deshalb nicht auf ein wohldefiniertes Optimierungsproblem. Diesem Umstand wird in Kapitel 4 Rechnung getragen. Wir berechnen in der produktionstheoretischen Interpretation die Struktur der "optimalen Geschwindigkeit" (genauer, der "optimalen Produktionsraten") durch Einführung einer adäquaten Kostenfunktion und anschliessendem Lösen des Optimierungsproblems. Es wird gezeigt, dass die optimalen Produktionsraten durch vier Lagerbestandniveaus definiert werden können. Die Niveaus werden explizit berechnet. Das Optimierungsproblem kann explizit nur für serielle Produktionslinien mit (nur) zwei Arbeitszellen disskutiert werden. Dieser Umstand lässt uns in Kapitel 5 andere Wege suchen, um Durchfluss-Lagerbestandrelationen für längere Produktionslinien anzugeben. Die analogen Grössen in Verkehrssystemen — Verkehrsfluss und Verkehrsdichte — werden im so genannten Fundamentaldiagramm zusammengeführt (Fig. 0.2). Es entschlüsselt in einem einzigen Graphen die funktionale Beziehung zwischen dem Fahrzeugfluss und der Verkehrsdichte. Inspiriert durch das Mikro-Makro Paradigma der statistischen Mechanik leiten wir, ausgehend von einer mesoskopischen Beschreibungsebene, das wohlbekannte Fundamentaldiagramm von Greenshields ab. Die Studie basiert auf dem nichtlinearen, Boltzmann-ähnlichen Vielteilchenmodel von Ruijgrok und Wu. Die fundamentalen kinetischen Eigenschaften der Teilchen sind (i) Migration, (ii) Reaktion und (iii) Kollisionen. Folgende Interpretation als einfaches Verkehrsmodel ist möglich: (i) Fahren mit zwei möglichen Geschwindigkeiten, (ii) spontaner Wechsel zwischen den beiden möglichen Geschwindigkeiten (iii) Abbremsen eines schnellen Fahrzeugs das sich einem Langsamen nähert. Interpretiert als einfaches Model für serielle Produktionsprozesse, kann eingesehen werden, dass Migration eines Teilchens dem Weitertransport zu einer nächsten Arbeitszelle entspricht, dass der Reaktionsterm einer spontanen änderung des Operationszustandes der Zelle zugeordnet werden kann und dass Kollisionen angrenzender Zellen dann eintreffen, wenn der Lagerbestand dazwischen geleert wird. Im hydrodynamischen Limes wird gezeigt, dass die makroskopische Dichte ρ durch die "Burgersgleichung" gegeben ist und das der makroskopische Fluss proportional zur logistischen Gleichung ist J ∝ ρ(1-ρ). Fig. 0.2. Generic form of the density-flow relation in one-lane car traffic. Eine weitere Eigenschaft von Produktionsflüssen die mit Verkehrsflüssen geteilt wird, ist die granulare, platzkonsumierende Struktur der sich bewegenden Teilchen. Diese Bemerkung ist speziell dann von Wichtigkeit, wenn konvergente Strukturen, so genannte Multiplexer, vorhanden sind, die die Flüsse zusammenführen oder teilen. Das Zusammenführen mehrerer Flüsse zu einem gemeinsamen Materienstrom hängt klar von der räumlichen Ausdehnung der Teilchen ab und wird unter diesem Gesichtspunkt in Kapitel 6 untersucht (Fig. 0.3). Wir geben — unter geeigneten Hypothesen — die station äre Ausflussverteilung als Funktion der granularen Ausdehnung. Fig. 0.3. Merging of N streams of items into a buffer B. A conveyor transports the items from B to M. The spatial extensions of the items are crucial for the outflow. Die oben angesprochene Boltzmanngleichung von Ruijgrok und Wu kann, Dank einer logarithmischen Transformation, als "zufallsgesteuertes Evolutionsmodel" (random evolutions) interpretiert werden. Solch evolutive Systeme sind verbreitete Modellierungsmethoden die auch speziell geeignet sind, Maschinenausfälle ("Null-Eins" Dynamik) in die Dynamik aufzunehmen. Wir zeigen in Kapitel 7, dass im Falle einer Dynamik mit zwei möglichen Zuständen, die Wahrscheinlichkeitsdichte und der zugehörige Wahrscheinlichkeitsfluss (also die konstituierenden Grössen des Fundamentaldiagramms) in einer supersymmetrischen Beziehung stehen. Auf Grund der inhärenten Fluktuationen in Fabrikations- und Verkehrssystemen kann den Optimierungsmöglichkeiten beider Systeme folgende probabilistische Fragestellung zu Grunde gelegt werden: Gegeben eine Anfangsverteilung von Teilchen (von Jobs in den Arbeitszellen oder von Fahrzeugen auf dem Strassennetz), wie braucht die verrauschte Dynamik beeinflusst zu werden um die involvierten Teilchen (Jobs oder Fahrzeuge) effizient auf eine gegebene Endverteilung abzubilden? Diese Fragestellung scheint natürlich und kann direkt auf ein von E. Schrödinger gestelltes Problem zurückgeführt werden. Es besteht darin, zu gegebenen Anfangs- und Endbedingungen einen Diffusionsprozess zu konstruieren der ein Kostenfunktional minimiert. Basierend auf dieser allgemeinen Betrachtung wird in Kapitel 8 ein konzeptuell neues Effizienzmass für diffusionsunterstützte Transportprozesse eingeführt.
    Résumé
    La nécessité de maîtriser le pilotage des flux de produits délivrés par les processus de production opérant en environnement aléatoire (les aléas sont essentiellement dus aux enrayages des installations), nous a conduit à développer un ensemble de modèles mathématiques permettant de caractériser la dynamique et le contrôle de flux granulaires hors de l'équilibre thermodynamique. La thèse fait donc un usage intégré de concepts et de méthodes relevant de la mécanique statistique, de la théorie des files d'attentes, du trafic routier et de la théorie du contrôle optimal stochastique. Le travail regroupe et met en relations un ensemble de contributions dédiées aux phénomènes de transports d'objets circulant dans des installations de production [38, 39, 42, 40, 44, 41, 43]. Nous débutons par l'observation que nombreux sont les phénomènes dynamiques propres au trafic routier qui trouvent un analogue dans le domaine des flux de productions (Chapitre 3). Fondamentalement, ces similarités sont dues aux interactions non-linéaires entre les constituants présents dans ces deux types de systèmes. Dans le domaine du trafic routier, les interactions interviennent via les conducteurs qui tentent d'optimiser leur comportement en visant simultanément deux objectifs conflictuels à savoir, conduire avec célérité et sûreté. Dans le domaine des systèmes de production, les interactions interviennent entre les produits délivrés par les unités de production. En effet, les unités de production sont couplées via des convoyeurs et des zones de stockages dans lesquels les produits sont en interaction mutuelle. L'assèchement d'une ou plusieurs zones de stockage ou à l'opposé, leur saturation influe directement la dynamique des flux et détermineront les performances des systèmes de gestion de production. Les similarités formelles entre trafic routier et chaînes de production sont explorées dans le cadre concret d'une installation de type "flow-shop" (fig. 0.1), pour laquelle nous sommes conduit à distinguer entre des flux laminaires et des flux turbulents traversant l'installation. Par une analyse de stabilité, nous dérivons un diagramme de phases qui caractérise l'appartenance à l'un ou l'autre de ces régimes, ceci en fonction des paramètres de contrôle. Le point de vue interdisciplinaire adopté nous conduit à introduire un nouveau paramètre dynamique, jouant pour les chaînes de production, un rôle similaire au nombre de Reynolds en hydrodynamique. Fig. 0.1. Above: Sketch of a serial production line composed of N machines Mi with production rates vi and N -1 buffers Bi with buffer content yi. Below: Sketch of a one-lane traffic system composed of N cars with velocities vi and headways xi. Dynamical similarities between cars and work-cells: the production rates and the car velocities, depend both on their environment e.g., the content of the next nearest buffers vi = vi(yi-1, yi) resp. the distances to the next nearest cars vi = vi(xi-1, xi). Les modèles de trafic que nous utilisons pour les flux productions sont connus, dans le domaine du trafic de véhicules, comme étant du type "modèle à vitesse optimale". Ces modèles, de nature phénoménologique, tiennent compte simultanément de l'évolution en environnement aléatoire et des impératifs de sécurité requis par les conducteurs. Au chapitre 4, nous calculons, pour un dipôle de production, les "vitesses" optimales (i.e. la politique de production optimale) en utilisant un ensemble de critères d'optimisation naturels et pertinents pour les applications usuelles. Une extension directe du problème à des multipôles de production ne permet plus une approche analytique. C'est la raison pour laquelle nous proposons, au chapitre 5, un nouveau point de vue qui lui offre la possibilité de relier, dans les régimes stationnaires, l'amplitude du flux de production avec la densité locale des entités en circulation. Cette relation s'exprime via un diagramme — flux et densité — connu sous le nom le diagramme fondamental (fig.0.2) qui a été introduit par Greenshields en 1931. A partir de considérations purement microscopiques et en s'inspirant très directement du paradigme "micro-macroscopique" emprunté à la mécanique statistique, nous dérivons ce diagramme fondamental analytiquement. A cette fin, nous sommes amenés à introduire un niveau de description intermédiaire (i.e. le point de vue mésoscopique) qui fait appel à des équations de type Boltzmann avec des vitesses discrètes (modèle de Ruijgrok et Wu). Initialement, les propriétés cinétiques fondamentales des particules modélisées sont (i) migration, (ii) réaction et (iii) collision se traduisent en termes de trafic routier par (i) conduire avec deux vitesses possibles, (ii) modifier sa vitesse (iii) ralentir à cause de la présence d'une voiture plus lente en aval. Cette analogie exploitée dans le cadre de la production, nous permet de construire un modèle dynamique — fortement simplifié - qui décrit les multipôles de production. Les migrations et les réactions du modèle initial deviennent respectivement l'avancement d'une pièce et le changement d'état (i.e. marche- arrêt) d'une machine et une unité affamée correspond à une collision dans le domaine du trafic. Dans cette approche, il est remarquable que dans la limite hydrodynamique, la densité ρ obéisse à l'équation de Burgers alors que le flux J lui satisfasse à l'équation logistique J ∝ ρ(1-ρ). Fig. 0.2. Generic form of the density-flow relation in one-lane car traffic. Une autre propriété fondamentale commune aux flux de produits et aux flux de véhicules est l'extension spatiale des objets en circulation. La prise en compte de cette extension est tout particulièrement nécessaire lorsque l'on a affaire soit à des aiguillages soit à des multiplexeurs rassemblant plusieurs flux parallèles en un seul flux émergent. Cette problématique est discutée au chapitre 6, où nous caractérisons le flux de sortie d'un multiplexeur en fonction de la taille des objets en circulation (fig. 0.3). Fig. 0.3. Merging of N streams of items into a buffer B. A conveyor transports the items from B to M. The spatial extensions of the items are crucial for the outflow. L'équation de Boltzmann dans sa variante à vitesses discrètes, (i.e. le modèle de Ruijgrok et Wu mentionné précédemment), est très intimement connectée, via une transformation logarithmique, à des modèles d'évolution sujets à des changements aléatoires de vitesses. Ce point de vue est lui également adapté à la modélisation d'une unité de production sujette à des aléas et nous montrons au chapitre 7 que, sous certaines hypothèses, la densité de probabilité et son flux associé conjointement obéissent à une relation super-symétrique bien connue en mécanique quantique. Tout au long de notre travail, la présence ubiquitaire de fluctuations, nous amène à repenser la nature des problèmes d'optimisation des flux en termes purement probabilistes et directement inspiré par une ancienne mais fondamentale contribution de E. Schrödinger (1925). Comment, à partir d'un état initial aléatoire mais dont la distribution de probabilité est donnée, piloter l'évolution afin de réaliser un état final lui aussi aléatoire mais dont la distribution de probabilités est définie à priori et ceci tout en minimisant une fonction objectif donnée. Ce cadre général appliqué dans le domaine du transport, nous permet de proposer de nouveaux critères de performance pour le pilotage des flux granulaires et en particulier d'avancer une définition rigoureuse de l'efficacité des moteurs browniens.