Continuous approximation of $ M_t/M_t/ 1 $ distributions with application to production

Dieter Armbruster; Simone Göttlich; Stephan Knapp

doi:10.3934/jcd.2020010

Article Contents

2020, Volume 7, Issue 2: 243-269. Doi: 10.3934/jcd.2020010

This issue Previous Article An incremental approach to online dynamic mode decomposition for time-varying systems with applications to EEG data modeling Next Article Numerical investigation of a neural field model including dendritic processing

Continuous approximation of $ M_t/M_t/ 1 $ distributions with application to production

1.
Arizona State University, School of Mathematical and Statistical Sciences, Tempe, AZ 85257-1804, USA
2.
University of Mannheim, Department of Mathematics, 68131 Mannheim, Germany

Received: October 2019

Published: July 2020

Abstract / Introduction Full Text(HTML) Figure(11) / Table(3) Related Papers Cited by

Abstract

A single queueing system with time-dependent exponentially distributed arrival processes and exponential machine processes (Kendall notation $ M_t/M_t/1 $) is analyzed. Modeling the time evolution for the discrete queue-length distribution by a continuous drift-diffusion process a Smoluchowski equation on the half space is derived approximating the forward Kolmogorov equations. The approximate model is analyzed and validated, showing excellent agreement for the probabilities of all queue lengths and for all queuing utilizations, including ones that are very small and some that are significantly larger than one. Having an excellent approximation for the probability of an empty queue generates an approximation of the expected outflow of the queueing system. Comparisons to several well-established approximations from the literature show significant improvements in several numerical examples.

Keywords:

Mathematics Subject Classification: 60K25, 90B30.

Citation:

FullText(HTML)

Figure 1. Graphical representation of a single queue service unit

Download: Full-size image PowerPoint slide

Figure 2. Comparison of queue-length distribution with exact ODE system and continuous approximation in the moderate ramp up case, (a) probability $ p_0(t) $, (b) $ p_3(t) $, (c) supremum error

Download: Full-size image PowerPoint slide

Figure 3. Comparison of queue-length distribution with exact ODE system and continuous approximation in the strong ramp up case, (a) probability $ p_0(t) $, (b) $ p_3(t) $, (c) supremum error

Download: Full-size image PowerPoint slide

Figure 4. Comparison of queue-length distribution with exact ODE system and continuous approximation in the very strong ramp up case, (a) probability $ p_0(t) $, (b) $ p_{10}(t) $, (c) $ p_{40}(t) $, (d) supremum error

Download: Full-size image PowerPoint slide

Figure 5. Comparison of queue-length distribution with exact ODE system and continuous approximation in the moderate ramp down case, (a) probability $ p_0(t) $, (b) $ p_3(t) $, (c) supremum error

Download: Full-size image PowerPoint slide

Figure 6. Comparison of queue-length distribution with exact ODE system and continuous approximation in the strong ramp down case, (a) probability $ p_0(t) $, (b) $ p_3(t) $, (c) supremum error

Download: Full-size image PowerPoint slide

Figure 7. Comparison of queue-length distribution with exact ODE system and continuous approximation in the moderate cyclic inflow rate case

Download: Full-size image PowerPoint slide

Figure 8. Comparison of queue-length distribution with exact ODE system and continuous approximation in the strong cyclic inflow rate case

Download: Full-size image PowerPoint slide

Figure 9. Comparison of queue-length distribution with exact ODE-system and continuous approximation in the very strong cyclic inflow rate case

Download: Full-size image PowerPoint slide

Figure 10. Comparison of the expected outflow using approximations from the literature (K, GVA, GSA) and our approach (A), where the inflow and processing rates are taken from [29], see (b)

Download: Full-size image PowerPoint slide

Figure 11. Comparison of the expected outflow using approximations from the literature (K, GVA, GSA) and our approach (A), where the inflow and processing rates are highly transient and periodic, see (b)

Download: Full-size image PowerPoint slide

Table 1. Error of the continuous approximation for different periods in the moderate, strong and very strong cyclic case

$ T_{\text{Per}} $		$ \max_j \\|\epsilon^A(t_j)\\|_\infty \;[10^{-3}] $
	moderate cyclic case	strong cyclic case	very strong cyclic case
25	1.4876	6.8495	6.5022
10	1.7911	8.8031	11.6854
5	2.2439	12.0694	17.2880
2	3.1356	17.1375	25.8903
1	3.2942	18.1220	30.9673

| Show Table

DownLoad: CSV

