American Institute of Mathematical Sciences

Advanced
February  2019, 12(1): 177-193. doi: 10.3934/krm.2019008

Kinetic models and intrinsic timescales: Simulation comparison for a 2nd order queueing model

Dieter Armbruster and  Matthew Wienke

School of Mathematical and Statistical Sciences, Arizona State University, Tempe, AZ, 85287-1804, USA

Received  February 2018 Published  July 2018

Fund Project: D.A. gratefully acknowledges support through NSF grant DMS-1515592 and travel support through the KI-Net grant, NSF RNMS grant No. 1107291.

Kinetic models of stochastic production flows can be expanded into deterministic moment equations and thus approximated with appropriate closures. A second order model for the product density and the product speed has previously been proposed. A systematic analysis comparing simulations of the partial differential equations (PDE) with discrete event simulations (DES) is performed. Specifically, factory production is modeled as an M/M/1 queue where the arrival process is a non-homogeneous Poisson process. Three fundamental scenarios for such a time dependent influx are studied: An instant step up/step down of the arrival rate, an exponential step up/step down and periodic variation of the average arrival rate. It is shown that the second order model in general yields significant improvements over the first order model. Adding diffusion into the PDE further improves the agreement in particular for queues with low utilization. The analysis also points to fundamental open issues regarding kinetic models of time dependent agent based simulations. Memory effects and the possibility of resonance in deterministic models are caused by intrinsic timescales of the PDE that are not present in the original stochastic processes.

Keywords: Kinetic models, production systems, simulations, 2nd order models, transients.
Mathematics Subject Classification: 60K35, 90B30, 93A30.
Citation: Dieter Armbruster, Matthew Wienke. Kinetic models and intrinsic timescales: Simulation comparison for a 2nd order queueing model. Kinetic & Related Models, 2019, 12 (1) : 177-193. doi: 10.3934/krm.2019008
References:
[1]

D. Armbruster, J. Fonteijn and M. Wienke, Modeling production planning and transient clearing functions, in Robust Manufacturing Control, Springer, 2012, 77–88 doi: 10.1007/978-3-642-30749-2_6.  Google Scholar

[2]

D. Armbruster, D. Marthaler and C. Ringhofer, Kinetic and fluid model hierarchies for supply chains, Multiscale Modeling & Simulation, 2 (2003), 43-61.  doi: 10.1137/S1540345902419616.  Google Scholar

[3]

D. Armbruster, D. E. Marthaler, C. Ringhofer, K. Kempf and T.-C. Jo, A continuum model for a re-entrant factory, Operations Research, 54 (2006), 933-950.  doi: 10.1287/opre.1060.0321.  Google Scholar

[4]

A. Aw and M. Rascle, Resurrection of "second order" models of traffic flow, SIAM Journal on Applied Mathematics, 60 (2000), 916-938.  doi: 10.1137/S0036139997332099.  Google Scholar

[5]

M. Bramson, Stability of Queueing Networks, Springer-Verlag, New York, 2008.  Google Scholar

[6]

G. Bretti, C. D'Apice, R. Manzo and B. Piccoli, A continuum-discrete model for supply chains dynamics, Networks and Heterogeneous Media, 2 (2007), 661-694.  doi: 10.3934/nhm.2007.2.661.  Google Scholar

[7]

C. Cercignani, The Boltzmann Equation, Springer-Verlag, 1988. Google Scholar

[8]

J.-M. Coron and Z. Wang, Controllability for a scalar conservation law with nonlocal velocity, Journal of Differential Equations, 252 (2012), 181-201.  doi: 10.1016/j.jde.2011.08.042.  Google Scholar

[9]

J.-M. Coron, M. Kawski and Z. Wang, Analysis of a conservation law modeling a highly re-entrant manufacturing system, AIMS, 14 (2014), 1337–1359, arXiv: 0907.1274. doi: 10.3934/dcdsb.2010.14.1337.  Google Scholar

[10]

C. F. Daganzo, Requiem for second-order fluid approximations of traffic flow, Transportation Research Part B: Methodological, 29 (1995), 277-286.  doi: 10.1016/0191-2615(95)00007-Z.  Google Scholar

[11]

J. Dai, On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models, The Annals of Applied Probability, 5 (1995), 49-77.  doi: 10.1214/aoap/1177004828.  Google Scholar

