Infoscience

Thesis

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

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.

    Thèse École polytechnique fédérale de Lausanne EPFL, n° 3247 (2005)
    Section de microtechnique
    Faculté des sciences et techniques de l'ingénieur
    Institut de microtechnique
    Laboratoire de production microtechnique 1
    Jury: Hannes Bleuler, Yves Dallery, Jacques Jacot, Thomas Mountford, Chris van den Broeck

    Public defense: 2005-5-27

    Reference

    Record created on 2005-04-06, modified on 2016-08-08

Related material