November  2017, 22(9): 3235-3258. doi: 10.3934/dcdsb.2017090

Semi-Markovian capacities in production network models

University of Mannheim, Department of Mathematics, 68131 Mannheim, Germany

* Corresponding author: Simone Göttlich

Received  July 2016 Revised  December 2016 Published  March 2017

Fund Project: This work was financially supported by the DAAD project "DAAD-PPP VR China" (Projekt-ID: 57215936)

In this paper, we focus on production network models based on ordinary and partial differential equations that are coupled to semi-Markovian failure rates for the processor capacities. This modeling approach allows for intermediate capacity states in the range of total breakdown to full capacity, where operating and down times might be arbitrarily distributed. The mathematical challenge is to combine the theory of semi-Markovian processes within the framework of conservation laws. We show the existence and uniqueness of such stochastic network solutions, present a suitable simulation method and explain the link to the common queueing theory. A variety of numerical examples emphasizes the characteristics of the proposed approach.

Citation: 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
References:
[1]

D. ArmbrusterP. Degond and C. Ringhofer, A model for the dynamics of large queuing networks and supply chains, SIAM J. Appl. Math., 66 (2006), 896-920.  doi: 10.1137/040604625.  Google Scholar

[2]

J. Banks, J. S. Carson, B. L. Nelson and D. M. Nicol, Discrete-Event System Simulation 5th edition, Pearson, 2010. Google Scholar

[3]

C. D'Apice, S. Göttlich, M. Herty and B. Piccoli, Modeling, Simulation, and Optimization of Supply Chains 1st edition, SIAM, Philadelphia, 2010. doi: 10.1137/1.9780898717600.  Google Scholar

[4]

C. D'ApiceP. I. Kogut and R. Manzo, On relaxation of state constrained optimal control problem for a PDE-ODE model of supply chains, Netw. Heterog. Media, 9 (2014), 501-518.  doi: 10.3934/nhm.2014.9.501.  Google Scholar

[5]

C. D'ApiceR. Manzo and B. Piccoli, Modelling supply networks with partial differential equations, Quart. Appl. Math., 67 (2009), 419-440.  doi: 10.1090/S0033-569X-09-01129-1.  Google Scholar

[6]

C. D'ApiceR. Manzo and B. Piccoli, Existence of solutions to Cauchy problems for a mixed continuum-discrete model for supply chains and networks, J. Math. Anal. Appl., 362 (2010), 374-386.  doi: 10.1016/j.jmaa.2009.07.058.  Google Scholar

[7]

C. D'ApiceR. Manzo and B. Piccoli, Optimal input flows for a PDE-ODE model of supply chains, Commun. Math. Sci., 10 (2012), 1225-1240.  doi: 10.4310/CMS.2012.v10.n4.a10.  Google Scholar

[8]

C. D'ApiceR. Manzo and B. Piccoli, Numerical schemes for the optimal input flow of a supply chain, SIAM J. Numer. Anal., 51 (2013), 2634-2650.  doi: 10.1137/120889721.  Google Scholar

[9]

M. H. A. Davis, Piecewise-deterministic {M}arkov processes: A general class of nondiffusion stochastic models, J. Roy. Statist. Soc. Ser. B, 46 (1984), 353-388.   Google Scholar

[10]

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

[11]

L. Forestier-CosteS. Göttlich and M. Herty, Data-fitted second-order macroscopic production models, SIAM J. Appl. Math., 75 (2015), 999-1014.  doi: 10.1137/140989832.  Google Scholar

[12]

D. T. Gillespie, A general method for numerically simulating the stochastic time evolution of coupled chemical reactions, J. Computational Phys., 22 (1976), 403-434.  doi: 10.1016/0021-9991(76)90041-3.  Google Scholar

[13]

D. T. Gillespie, Approximate accelerated stochastic simulation of chemically reacting systems, J. Chem. Phys., 115 (2001), 1716-1733.  doi: 10.1063/1.1378322.  Google Scholar

[14]

S. GöttlichM. Herty and A. Klar, Network models for supply chains, Commun. Math. Sci., 3 (2005), 545-559.  doi: 10.4310/CMS.2005.v3.n4.a5.  Google Scholar

