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

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

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.

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.

[2]

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

[3]

D. ArmbrusterD. E. MarthalerC. RinghoferK. 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.

[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.

[5]

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

[6]

G. BrettiC. D'ApiceR. 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.

[7]

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

[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.

[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.

[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.

[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.

[12]

J. DaiJ. 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.

[13]

C. D'ApiceR. 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.

[14]

L. Forestier-CosteS. 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.

[15]

S. GöttlichM. 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.

[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.

[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.

[18]

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

[19]

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

[20]

T. LiM. 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.

[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.

[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.

[23]

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

[24]

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

[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.

[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.

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.

[2]

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

[3]

D. ArmbrusterD. E. MarthalerC. RinghoferK. 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.

[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.

[5]

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

[6]

G. BrettiC. D'ApiceR. 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.

[7]

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

[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.

[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.

[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.

[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.

[12]

J. DaiJ. 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.

[13]

C. D'ApiceR. 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.

[14]

L. Forestier-CosteS. 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.

[15]

S. GöttlichM. 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.

[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.

[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.

[18]

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

[19]

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

[20]

T. LiM. 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.

[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.

[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.

[23]

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

[24]

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

[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.

[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.

Figure 1.  DES and exact input patterns Eq. (11) for the exponential relaxation scenario
Figure 2.  DES and exact input patterns for a) a stepwise transition scenario and b) a cyclic input scenario
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 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 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 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 7.  DES outflux for cyclic influx with range [0.3, 0.7] and slow and fast influx variations
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 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$
[1]

Chengjian Zhang, Lu Zhao. The attractors for 2nd-order stochastic delay lattice systems. Discrete & Continuous Dynamical Systems - A, 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]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

Martial Agueh, Guillaume Carlier, Reinhard Illner. Remarks on a class of kinetic models of granular media: Asymptotics and entropy bounds. Kinetic & Related Models, 2015, 8 (2) : 201-214. doi: 10.3934/krm.2015.8.201

[20]

Gabriella Puppo, Matteo Semplice, Andrea Tosin, Giuseppe Visconti. Kinetic models for traffic flow resulting in a reduced space of microscopic velocities. Kinetic & Related Models, 2017, 10 (3) : 823-854. doi: 10.3934/krm.2017033

2017 Impact Factor: 1.219

Metrics

  • PDF downloads (31)
  • HTML views (81)
  • Cited by (0)

Other articles
by authors

[Back to Top]