×

Heavy-traffic limits for an infinite-server fork-join queueing system with dependent and disruptive services. (English) Zbl 1367.60116

Summary: We study an infinite-server fork-join queueing system with dependent services, which experiences alternating renewal service disruptions. Jobs are forked into a fixed number of parallel tasks upon arrival and processed at the corresponding parallel service stations with multiple servers. Synchronization of a job occurs when its parallel tasks are completed, i.e., non-exchangeable. Service times of the parallel tasks of each job can be correlated, having a general continuous joint distribution function, and moreover, the service vectors of consecutive jobs form a stationary dependent sequence satisfying the strong mixing (\(\alpha \)-mixing) condition. The system experiences renewal alternating service disruptions with up and down periods. In each up period, the system operates normally, but in each down period, jobs continue to enter the system, while all the servers will stop working, and services received will be conserved and resume at the beginning of the next up period. We study the impact of both the dependence among service times and these down times upon the service dynamics, the unsynchronized queueing dynamics, and the synchronized process, assuming that the down times are asymptotically negligible. We prove FWLLN and FCLT for these processes, where the limit processes in the FCLT possess a stochastic decomposition property and the convergence requires the Skorohod \(M_1\) topology.

MSC:

60K25 Queueing theory (aspects of probability theory)
60F17 Functional limit theorems; invariance principles
60F05 Central limit and other weak theorems
90B22 Queues and service in operations research
60J75 Jump processes (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdel-Hameed, M.: Lévy Processes and Their Applications in Reliability and Storage. Springer, Berlin (2014) · Zbl 1283.60005
[2] Applebaum, D.: Lévy Processes and Stochastic Calculus. Cambridge University Press, Cambridge (2009) · Zbl 1200.60001
[3] Atar, R., Mandelbaum, A., Zviran, A.: Control of fork-join networks in heavy traffic. In: 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), IEEE (2012) · Zbl 0892.60090
[4] Bickel, P.J., Wichura, M.J.: Convergence criteria for multiparameter stochastic processes and some applications. Ann. Math. Stat. 42, 1656-1670 (1971) · Zbl 0265.60011
[5] Billingsley, P.: Convergence of Probability Measures. Wiley, New York (2009) · Zbl 0172.21201
[6] Brémaud, P.: Point Processes and Queues. Springer, New York (1981) · Zbl 0478.60004
[7] Bücher, A.: A note on weak convergence of the sequential multivariate empirical process under strong mixing. J. Theor. Prob. 28(3), 1028-1037 (2015). doi:10.1007/s10959-013-0529-5 · Zbl 1330.60057
[8] Chen, H., Whitt, W.: Diffusion approximations for open queueing networks with service interruptions. Queueing Syst. 13, 335-359 (1993) · Zbl 0783.60088
[9] Dai, H.: Exact Monte Carlo simulation for fork-join networks. Adv. Appl. Prob. 43(2), 484-503 (2011) · Zbl 1220.65010
[10] Davydov, Y.A.: Convergence of distributions generated by stationary stochastic process. Theory Prob. Appl. 13(4), 691-696 (1968) · Zbl 0181.44101
[11] Durrett, R.: Probability: Theory and Examples. Cambridge University Press, Cambridge (2010) · Zbl 1202.60001
[12] Ethier, S.N., Kurtz, T.G.: Markov Processes: Characterization and Convergence. Wiley, New York (2009) · Zbl 1089.60005
[13] Gurvich, I., Ward, A.: On the dynamic control of matching queues. Stoch. Syst. 4(2), 479-523 (2014) · Zbl 1327.60177
[14] Ivanoff, B.G.: The function space D \[([0,\infty )^q\][0,∞)q, E). Can. J. Stat. 8(2), 179-191 (1980) · Zbl 0467.60009
[15] Jacod, J., Shiryaev, A.N.: Limit Theorems for Stochastic Processes. Springer, Berlin (1987) · Zbl 0635.60021
[16] Jayawardene, A.K., Kella, \[O.: M/G/\infty\] M/G/∞ with alternating renewal breakdowns. Queueing Syst.22(1-2), 79-95 · Zbl 0853.60072
[17] Kella, O., Whitt, W.: Diffusion approximations for queues with server vacations. Adv. Appl. Prob. 22, 706-729 (1990) · Zbl 0713.60101
[18] Kella, O., Whitt, W.: Queues with server vacations and Lévy processes with secondary jump input. Ann. Appl. Prob. 1, 104-117 (1991) · Zbl 0725.60079
[19] Ko, S.S., Serfozo, R.F.: Response times in \[M/M/s\] M/M/s fork-join networks. Adv. Appl. Prob. 36(3), 854-871 (2004) · Zbl 1064.60181
[20] Ko, S.S., Serfozo, R.F.: Sojourn times in \[G/M/1\] G/M/1 fork-join networks. Nav. Res. Logist. 55(5), 432-443 (2008) · Zbl 1209.90114
[21] Krichagina, E.V., Puhalskii, A.A.: A heavy-traffic analysis of a closed queueing system with a \[GI/\infty\] GI/∞ service center. Queueing Syst. 25(1-4), 235-280 (1997) · Zbl 0892.60090
[22] Kyprianou, A.E.: Introductory Lectures on Fluctuations of Lévy Processes with Applications. Springer, Berlin (2006) · Zbl 1104.60001
[23] Liptser, R.S., Shiryaev, A.N.: Theory of Martingales. Kluwer, Dordrecht (1989)
[24] Lu, H., Pang, G.: Gaussian limits of a fork-join network with non-exchangeable synchronization in heavy-traffic. Math. Oper. Res. 41(2), 560-595 (2016) · Zbl 1342.60157
[25] Lu, H., Pang, G.: Heavy-traffic limits for a fork-join network in the Halfin-Whitt regime (2015) (under review) · Zbl 1359.60045
[26] Lu, H., Pang, G., Zhou, \[Y.: G/GI/N(+GI)\] G/GI/N(+GI) queues with service interruptions in the Halfin-Whitt regime. Math. Methods Oper. Res. 83(1), 127-160 (2016) · Zbl 1344.60088
[27] Neuhaus, G.: On weak convergence of stochastic processes with multidimensional time parameter. Ann. Math. Stat. 42(4), 1285-1295 (1971) · Zbl 0222.60013
[28] Nguyen, V.: Processing networks with parallel and sequential tasks: heavy traffic analysis and Brownian limits. Ann. Appl. Prob. 3(1), 28-55 (1993) · Zbl 0771.60082
[29] Nguyen, V.: The trouble with diversity: fork-join networks with heterogeneous customer population. Ann. Appl. Prob. 4(1), 1-25 (1994) · Zbl 0797.60078
[30] Olvera-Cravioto, M., Ruiz-Lacedelli, O.: Parallel queues with synchronization (2015) (preprint) · Zbl 1481.60196
[31] Özkan, E., Ward, A.R.: On the control of fork-join networks (2015) (preprint) · Zbl 1434.60265
[32] Pang, G., Whitt, W.: Service interruptions in large-scale service systems. Manag. Sci. 55, 1499-1512 (2009a) · Zbl 1232.90132
[33] Pang, G., Whitt, W.: Heavy-traffic limits for many-server queues with service interruptions. Queueing Syst. 61, 167-202 (2009b) · Zbl 1166.60336
[34] Pang, G., Whitt, W.: Two-parameter heavy-traffic limits for infinite-server queues. Queueing Syst. 65(4), 325-364 (2010) · Zbl 1231.60100
[35] Pang, G., Whitt, W.: Two-parameter heavy-traffic limits for infinite-server queues with dependent service times. Queueing Syst. 73, 119-146 (2013) · Zbl 1264.60068
[36] Pang, G., Zhou, \[Y.: G/G/\infty\] G/G/∞ queues with renewal alternating interruptions. Adv. Appl. Prob. (2016) · Zbl 1351.60123
[37] Pang, G., Zhou, Y.: Two-parameter process limits for an infinite-server queue with arrival dependent services. Stoch. Process. Appl. (2016) · Zbl 1231.60100
[38] Sklar, M.: Fonctions de répartition à n dimensions et leurs marges. Publ. Inst. Statist. Univ, Paris (1959) · Zbl 0100.14202
[39] Straf, M.L.: Weak convergence of stochastic processes with several parameters. In: Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, vol. 2, pp. 187-221 (1972) · Zbl 0255.60019
[40] Varma, S.: Heavy and light traffic approximations for queues with synchronization constraints. Ph.D. Thesis (1990) · Zbl 0771.60082
[41] Whitt, W.: Stochastic-Process Limits: An Introduction to Stochastic-Process Limits and Their Application to Queues. Springer, New York (2002) · Zbl 0993.60001
[42] Zaied, I.: The offered load in fork-join networks: calculations and applications to service engineering of emergency department. M.Sc. Research Thesis. Technion, Haifa (2012)
[43] Zviran, A.: Fork-join networks in heavy traffic: diffusion approximations and control. M.Sc. Research Thesis. Technion, Haifa (2011) · Zbl 0265.60011
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.