[15]

S. GöttlichM. Herty and C. Ringhofer, Optimization of order policies in supply networks, European J. Oper. Res., 202 (2010), 456-465.  doi: 10.1016/j.ejor.2009.05.028.  Google Scholar

[16]

S. GöttlichA. Klar and S. Tiwari, Complex material flow problems: A multi-scale model hierarchy and particle methods, J. Engrg. Math, 92 (2015), 15-29.  doi: 10.1007/s10665-014-9767-5.  Google Scholar

[17]

S. GöttlichS. Martin and T. Sickenberger, Time-continuous production networks with random breakdowns, Netw. Heterog. Media, 6 (2011), 695-714.  doi: 10.3934/nhm.2011.6.695.  Google Scholar

[18]

F. Grabski, Semi-Markov failure rates processes, Appl. Math. Comput., 217 (2011), 9956-9965.  doi: 10.1016/j.amc.2011.04.055.  Google Scholar

[19]

F. Grabski, Semi-Markov Processes: Applications in System Reliability and Maintenance, 1st edition, Elsevier, Amsterdam, 2015. doi: 10.1007/978-1-4612-0873-0.  Google Scholar

[20]

D. Gross, J. F. Shortle, J. M. Thompson and C. M. Harris, Fundamentals of Queueing Theory, 4th edition, John Wiley & Sons, Inc. , Hoboken, NJ, 2008. doi: 10.1002/9781118625651.  Google Scholar

[21]

B. Harlamov, Continuous Semi-{M}arkov Processes, 1st edition, ISTE, London; John Wiley & Sons, Inc. , Hoboken, NJ, 2008. doi: 10.1002/9780470610923.  Google Scholar

[22]

M. Kolonko, Stochastische Simulation, (German) [Stochastic Simulation], 1st edition, Vieweg+Teubner Verlag, Wiesbaden, 2008. doi: 10.1007/978-3-8348-9290-4.  Google Scholar

[23]

A. M. Lee, Applied Queueing Theory, Reprint edition, Macmillan [u. a. ], London [u. a. ], 1966. doi: 10.1007/978-1-349-00273-3.  Google Scholar

[24]

L. Lipsky, Queueing Theory, 2nd edition, Springer, New York, 2009. doi: 10.1007/978-0-387-49706-8.  Google Scholar

[25]

J. Medhi, Stochastic Processes, 3rd edition, New Age Science, Tunbridge Wells, 2010. Google Scholar

[26]

J. R. Norris, Markov Chains, Reprint edition, Cambridge University Press, Cambridge, 1998.  Google Scholar

[27]

R. Pyke, Markov renewal processes: Definitions and preliminary properties, Ann. Math. Statist., 32 (1961), 1231-1242.  doi: 10.1214/aoms/1177704863.  Google Scholar

show all references

References:
[1]

D. ArmbrusterP. Degond and C. Ringhofer, A model for the dynamics of large queuing networks and supply chains, SIAM J. Appl. Math., 66 (2006), 896-920.  doi: 10.1137/040604625.  Google Scholar

[2]

J. Banks, J. S. Carson, B. L. Nelson and D. M. Nicol, Discrete-Event System Simulation 5th edition, Pearson, 2010. Google Scholar

[3]

C. D'Apice, S. Göttlich, M. Herty and B. Piccoli, Modeling, Simulation, and Optimization of Supply Chains 1st edition, SIAM, Philadelphia, 2010. doi: 10.1137/1.9780898717600.  Google Scholar

[4]

C. D'ApiceP. I. Kogut and R. Manzo, On relaxation of state constrained optimal control problem for a PDE-ODE model of supply chains, Netw. Heterog. Media, 9 (2014), 501-518.  doi: 10.3934/nhm.2014.9.501.  Google Scholar

[5]

C. D'ApiceR. Manzo and B. Piccoli, Modelling supply networks with partial differential equations, Quart. Appl. Math., 67 (2009), 419-440.  doi: 10.1090/S0033-569X-09-01129-1.  Google Scholar

[6]