[12]

J. Dai, J. Hasenbein and J. V. Vate, Stability and instability of a two-station queueing network, Annals of Applied Probability, 14 (2004), 326-377.  doi: 10.1214/aoap/1075828055.  Google Scholar

[13]

C. D'Apice, R. Manzo and B. Piccoli, Modelling supply networks with partial differential equations, Quarterly of Applied Mathematics, 67 (2009), 419-440.  doi: 10.1090/S0033-569X-09-01129-1.  Google Scholar

[14]

L. Forestier-Coste, S. Göttlich and M. Herty, Data-fitted second-order macroscopic production models, SIAM Journal on Applied Mathematics, 75 (2015), 999-1014.  doi: 10.1137/140989832.  Google Scholar

[15]

S. Göttlich, M. Herty and A. Klar, Network models for supply chains, Communications in Mathematical Sciences, 3 (2005), 545-559.  doi: 10.4310/CMS.2005.v3.n4.a5.  Google Scholar

[16]

A. Hofkamp, J. Rooda, R. Schiffelers and D. van Beek, Chi 2.0 Reference Manual, Technical report, Technical Report SE-Report 2008-02, Eindhoven University of Technology, Department of Mechanical Engineering, The Netherlands, 2008. http://se.wtb.tue.nl/sereports, 2007. Google Scholar

[17]

A. Keimer and L. Pflug, Existence, uniqueness and regularity results on nonlocal balance laws, Journal of Differential Equations, 263 (2017), 4023-4069.  doi: 10.1016/j.jde.2017.05.015.  Google Scholar

[18]

R. J. LeVeque, Numerical Methods for Conservation Laws, Second Edition, Birkhauser Verlag, Basel, Switzerland, 1992. doi: 10.1007/978-3-0348-8629-1.  Google Scholar

[19]

P. A. Lewis and G. S. Shedler, Simulation of Nonhomogeneous Poisson Processes by Thinning, Technical report, DTIC Document, 1978. Google Scholar

[20]

T. Li, M. Tang and X. Yang, An augmented keller-segal model for e. coli chemotaxis in fast-varying environments, Communication in Mathematical Sciences, 14 (2016), 883-891.  doi: 10.4310/CMS.2016.v14.n3.a12.  Google Scholar

[21]

M. J. Lighthill and G. B. Whitham, On kinematic waves. ⅱ. a theory of traffic flow on long crowded roads, Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 229 (1955), 317-345.  doi: 10.1098/rspa.1955.0089.  Google Scholar

[22]

J. D. C. Little, A proof of the queuing formula: L = $λ$w, Operations Research, 9 (1961), 383-387.  doi: 10.1287/opre.9.3.383.  Google Scholar

[23]

P. I. Richards, Shock waves on the highway, Operations Research, 4 (1956), 42-51.  doi: 10.1287/opre.4.1.42.  Google Scholar

[24]

S. M. Ross, Simulation, Fifth Edition, Academic Press, Oxford, 2013. doi: 10.1016/B978-0-12-415825-2.00001-2.  Google Scholar

[25]

P. Shang and Z. Wang, Analysis and control of a scalar conservation law modeling a highly re-entrant manufacturing system, Journal of Differential Equations, 250 (2011), 949-982.  doi: 10.1016/j.jde.2010.09.003.  Google Scholar

[26]

M. Sun, Singular solutions to the Riemann problem for a macroscopic production model, ZAMM-Journal of Applied Mathematics and Mechanics/Zeitschrift für Angewandte Mathematik und Mechanik, 97 (2017), 916-931.  doi: 10.1002/zamm.201600171.  Google Scholar

show all references

References:
[1]

D. Armbruster, J. Fonteijn and M. Wienke, Modeling production planning and transient clearing functions, in Robust Manufacturing Control, Springer, 2012, 77–88 doi: 10.1007/978-3-642-30749-2_6.  Google Scholar

[2]

D. Armbruster, D. Marthaler and C. Ringhofer, Kinetic and fluid model hierarchies for supply chains, Multiscale Modeling & Simulation, 2 (2003), 43-61.  doi: 10.1137/S1540345902419616.  Google Scholar

[3]

