Taylor series expansions for Poisson-driven (max,+)-linear systems. (English) Zbl 0863.60092

Summary: We give a Taylor series expansion for the mean value of the canonical stationary state variables of open \((\max,+)\)-linear stochastic systems with Poisson input process. Probabilistic expressions are derived for coefficients of all orders, under certain integrability conditions. The coefficients in the series expansion are the expectations of polynomials, known in explicit form, of certain random variables defined from the data of the \((\max,+)\)-linear system. These polynomials are of independent combinatorial interest: their monomials belong to a subset of those obtained in the multinomial expansion; they are also invariant under cyclic permutation and under translations along the main diagonal. The method for proving these results is based on two ingredients: (1) the \((\max,+)\)-linear representation of the stationary state variables as functionals of the input point process; (2) the series expansion representation of functionals of marked point processes and, in particular, of Poisson point processes.
Several applications of these results are proposed in queueing theory and within the framework of stochastic Petri nets. It is well known that \((\max,+)\)-linear systems allow one to represent stochastic Petri nets belonging to the class of event graphs. This class contains various instances of queueing networks like acyclic or cyclic fork-join queueing networks, finite or infinite capacity tandem queueing networks with various types of blocking (manufacturing and communication), synchronized queueing networks and so on. It also contains some basic manufacturing models such as Kanban networks, job-shop systems and so forth. The applicability of this expansion method is discussed for several systems of this type. In the \(M/D\) case (i.e., all service times are deterministic), the approach is quite practical, as all coefficients of the expansion are obtained in closed form. In the \(M/GI\) case, the computation of the coefficient of order \(k\) can be seen as that of joint distributions in a stochastic PERT graph of an order which is linear in \(k\).


60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
60G55 Point processes (e.g., Poisson, Cox, Hawkes processes)
Full Text: DOI