C. D'ApiceR. Manzo and B. Piccoli, Existence of solutions to Cauchy problems for a mixed continuum-discrete model for supply chains and networks, J. Math. Anal. Appl., 362 (2010), 374-386.  doi: 10.1016/j.jmaa.2009.07.058.  Google Scholar

[7]

C. D'ApiceR. Manzo and B. Piccoli, Optimal input flows for a PDE-ODE model of supply chains, Commun. Math. Sci., 10 (2012), 1225-1240.  doi: 10.4310/CMS.2012.v10.n4.a10.  Google Scholar

[8]

C. D'ApiceR. Manzo and B. Piccoli, Numerical schemes for the optimal input flow of a supply chain, SIAM J. Numer. Anal., 51 (2013), 2634-2650.  doi: 10.1137/120889721.  Google Scholar

[9]

M. H. A. Davis, Piecewise-deterministic {M}arkov processes: A general class of nondiffusion stochastic models, J. Roy. Statist. Soc. Ser. B, 46 (1984), 353-388.   Google Scholar

[10]

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

[11]

L. Forestier-CosteS. Göttlich and M. Herty, Data-fitted second-order macroscopic production models, SIAM J. Appl. Math., 75 (2015), 999-1014.  doi: 10.1137/140989832.  Google Scholar

[12]

D. T. Gillespie, A general method for numerically simulating the stochastic time evolution of coupled chemical reactions, J. Computational Phys., 22 (1976), 403-434.  doi: 10.1016/0021-9991(76)90041-3.  Google Scholar

[13]

D. T. Gillespie, Approximate accelerated stochastic simulation of chemically reacting systems, J. Chem. Phys., 115 (2001), 1716-1733.  doi: 10.1063/1.1378322.  Google Scholar

[14]

S. GöttlichM. Herty and A. Klar, Network models for supply chains, Commun. Math. Sci., 3 (2005), 545-559.  doi: 10.4310/CMS.2005.v3.n4.a5.  Google Scholar

[15]

S. GöttlichM. Herty and C. Ringhofer, Optimization of order policies in supply networks, European J. Oper. Res., 202 (2010), 456-465.  doi: 10.1016/j.ejor.2009.05.028.  Google Scholar

[16]

S. GöttlichA. Klar and S. Tiwari, Complex material flow problems: A multi-scale model hierarchy and particle methods, J. Engrg. Math, 92 (2015), 15-29.  doi: 10.1007/s10665-014-9767-5.  Google Scholar

[17]

S. GöttlichS. Martin and T. Sickenberger, Time-continuous production networks with random breakdowns, Netw. Heterog. Media, 6 (2011), 695-714.  doi: 10.3934/nhm.2011.6.695.  Google Scholar

[18]

F. Grabski, Semi-Markov failure rates processes, Appl. Math. Comput., 217 (2011), 9956-9965.  doi: 10.1016/j.amc.2011.04.055.  Google Scholar

[19]

F. Grabski, Semi-Markov Processes: Applications in System Reliability and Maintenance, 1st edition, Elsevier, Amsterdam, 2015. doi: 10.1007/978-1-4612-0873-0.  Google Scholar

[20]

D. Gross, J. F. Shortle, J. M. Thompson and C. M. Harris, Fundamentals of Queueing Theory, 4th edition, John Wiley & Sons, Inc. , Hoboken, NJ, 2008. doi: 10.1002/9781118625651.  Google Scholar

[21]

B. Harlamov, Continuous Semi-{M}arkov Processes, 1st edition, ISTE, London; John Wiley & Sons, Inc. , Hoboken, NJ, 2008. doi: 10.1002/9780470610923.  Google Scholar

[22]

M. Kolonko, Stochastische Simulation, (German) [Stochastic Simulation], 1st edition, Vieweg+Teubner Verlag, Wiesbaden, 2008. doi: 10.1007/978-3-8348-9290-4.  Google Scholar

[23]

A. M. Lee, Applied Queueing Theory, Reprint edition, Macmillan [u. a. ], London [u. a. ], 1966. doi: 10.1007/978-1-349-00273-3.  Google Scholar

[24]