Table 2. Error between the approximations and the ODE system result for inflow from [29]

	$ \overline{Out}^\text{A}(t) $	$ \overline{Out}^\text{K}(t) $	$ \overline{Out}^\text{GVA}(t) $	$ \overline{Out}^\text{GSA}(t) $
$ \\|\cdot\\|_\infty $	$ 0.0457 $	$ 0.6830 $	$ 7.0672 $	$ 1.0314 $
$ \\|\cdot\\|_{L^1} $	$ 0.3522 $	$ 3.9450 $	$ 3.8772 $	$ 3.4053 $

| Show Table

DownLoad: CSV

Table 3. Error between the approximations and the ODE system result for cyclic inflow

	$ \overline{Out}^\text{A}(t) $	$ \overline{Out}^\text{K}(t) $	$ \overline{Out}^\text{GVA}(t) $	$ \overline{Out}^\text{GSA}(t) $
$ \\|\cdot\\|_\infty $	$ 0.0196 $	$ 0.9041 $	$ 0.5876 $	$ 0.2901 $
$ \\|\cdot\\|_{L^1} $	$ 0.2622 $	$ 10.5651 $	$ 4.8328 $	$ 2.8259 $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	D. Armbruster, D. Marthaler and C. Ringhofer, Kinetic and fluid model hierarchies for supply chains, Multiscale Model. Simul., 2 (2003), 43-61. doi: 10.1137/S1540345902419616.
[2]	D. Armbruster and R. Uzsoy, Continuous dynamic models, clearing functions, and discrete-event simulation in aggregate production planning, INFORMS TutORials in Operations Research, (2014). doi: 10.1287/educ.1120.0102.
[3]	D. Armbruster and M. Wienke, Kinetic models and intrinsic timescales: Simulation comparison for a 2nd order queueing model, Kinet. Relat. Models, 12 (2019), 177-193. doi: 10.3934/krm.2019008.
[4]	N. Bellomo, C. Bianca and V. Coscia, On the modeling of crowd dynamics: An overview and research perspectives, SeMA J., 54 (2011), 25-46. doi: 10.1007/bf03322586.
[5]	H. Chen and D. D. Yao, Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization, vol. 46, Springer-Verlag, New York, 2001. doi: 10.1007/978-1-4757-5301-1.
[6]	R. M. Colombo, M. Herty and M. Mercier, Control of the continuity equation with a non local flow, ESAIM Control Optim. Calc. Var., 17 (2011), 353-379. doi: 10.1051/cocv/2010007.
[7]	J.-M. Coron and Z. Wang, Controllability for a scalar conservation law with nonlocal velocity, J. Differential Equations, 252 (2012), 181-201. doi: 10.1016/j.jde.2011.08.042.
[8]	E. Cristiani, B. Piccoli and A. Tosin, Multiscale Modeling of Pedestrian Dynamics, vol. 12 of MS & A. Modeling, Simulation and Applications, Springer, Cham, 2014. doi: 10.1007/978-3-319-06620-2.
[9]	P. Degond and C. Ringhofer, Stochastic dynamics of long supply chains with random breakdowns, SIAM J. Appl. Math., 68 (2007), 59-79. doi: 10.1137/060674302.
[10]	M. Garavello and B. Piccoli, Traffic Flow on Networks, AIMS Series on Applied Mathematics, 1. American Institute of Mathematical Sciences (AIMS), Springfield, MO, 2006.
[11]	D. Gross, J. F. Shortle, J. M. Thompson and C. M. Harris, Fundamentals of Queueing Theory, 4th edition, Wiley Series in Probability and Statistics, John Wiley & Sons, Inc., Hoboken, NJ, 2008. doi: 10.1002/9781118625651.
[12]	C. Grossmann and H.-G. Roos, Numerical Treatment of Partial Differential Equations, Universitext, Springer, Berlin, 2007, Translated and revised from the 3rd (2005) German edition by Martin Stynes. doi: 10.1007/978-3-540-71584-9.
[13]	A. Keimer and L. Pflug, Existence, uniqueness and regularity results on nonlocal balance laws, J. Differential Equations, 263 (2017), 4023-4069. doi: 10.1016/j.jde.2017.05.015.
[14]	K. G. Kempf, P. Keskinocak and R. Uzsoy, Planning Production and Inventories in the Extended Enterprise, vol. 2, Springer, 2011.
[15]	Y. M. Ko and N. Gautam, Critically loaded time-varying multiserver queues: Computational challenges and approximations, INFORMS J. Comput., 25 (2013), 285-301. doi: 10.1287/ijoc.1120.0502.
[16]	M. La Marca, D. Armbruster, M. Herty and C. Ringhofer, Control of continuum models of production systems, IEEE Trans. Automat. Control, 55 (2010), 2511-2526. doi: 10.1109/TAC.2010.2046925.
[17]	O. A. Ladyženskaja, V. A. Solonnikov and N. N. Ural'ceva, Linear and Quasilinear Equations of Parabolic Type, Translated from the Russian by S. Smith. Translations of Mathematical Monographs, Vol. 23, American Mathematical Society, Providence, R.I., 1968.
[18]	G. Lamm and K. Schulten, Extended brownian dynamics. Ⅱ. reactive, nonlinear diffusion, J. Chem. Phys, 78 (1983), 2713-2734. doi: 10.1063/1.445002.
[19]	R. J. LeVeque, Finite Volume Methods for Hyperbolic Problems, Cambridge Texts in Applied Mathematics, Cambridge University Press, Cambridge, 2002. doi: 10.1017/CBO9780511791253.
[20]	M. J. Lighthill and G. B. Whitham, On kinematic waves Ⅱ. A theory of traffic flow on long crowded roads, Proc. Roy. Soc. London Ser. A, 229 (1955), 317-345. doi: 10.1098/rspa.1955.0089.
[21]	A. Mandelbaum and W. A. Massey, Strong approximations for time-dependent queues, Math. Oper. Res., 20 (1995), 33-64. doi: 10.1287/moor.20.1.33.
[22]	A. Mandelbaum, W. A. Massey and M. I. Reiman, Strong approximations for Markovian service networks, Queueing Systems Theory Appl., 30 (1998), 149-201. doi: 10.1023/A:1019112920622.
[23]	W. A. Massey and J. Pender, Gaussian skewness approximation for dynamic rate multi-server queues with abandonment, Queueing Syst., 75 (2013), 243-277. doi: 10.1007/s11134-012-9340-8.
[24]	G. F. Newell, Queues with time-dependent arrival rates. Ⅰ. The transition through saturation, J. Appl. Probability, 5 (1968), 436-451. doi: 10.2307/3212264.
[25]	G. F. Newell, Queues with time-dependent arrival rates. Ⅱ. The maximum queue and the return to equilibrium, J. Appl. Probability, 5 (1968), 579-590. doi: 10.1017/S0021900200114421.
[26]	G. F. Newell, Queues with time-dependent arrival rates. Ⅲ. A mild rush hour, J. Appl. Probability, 5 (1968), 591-606. doi: 10.1017/S0021900200114433.
[27]	J. Pender, A Poisson-Charlier approximation for nonstationary queues, Oper. Res. Lett., 42 (2014), 293-298. doi: 10.1016/j.orl.2014.05.001.
[28]	P. I. Richards, Shock waves on the highway, Operations Res., 4 (1956), 42-51. doi: 10.1287/opre.4.1.42.
[29]	K. L. Rider, A simple approximation to the average queue size in the time-dependent $M/M/1$ queue, J. Assoc. Comput. Mach., 23 (1976), 361-367. doi: 10.1145/321941.321955.
[30]	M. v. Smoluchowski, Drei Vorträge über Diffusion, Brownsche Molekularbewegung und Koagulation von Kolloidteilchen, part ⅰ and part ⅱ, Physik. Z., 17 (1916), 557–571 (part Ⅰ); 585–599 (part Ⅱ).
[31]	M. v. Smoluchowski, Über Brownsche Molekularbewegung unter Einwirkung äußerer Kräfte und deren Zusammenhang mit der verallgemeinerten Diffusionsgleichung, Ann. Physik, 48 (1916), 1103-1112.
[32]	W. A. Strauss, Partial Differential Equations, 2nd edition, John Wiley & Sons, Ltd., Chichester, 2008.
[33]	W.-P. Wang, D. Tipper and S. Banerjee, A Simple Approximation for Modeling Nonstationary Queues, in Proceedings of IEEE INFOCOM '96. Conference on Computer Communications, IEEE Comput. Soc. Press, 1996.
[34]	W. Whitt, Time-varying queues, Queueing Models and Service Management, 1 (2018), 079-164.
[35]	M. Wienke, An Aggregate Second Order Continuum Model for Transient Production Planning, PhD thesis, Arizona State University, 2015, https://repository.asu.edu/attachments/162150/content/Wienke_asu_0010E_15448.pdf