D. Armbruster, D. E. Marthaler, C. Ringhofer, K. Kempf and T.-C. Jo, A continuum model for a re-entrant factory, Operations Research, 54 (2006), 933-950.  doi: 10.1287/opre.1060.0321.  Google Scholar

[4]

A. Aw and M. Rascle, Resurrection of "second order" models of traffic flow, SIAM Journal on Applied Mathematics, 60 (2000), 916-938.  doi: 10.1137/S0036139997332099.  Google Scholar

[5]

M. Bramson, Stability of Queueing Networks, Springer-Verlag, New York, 2008.  Google Scholar

[6]

G. Bretti, C. D'Apice, R. Manzo and B. Piccoli, A continuum-discrete model for supply chains dynamics, Networks and Heterogeneous Media, 2 (2007), 661-694.  doi: 10.3934/nhm.2007.2.661.  Google Scholar

[7]

C. Cercignani, The Boltzmann Equation, Springer-Verlag, 1988. Google Scholar

[8]

J.-M. Coron and Z. Wang, Controllability for a scalar conservation law with nonlocal velocity, Journal of Differential Equations, 252 (2012), 181-201.  doi: 10.1016/j.jde.2011.08.042.  Google Scholar

[9]

J.-M. Coron, M. Kawski and Z. Wang, Analysis of a conservation law modeling a highly re-entrant manufacturing system, AIMS, 14 (2014), 1337–1359, arXiv: 0907.1274. doi: 10.3934/dcdsb.2010.14.1337.  Google Scholar

[10]

C. F. Daganzo, Requiem for second-order fluid approximations of traffic flow, Transportation Research Part B: Methodological, 29 (1995), 277-286.  doi: 10.1016/0191-2615(95)00007-Z.  Google Scholar

[11]

J. Dai, On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models, The Annals of Applied Probability, 5 (1995), 49-77.  doi: 10.1214/aoap/1177004828.  Google Scholar

[12]

J. Dai, J. Hasenbein and J. V. Vate, Stability and instability of a two-station queueing network, Annals of Applied Probability, 14 (2004), 326-377.  doi: 10.1214/aoap/1075828055.  Google Scholar

[13]

C. D'Apice, R. Manzo and B. Piccoli, Modelling supply networks with partial differential equations, Quarterly of Applied Mathematics, 67 (2009), 419-440.  doi: 10.1090/S0033-569X-09-01129-1.  Google Scholar

[14]

L. Forestier-Coste, S. Göttlich and M. Herty, Data-fitted second-order macroscopic production models, SIAM Journal on Applied Mathematics, 75 (2015), 999-1014.  doi: 10.1137/140989832.  Google Scholar

[15]

S. Göttlich, M. Herty and A. Klar, Network models for supply chains, Communications in Mathematical Sciences, 3 (2005), 545-559.  doi: 10.4310/CMS.2005.v3.n4.a5.  Google Scholar

[16]

A. Hofkamp, J. Rooda, R. Schiffelers and D. van Beek, Chi 2.0 Reference Manual, Technical report, Technical Report SE-Report 2008-02, Eindhoven University of Technology, Department of Mechanical Engineering, The Netherlands, 2008. http://se.wtb.tue.nl/sereports, 2007. Google Scholar

[17]

A. Keimer and L. Pflug, Existence, uniqueness and regularity results on nonlocal balance laws, Journal of Differential Equations, 263 (2017), 4023-4069.  doi: 10.1016/j.jde.2017.05.015.  Google Scholar

[18]

R. J. LeVeque, Numerical Methods for Conservation Laws, Second Edition, Birkhauser Verlag, Basel, Switzerland, 1992. doi: 10.1007/978-3-0348-8629-1.  Google Scholar

[19]

P. A. Lewis and G. S. Shedler, Simulation of Nonhomogeneous Poisson Processes by Thinning, Technical report, DTIC Document, 1978. Google Scholar

[20]

T. Li, M. Tang and X. Yang, An augmented keller-segal model for e. coli chemotaxis in fast-varying environments, Communication in Mathematical Sciences, 14 (2016), 883-891.  doi: 10.4310/CMS.2016.v14.n3.a12.  Google Scholar

[21]

M. J. Lighthill and G. B. Whitham, On kinematic waves. ⅱ. a theory of traffic flow on long crowded roads, Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 229 (1955), 317-345.  doi: 10.1098/rspa.1955.0089.  Google Scholar