L. Lipsky, Queueing Theory, 2nd edition, Springer, New York, 2009. doi: 10.1007/978-0-387-49706-8.  Google Scholar

[25]

J. Medhi, Stochastic Processes, 3rd edition, New Age Science, Tunbridge Wells, 2010. Google Scholar

[26]

J. R. Norris, Markov Chains, Reprint edition, Cambridge University Press, Cambridge, 1998.  Google Scholar

[27]

R. Pyke, Markov renewal processes: Definitions and preliminary properties, Ann. Math. Statist., 32 (1961), 1231-1242.  doi: 10.1214/aoms/1177704863.  Google Scholar

Figure 1.  General idea of a semi-Markov process
Figure 2.  Sample path and its pseudo inverse
Figure 3.  Comparison with $\lambda = 0.1$
Figure 4.  Comparison with $\lambda = 0.5$
Figure 5.  Comparison with $\lambda = 0.75$
Figure 6.  Comparison with $\lambda = 1.25$
Figure 7.  Graph representation of the CTMCs
Figure 8.  Difference of the sampled mean an variance densities
Figure 9.  Sampled mean and variance of the queue-loads
Figure 10.  Sample mean and variance of the network outflow
Figure 11.  Difference of the sample mean and variance densities
Figure 12.  Sample mean and variance of the queue-loads
Figure 13.  Sample mean and variance of the network outflow
Figure 14.  Histogram of production times
Figure 15.  Different pdf of the gamma distribution
Figure 16.  erial network with five processors
Figure 17.  Sample mean of the density in the exponential case
Figure 18.  Sampled mean of the density with $\alpha = 4$ and $\alpha = 0.25$
Figure 19.  Sampled mean and variance of the network outflow
Figure 20.  Comparison of the sample mean and variance of the first processor capacity process
Figure 21.  Comparison of the sample mean of the network outflow and the network queue-loads
Figure 22.  Comparison of the sample variance of the network outflow and the network queue-loads
Figure 23.  Comparison of the production time for 0.9 amount of goods
Table 1.  Sample mean and variance of the production time
Case 1Case 2
$\overline{\tau}_{prod}(\infty)$2.23572.2197
$\sigma^2(\tau_{prod}(\infty))$0.05290.0466
Case 1Case 2
$\overline{\tau}_{prod}(\infty)$2.23572.2197
$\sigma^2(\tau_{prod}(\infty))$0.05290.0466
Table 2.  Parameters of the network model with five processors
Processor e12345
MTBF0.95 $\infty$0.851.90.95
MRT0.0500.150.100.05
Processor e12345
MTBF0.95 $\infty$0.851.90.95
MRT0.0500.150.100.05
Table 3.  Sample mean and variance of the network queue-load
$\alpha = \frac{1}{4}$$\alpha = 1$ $\alpha = 4$
$\overline{q^{net}(4)}$1.33611.73912.8382
$\sigma^2(q^{net}(4))$0.32781.25885.1694
$\alpha = \frac{1}{4}$$\alpha = 1$ $\alpha = 4$
$\overline{q^{net}(4)}$1.33611.73912.8382
$\sigma^2(q^{net}(4))$0.32781.25885.1694
[1]

Mauro Garavello. A review of conservation laws on networks. Networks & Heterogeneous Media, 2010, 5 (3) : 565-581. doi: 10.3934/nhm.2010.5.565

[2]

Georges Bastin, B. Haut, Jean-Michel Coron, Brigitte d'Andréa-Novel. Lyapunov stability analysis of networks of scalar conservation laws. Networks & Heterogeneous Media, 2007, 2 (4) : 751-759. doi: 10.3934/nhm.2007.2.751

[3]

Martin Gugat, Alexander Keimer, Günter Leugering, Zhiqiang Wang. Analysis of a system of nonlocal conservation laws for multi-commodity flow on networks. Networks & Heterogeneous Media, 2015, 10 (4) : 749-785. doi: 10.3934/nhm.2015.10.749

[4]

Yanning Li, Edward Canepa, Christian Claudel. Efficient robust control of first order scalar conservation laws using semi-analytical solutions. Discrete & Continuous Dynamical Systems - S, 2014, 7 (3) : 525-542. doi: 10.3934/dcdss.2014.7.525

[5]

Avner Friedman. Conservation laws in mathematical biology. Discrete & Continuous Dynamical Systems - A, 2012, 32 (9) : 3081-3097. doi: 10.3934/dcds.2012.32.3081

[6]

Mauro Garavello, Roberto Natalini, Benedetto Piccoli, Andrea Terracina. Conservation laws with discontinuous flux. Networks & Heterogeneous Media, 2007, 2 (1) : 159-179. doi: 10.3934/nhm.2007.2.159

[7]

Len G. Margolin, Roy S. Baty. Conservation laws in discrete geometry. Journal of Geometric Mechanics, 2019, 11 (2) : 187-203. doi: 10.3934/jgm.2019010

[8]

Wen-Xiu Ma. Conservation laws by symmetries and adjoint symmetries. Discrete & Continuous Dynamical Systems - S, 2018, 11 (4) : 707-721. doi: 10.3934/dcdss.2018044

[9]

Tai-Ping Liu, Shih-Hsien Yu. Hyperbolic conservation laws and dynamic systems. Discrete & Continuous Dynamical Systems - A, 2000, 6 (1) : 143-145. doi: 10.3934/dcds.2000.6.143

[10]

Yanbo Hu, Wancheng Sheng. The Riemann problem of conservation laws in magnetogasdynamics. Communications on Pure & Applied Analysis, 2013, 12 (2) : 755-769. doi: 10.3934/cpaa.2013.12.755

[11]

Stefano Bianchini, Elio Marconi. On the concentration of entropy for scalar conservation laws. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 73-88. doi: 10.3934/dcdss.2016.9.73

[12]

Christophe Prieur. Control of systems of conservation laws with boundary errors. Networks & Heterogeneous Media, 2009, 4 (2) : 393-407. doi: 10.3934/nhm.2009.4.393

[13]

Alberto Bressan, Marta Lewicka. A uniqueness condition for hyperbolic systems of conservation laws. Discrete & Continuous Dynamical Systems - A, 2000, 6 (3) : 673-682. doi: 10.3934/dcds.2000.6.673

[14]

Rinaldo M. Colombo, Kenneth H. Karlsen, Frédéric Lagoutière, Andrea Marson. Special issue on contemporary topics in conservation laws. Networks & Heterogeneous Media, 2016, 11 (2) : i-ii. doi: 10.3934/nhm.2016.11.2i

[15]

Laurent Lévi, Julien Jimenez. Coupling of scalar conservation laws in stratified porous media. Conference Publications, 2007, 2007 (Special) : 644-654. doi: 10.3934/proc.2007.2007.644

[16]

Boris Andreianov, Kenneth H. Karlsen, Nils H. Risebro. On vanishing viscosity approximation of conservation laws with discontinuous flux. Networks & Heterogeneous Media, 2010, 5 (3) : 617-633. doi: 10.3934/nhm.2010.5.617

[17]

Alexander Bobylev, Mirela Vinerean, Åsa Windfäll. Discrete velocity models of the Boltzmann equation and conservation laws. Kinetic & Related Models, 2010, 3 (1) : 35-58. doi: 10.3934/krm.2010.3.35

[18]

Gui-Qiang Chen, Monica Torres. On the structure of solutions of nonlinear hyperbolic systems of conservation laws. Communications on Pure & Applied Analysis, 2011, 10 (4) : 1011-1036. doi: 10.3934/cpaa.2011.10.1011

[19]

Dmitry V. Zenkov. Linear conservation laws of nonholonomic systems with symmetry. Conference Publications, 2003, 2003 (Special) : 967-976. doi: 10.3934/proc.2003.2003.967

[20]

Stefano Bianchini. A note on singular limits to hyperbolic systems of conservation laws. Communications on Pure & Applied Analysis, 2003, 2 (1) : 51-64. doi: 10.3934/cpaa.2003.2.51

2018 Impact Factor: 1.008

Metrics

  • PDF downloads (68)
  • HTML views (22)
  • Cited by (0)

Other articles
by authors

[Back to Top]