Analysis of exponential reliable production lines using Kronecker descriptors

Abstract

This paper presents a solution procedure for reliable production lines with service times distributed according to an exponential distribution, based on a Markovian formulation with a Kronecker structured representation (sum of tensor products). Specifically, structured Markovian formalisms are used to reduce the impact of the well-known state explosion problem associated with other methods of solution. Such formalisms combined with the Kronecker representation deliver memory efficiency in storing very large models, i.e. models with more than states. The exact steady-state solutions of these models may be obtained using efficient existing software packages. The proposed solution procedure is illustrated with two detailed examples, and generalised with a model construction algorithm. The computed throughput for several examples of production lines with perfectly reliable machines, as well as the computational costs in terms of CPU time to solve them with PEPS2007 and GTAexpress software packages, are also presented. In effect the paper demonstrates the power of the use of the Kronecker descriptor analysis applied to the derivation of the exact solution of the particular class of production lines considered. The Kronecker descriptor methodology is well-known to analysts concerned with computer and communication systems.

Keywords:

• Markov modelling
• stochastic models
• throughput
• queueing networks
• production modelling
• performance analysis
• manufacturing systems engineering
• stochastic automata networks
• tensor (Kronecker) algebra

Acknowledgements

The order of authors is merely alphabetical. Paulo Fernandes is funded by CNPq Brazil (PQ 307284/2010-7). Afonso Sales receives grants from CAPES Brazil (PNPD 02388/09-0). Chrissoleon Papadopoulos for this research was co-financed by the European Union (European Social Fund -– ESF) and Greek national funds through the Operational Program ‘Education and Lifelong Learning’ of the National Strategic Reference Framework (NSRF) – Research Funding Program: THALES. Investing in knowledge society through the European Social Fund.

Notes

1. We consider two matrices stochastic equivalent when they represent the same stochastic process, i.e. they deliver the same steady state and transient solution.

2. The term ‘complexity’ is employed here in the computational sense, i.e. the amount of computational resources to achieve the solution Cook 1983. Specifically, we are interested in the processing resources, and, therefore, a value which is proportional to the time to obtain the solution. Usually, the time to achieve the solution is estimated as the number of floating point operations needed to compute the solution, and the complexity itself is expressed as a relation (e.g., linear, exponential) with a proportional value and the number of floating point multiplications.