[22]

J. D. C. Little, A proof of the queuing formula: L = $λ$w, Operations Research, 9 (1961), 383-387.  doi: 10.1287/opre.9.3.383.  Google Scholar

[23]

P. I. Richards, Shock waves on the highway, Operations Research, 4 (1956), 42-51.  doi: 10.1287/opre.4.1.42.  Google Scholar

[24]

S. M. Ross, Simulation, Fifth Edition, Academic Press, Oxford, 2013. doi: 10.1016/B978-0-12-415825-2.00001-2.  Google Scholar

[25]

P. Shang and Z. Wang, Analysis and control of a scalar conservation law modeling a highly re-entrant manufacturing system, Journal of Differential Equations, 250 (2011), 949-982.  doi: 10.1016/j.jde.2010.09.003.  Google Scholar

[26]

M. Sun, Singular solutions to the Riemann problem for a macroscopic production model, ZAMM-Journal of Applied Mathematics and Mechanics/Zeitschrift für Angewandte Mathematik und Mechanik, 97 (2017), 916-931.  doi: 10.1002/zamm.201600171.  Google Scholar

Figure 1.  DES and exact input patterns Eq. (11) for the exponential relaxation scenario
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  DES and exact input patterns for a) a stepwise transition scenario and b) a cyclic input scenario
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  DES simulations and solutions of the $1^{st}$ order PDE (Eq. (14)) for the exponential relaxation scenario and the stepwise transition scenario for up and down transitions between $\lambda = 0.3$ and $\lambda = 0.7$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  DES simulations and solutions of the $2^{nd}$ order PDE (Eq. (15)) for the exponential relaxation scenario and the stepwise transition scenario for up and down transitions between $\lambda = 0.3$ and $\lambda = 0.7$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  DES simulations and solutions of the $2^{nd}$ order PDE with diffusion Eq. (16) for the exponential relaxation scenario and the stepwise transition scenario for up and down transitions between $\lambda = 0.3$ and $\lambda = 0.7$. The diffusion coefficient is set at $D = 0.1$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  DES (blue) and PDE (red) outflux for cyclic influx with range [0.3, 0.7] and period $T = 12$ with phase adjusted solution (green)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  DES outflux for cyclic influx with range [0.3, 0.7] and slow and fast influx variations
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 8.  Normalized output amplitude as a function of the input frequency for DES and PDE simulations. a) mean utilization $\bar{u} = 0.6$, b) $\bar{u} = 0.5$, c) $\bar{u} = 0.4$. We see resonances for the forcing frequency to be approximately equal to the mean queuing frequencies $\bar{\nu} = 0.5$ in b) and $\bar{\nu} = 0.6$ and a harmonic $2 \bar{\nu} = 1.2$ for (c)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 9.  Delay between the PDE simulation and the DES for the exponential relaxation scenario and the stepwise transition scenario. The asterisks mark simulation results and the curve shows the mean waiting time for an M/M/1 queue as a function of the influx parameter $\lambda$
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Chengjian Zhang, Lu Zhao. The attractors for 2nd-order stochastic delay lattice systems. Discrete & Continuous Dynamical Systems, 2017, 37 (1) : 575-590. doi: 10.3934/dcds.2017023
[2]

N. Bellomo, A. Bellouquid. From a class of kinetic models to the macroscopic equations for multicellular systems in biology. Discrete & Continuous Dynamical Systems - B, 2004, 4 (1) : 59-80. doi: 10.3934/dcdsb.2004.4.59
[3]

Pierre Carcaud, Pierre-Henri Chavanis, Mohammed Lemou, Florian Méhats. Evaporation law in kinetic gravitational systems described by simplified Landau models. Discrete & Continuous Dynamical Systems - B, 2010, 14 (3) : 907-934. doi: 10.3934/dcdsb.2010.14.907
[4]

Pierre Degond, Hailiang Liu. Kinetic models for polymers with inertial effects. Networks & Heterogeneous Media, 2009, 4 (4) : 625-647. doi: 10.3934/nhm.2009.4.625
[5]

Seung-Yeal Ha, Doron Levy. Particle, kinetic and fluid models for phototaxis. Discrete & Continuous Dynamical Systems - B, 2009, 12 (1) : 77-108. doi: 10.3934/dcdsb.2009.12.77
[6]

