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.  Google Scholar

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

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

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

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

[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.  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. 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.  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. ArmbrusterD. 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. 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.  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. 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.  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. 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.  Google Scholar

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

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

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

Anna Abbatiello, Eduard Feireisl, Antoní Novotný. Generalized solutions to models of compressible viscous fluids. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 1-28. doi: 10.3934/dcds.2020345

[2]

Xin Guo, Lexin Li, Qiang Wu. Modeling interactive components by coordinate kernel polynomial models. Mathematical Foundations of Computing, 2020, 3 (4) : 263-277. doi: 10.3934/mfc.2020010

[3]

Urszula Ledzewicz, Heinz Schättler. On the role of pharmacometrics in mathematical models for cancer treatments. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 483-499. doi: 10.3934/dcdsb.2020213

[4]

P. K. Jha, R. Lipton. Finite element approximation of nonlocal dynamic fracture models. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1675-1710. doi: 10.3934/dcdsb.2020178

[5]

Wei Feng, Michael Freeze, Xin Lu. On competition models under allee effect: Asymptotic behavior and traveling waves. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5609-5626. doi: 10.3934/cpaa.2020256

[6]

Zhimin Li, Tailei Zhang, Xiuqing Li. Threshold dynamics of stochastic models with time delays: A case study for Yunnan, China. Electronic Research Archive, 2021, 29 (1) : 1661-1679. doi: 10.3934/era.2020085

[7]

Evelyn Sander, Thomas Wanner. Equilibrium validation in models for pattern formation based on Sobolev embeddings. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 603-632. doi: 10.3934/dcdsb.2020260

[8]

Shigui Ruan. Nonlinear dynamics in tumor-immune system interaction models with delays. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 541-602. doi: 10.3934/dcdsb.2020282

[9]

Eric Foxall. Boundary dynamics of the replicator equations for neutral models of cyclic dominance. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1061-1082. doi: 10.3934/dcdsb.2020153

[10]

Yanan Li, Zhijian Yang, Na Feng. Uniform attractors and their continuity for the non-autonomous Kirchhoff wave models. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021018

[11]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168

[12]

Annegret Glitzky, Matthias Liero, Grigor Nika. Dimension reduction of thermistor models for large-area organic light-emitting diodes. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020460

[13]

Yen-Luan Chen, Chin-Chih Chang, Zhe George Zhang, Xiaofeng Chen. Optimal preventive "maintenance-first or -last" policies with generalized imperfect maintenance models. Journal of Industrial & Management Optimization, 2021, 17 (1) : 501-516. doi: 10.3934/jimo.2020149

[14]

Xueli Bai, Fang Li. Global dynamics of competition models with nonsymmetric nonlocal dispersals when one diffusion rate is small. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3075-3092. doi: 10.3934/dcds.2020035

[15]

Wenbin Lv, Qingyuan Wang. Global existence for a class of Keller-Segel models with signal-dependent motility and general logistic term. Evolution Equations & Control Theory, 2021, 10 (1) : 25-36. doi: 10.3934/eect.2020040

[16]

Ching-Hui Wang, Sheng-Chen Fu. Traveling wave solutions to diffusive Holling-Tanner predator-prey models. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2021007

[17]

Yu-Jhe Huang, Zhong-Fu Huang, Jonq Juang, Yu-Hao Liang. Flocking of non-identical Cucker-Smale models on general coupling network. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1111-1127. doi: 10.3934/dcdsb.2020155

[18]

Sabine Hittmeir, Laura Kanzler, Angelika Manhart, Christian Schmeiser. Kinetic modelling of colonies of myxobacteria. Kinetic & Related Models, 2021, 14 (1) : 1-24. doi: 10.3934/krm.2020046

[19]

Toshiko Ogiwara, Danielle Hilhorst, Hiroshi Matano. Convergence and structure theorems for order-preserving dynamical systems with mass conservation. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3883-3907. doi: 10.3934/dcds.2020129

[20]

Lan Luo, Zhe Zhang, Yong Yin. Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial & Management Optimization, 2021, 17 (2) : 779-803. doi: 10.3934/jimo.2019134

2019 Impact Factor: 1.311

Metrics

  • PDF downloads (115)
  • HTML views (227)
  • Cited by (1)

Other articles
by authors

[Back to Top]