[1] Asmussen, S. (1987). Applied Probability and Queues. Wiley, Chichester. · Zbl 0624.60098
[2] Baccelli, F. (1992). Ergodic theory of stochastic Petri networks. Ann. Probab. 20 375-396. · Zbl 0742.60091
[3] Baccelli, F. and Brémaud, P. (1993). Virtual customers in sensitivity and light traffic analysis via Campbell’s formula for point processes. Adv. in Appl. Probab. 25 221-224. JSTOR: · Zbl 0787.60057
[4] Baccelli, F. and Brémaud, P. (1994). Elements of Queueing Theory. Springer, Berlin. · Zbl 0801.60081
[5] Baccelli, F., Borovkov, A. A. and Mairesse, J. (1995). On large tandem queueing networks. INRIA Report. · Zbl 0976.60088
[6] Baccelli, F., Cohen, G., Olsder, G. J. and Quadrat, J. P. (1992). Sy nchronization and Linearity. Wiley, Chichester. · Zbl 0824.93003
[7] Bavnick, H., Hooghiemstra, G. and de Waard, E. (1993). An application of Gegenbauer poly nomials in queueing theory. J. Comput. Appl. Math. 49 1-10. · Zbl 0789.60075
[8] Blanc, J. P. C. (1992). The power-series algorithm applied to the shortest-queue model. Oper. Res. 40 157-167. JSTOR: · Zbl 0743.60092
[9] Blanc, J. P. C. and van den Hout, W. (1995). Development and justification of the powerseries algorithm for BMAP-sy stems. Stochastic Models 11 471-496. · Zbl 0829.60092
[10] Blaszczy szy n, B. (1995). Factorial moment expansion for stochastic sy stems. Stochastic Process. Appl. 56 321-335. · Zbl 0816.60042
[11] Blaszczy szy n, B., Frey, A. and Schmidt, V. (1995). Light-traffic approximations for Markov-modulated multi-server queues. Stochastic Models 11 423-445. · Zbl 0829.60090
[12] Blaszczy szy n, B. and Rolski, T. (1993). Queues in series in light traffic. Ann. Appl. Probab. 3 881-896. · Zbl 0781.60081
[13] Blaszczy szy n, B. and Rolski, T. (1995). Expansions for Markov-modulated sy stems and approximations of ruin probability. J. Appl. Probab. 32.
[14] Blaszczy szy n, B., Rolski, T. and Schmidt, V. (1995). Light-traffic approximation in queues and related stochastic models. In Advances in Queueing: Theory, Methods and Open Problems (J. H. Dshalalow, ed.) 379-406. CRC Press, Boca Raton, FL. · Zbl 0865.60088
[15] Boxma, O. J. (1979). On a tandem queueing model with identical service times at both counters. Adv. in Appl. Probab. 11 616-659. JSTOR: · Zbl 0406.60081
[16] Boxma, O. J. and Daduna, H. (1990). Sojourn times in queueing networks. In Stochastic Analy sis of Computer and Communication Sy stems (H. Takagi, ed.) 401-450. NorthHolland, Amsterdam.
[17] Cheng, D. and Yao, D. (1993). Tandem queues with general blocking: a unified model and comparison results. DEDS: Theory and Applications 2 207-234. · Zbl 0767.60091
[18] Cohen, G., Dubois, D., Quadrat, J. P. and Viot, M. (1983). A linear sy stem-theoretic view of discrete event processes. In Proceedings of the 22nd Conference on Decision and Control. IEEE, New York.
[19] Cohen, G., Dubois, D., Quadrat, J. P. and Viot, M. (1985). A linear sy stem-theoretic view of discrete event processes and its use for performance evaluation in manufacturing. IEEE Trans. Automat. Control AC-30 210-220. · Zbl 0557.93005
[20] Franken, P., K önig, D., Arndt, U. and Schmidt, V. (1982). Queues and Point Processes. Wiley, Chichester. · Zbl 0505.60058
[21] Frey, A. and Schmidt, V. (1995). Tay lor-series expansion for multivariate characteristics of risk processes. Insurance Math. Econom.
[22] Friedman, H. D. (1965). Reduction methods for tandem queueing sy stems. Oper. Res. 13 121-131. JSTOR: · Zbl 0143.40702
[23] Gong, W. B. and Hu, J. Q. (1992). The MacLaurin series for the GI/G/1 queue. J. Appl. Probab. 29 176-184. JSTOR: · Zbl 0765.60097
[24] Hooghiemstra, G., Keane, M. and van de Ree, S. (1988). Power series for stationary distributions of coupled processor models. SIAM J. Appl. Math. 48 1159-1166. JSTOR: · Zbl 0652.60097
[25] Hu, J. Q. (1994). Analy ticity of single-server queues in light traffic. Queueing Sy stems 19 63-80. · Zbl 0820.60075
[26] Hu, J. Q. (1995). The departure process of the GI/GI/1 queue and its MacLaurin series. Oper. Res.
[27] Hu, J. Q., Nananuku, S. and Gong, W. B. (1994). The departure process of the GI/GI/1 queue and its MacLaurin series. J. Appl. Probab. 30 898-912.
[28] Kleinrock, L. (1975). Queueing Sy stems 1. Wiley, New York. · Zbl 0334.60045
[29] K önig, D. and Schmidt, V. (1992). Random Point Processes. Teubner, Stuttgart. (In German.) · Zbl 0778.60037
[30] Kroese, D. P. and Schmidt, V. (1995). Light-traffic analysis for queues with spatially distributed arrivals. Math. Oper. Res. To appear. JSTOR: · Zbl 0848.60087
[31] Le Gall, P. (1994). The overall sojourn time in tandem queues with identical successive service times and renewal input. Stochastic Process. Appl. 52 165-178. · Zbl 0813.60088
[32] Li, H. and Zhu, Y. (1994). A new approach to the G/G/1 queue with generalized setup time and exhaustive server. J. Appl. Probab. 30 1083-1097. JSTOR: · Zbl 0820.60074
[33] Olsder, G. J., Resing, J. A. C., de Vries, R. E., Keane, M. S. and Hooghiemstra, G. · Zbl 1005.91023
[34] . Discrete event sy stems with stochastic processing times. IEEE Trans. Automat. Control AC-35 299-302. · Zbl 0707.93068
[35] Reiman, M. I. and Simon, B. (1989). Open queueing sy stems in light traffic. Math. Oper. Res. 14 26-59. JSTOR: · Zbl 0665.60105
[36] Simon, B. (1993). Calculating light traffic limits for sojourn times in open Markovian queueing sy stems. Stochastic Models 9 213-231. · Zbl 0771.60084
[37] Thorisson, H. (1985). The queue GI/G/1: finite moments of the cy cle variables and uniform rates of convergence. Stochastic Process. Appl. 19 85-99. · Zbl 0554.60088
[38] Zazanis, M. A. (1992). Analy ticity of Poisson-driven stochastic sy stems. Adv. in Appl. Probab. 24 532-541. JSTOR: · Zbl 0757.60045
[39] Zhu, Y. and Li, H. (1993). The MacLaurin expansion for a GI/GI/1 queue with Markov modulated arrival and services. Queueing Sy stems 14 125-134. · Zbl 0780.60098
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.