Michael Herty, Gabriella Puppo, Sebastiano Roncoroni, Giuseppe Visconti. The BGK approximation of kinetic models for traffic. Kinetic & Related Models, 2020, 13 (2) : 279-307. doi: 10.3934/krm.2020010
[7]

Wen Li, Song Wang, Volker Rehbock. A 2nd-order one-point numerical integration scheme for fractional ordinary differential equations. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 273-287. doi: 10.3934/naco.2017018
[8]

P. Bai, H.T. Banks, S. Dediu, A.Y. Govan, M. Last, A.L. Lloyd, H.K. Nguyen, M.S. Olufsen, G. Rempala, B.D. Slenning. Stochastic and deterministic models for agricultural production networks. Mathematical Biosciences & Engineering, 2007, 4 (3) : 373-402. doi: 10.3934/mbe.2007.4.373
[9]

Dieter Armbruster, Michael Herty, Xinping Wang, Lindu Zhao. Integrating release and dispatch policies in production models. Networks & Heterogeneous Media, 2015, 10 (3) : 511-526. doi: 10.3934/nhm.2015.10.511
[10]

Simone Göttlich, Stephan Knapp. Semi-Markovian capacities in production network models. Discrete & Continuous Dynamical Systems - B, 2017, 22 (9) : 3235-3258. doi: 10.3934/dcdsb.2017090
[11]

Renato Colucci, Javier López-de-la-Cruz. Dynamics of fermentation models for the production of dry and sweet wine. Communications on Pure & Applied Analysis, 2020, 19 (4) : 2015-2034. doi: 10.3934/cpaa.2020089
[12]

Carsten Hartmann, Juan C. Latorre, Wei Zhang, Grigorios A. Pavliotis. Addendum to "Optimal control of multiscale systems using reduced-order models". Journal of Computational Dynamics, 2017, 4 (1&2) : 167-167. doi: 10.3934/jcd.2017006
[13]

Carsten Hartmann, Juan C. Latorre, Wei Zhang, Grigorios A. Pavliotis. Optimal control of multiscale systems using reduced-order models. Journal of Computational Dynamics, 2014, 1 (2) : 279-306. doi: 10.3934/jcd.2014.1.279
[14]

Michael Herty, Christian Ringhofer. Averaged kinetic models for flows on unstructured networks. Kinetic & Related Models, 2011, 4 (4) : 1081-1096. doi: 10.3934/krm.2011.4.1081
[15]

Pierre Monmarché. Hypocoercive relaxation to equilibrium for some kinetic models. Kinetic & Related Models, 2014, 7 (2) : 341-360. doi: 10.3934/krm.2014.7.341
[16]

Alina Chertock, Changhui Tan, Bokai Yan. An asymptotic preserving scheme for kinetic models with singular limit. Kinetic & Related Models, 2018, 11 (4) : 735-756. doi: 10.3934/krm.2018030
[17]

Ali K. Unver, Christian Ringhofer, M. Emir Koksal. Parameter extraction of complex production systems via a kinetic approach. Kinetic & Related Models, 2016, 9 (2) : 407-427. doi: 10.3934/krm.2016.9.407
[18]

H. W. Broer, Renato Vitolo. Dynamical systems modeling of low-frequency variability in low-order atmospheric models. Discrete & Continuous Dynamical Systems - B, 2008, 10 (2&3, September) : 401-419. doi: 10.3934/dcdsb.2008.10.401
[19]

Alina Chertock, Alexander Kurganov, Mária Lukáčová-Medvi${\rm{\check{d}}}$ová, Șeyma Nur Özcan. An asymptotic preserving scheme for kinetic chemotaxis models in two space dimensions. Kinetic & Related Models, 2019, 12 (1) : 195-216. doi: 10.3934/krm.2019009
[20]

H.J. Hwang, K. Kang, A. Stevens. Drift-diffusion limits of kinetic models for chemotaxis: A generalization. Discrete & Continuous Dynamical Systems - B, 2005, 5 (2) : 319-334. doi: 10.3934/dcdsb.2005.5.319

2020 Impact Factor: 1.432

Tools

Metrics

  • PDF downloads (193)
  • HTML views (230)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy