Skip to main content
Erschienen in: Queueing Systems 1-2/2017

22.11.2016

Heavy-traffic limits for an infinite-server fork–join queueing system with dependent and disruptive services

verfasst von: Hongyuan Lu, Guodong Pang

Erschienen in: Queueing Systems | Ausgabe 1-2/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Abdel-Hameed, M.: Lévy Processes and Their Applications in Reliability and Storage. Springer, Berlin (2014)CrossRef Abdel-Hameed, M.: Lévy Processes and Their Applications in Reliability and Storage. Springer, Berlin (2014)CrossRef
2.
Zurück zum Zitat Applebaum, D.: Lévy Processes and Stochastic Calculus. Cambridge University Press, Cambridge (2009)CrossRef Applebaum, D.: Lévy Processes and Stochastic Calculus. Cambridge University Press, Cambridge (2009)CrossRef
3.
Zurück zum Zitat 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) 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)
4.
Zurück zum Zitat Bickel, P.J., Wichura, M.J.: Convergence criteria for multiparameter stochastic processes and some applications. Ann. Math. Stat. 42, 1656–1670 (1971)CrossRef Bickel, P.J., Wichura, M.J.: Convergence criteria for multiparameter stochastic processes and some applications. Ann. Math. Stat. 42, 1656–1670 (1971)CrossRef
5.
Zurück zum Zitat Billingsley, P.: Convergence of Probability Measures. Wiley, New York (2009) Billingsley, P.: Convergence of Probability Measures. Wiley, New York (2009)
6.
8.
Zurück zum Zitat Chen, H., Whitt, W.: Diffusion approximations for open queueing networks with service interruptions. Queueing Syst. 13, 335–359 (1993)CrossRef Chen, H., Whitt, W.: Diffusion approximations for open queueing networks with service interruptions. Queueing Syst. 13, 335–359 (1993)CrossRef
9.
Zurück zum Zitat Dai, H.: Exact Monte Carlo simulation for fork–join networks. Adv. Appl. Prob. 43(2), 484–503 (2011)CrossRef Dai, H.: Exact Monte Carlo simulation for fork–join networks. Adv. Appl. Prob. 43(2), 484–503 (2011)CrossRef
10.
Zurück zum Zitat Davydov, Y.A.: Convergence of distributions generated by stationary stochastic process. Theory Prob. Appl. 13(4), 691–696 (1968)CrossRef Davydov, Y.A.: Convergence of distributions generated by stationary stochastic process. Theory Prob. Appl. 13(4), 691–696 (1968)CrossRef
11.
Zurück zum Zitat Durrett, R.: Probability: Theory and Examples. Cambridge University Press, Cambridge (2010)CrossRef Durrett, R.: Probability: Theory and Examples. Cambridge University Press, Cambridge (2010)CrossRef
12.
Zurück zum Zitat Ethier, S.N., Kurtz, T.G.: Markov Processes: Characterization and Convergence. Wiley, New York (2009) Ethier, S.N., Kurtz, T.G.: Markov Processes: Characterization and Convergence. Wiley, New York (2009)
13.
Zurück zum Zitat Gurvich, I., Ward, A.: On the dynamic control of matching queues. Stoch. Syst. 4(2), 479–523 (2014)CrossRef Gurvich, I., Ward, A.: On the dynamic control of matching queues. Stoch. Syst. 4(2), 479–523 (2014)CrossRef
14.
Zurück zum Zitat Ivanoff, B.G.: The function space D (\([0,\infty )^q\), E). Can. J. Stat. 8(2), 179–191 (1980)CrossRef Ivanoff, B.G.: The function space D (\([0,\infty )^q\), E). Can. J. Stat. 8(2), 179–191 (1980)CrossRef
15.
Zurück zum Zitat Jacod, J., Shiryaev, A.N.: Limit Theorems for Stochastic Processes. Springer, Berlin (1987)CrossRef Jacod, J., Shiryaev, A.N.: Limit Theorems for Stochastic Processes. Springer, Berlin (1987)CrossRef
16.
Zurück zum Zitat Jayawardene, A.K., Kella, O.: \(M/G/\infty \) with alternating renewal breakdowns. Queueing Syst. 22(1–2), 79–95 Jayawardene, A.K., Kella, O.: \(M/G/\infty \) with alternating renewal breakdowns. Queueing Syst. 22(1–2), 79–95
17.
Zurück zum Zitat Kella, O., Whitt, W.: Diffusion approximations for queues with server vacations. Adv. Appl. Prob. 22, 706–729 (1990)CrossRef Kella, O., Whitt, W.: Diffusion approximations for queues with server vacations. Adv. Appl. Prob. 22, 706–729 (1990)CrossRef
18.
Zurück zum Zitat Kella, O., Whitt, W.: Queues with server vacations and Lévy processes with secondary jump input. Ann. Appl. Prob. 1, 104–117 (1991)CrossRef Kella, O., Whitt, W.: Queues with server vacations and Lévy processes with secondary jump input. Ann. Appl. Prob. 1, 104–117 (1991)CrossRef
19.
Zurück zum Zitat Ko, S.S., Serfozo, R.F.: Response times in \(M/M/s\) fork–join networks. Adv. Appl. Prob. 36(3), 854–871 (2004) Ko, S.S., Serfozo, R.F.: Response times in \(M/M/s\) fork–join networks. Adv. Appl. Prob. 36(3), 854–871 (2004)
20.
Zurück zum Zitat Ko, S.S., Serfozo, R.F.: Sojourn times in \(G/M/1\) fork–join networks. Nav. Res. Logist. 55(5), 432–443 (2008)CrossRef Ko, S.S., Serfozo, R.F.: Sojourn times in \(G/M/1\) fork–join networks. Nav. Res. Logist. 55(5), 432–443 (2008)CrossRef
21.
Zurück zum Zitat Krichagina, E.V., Puhalskii, A.A.: A heavy-traffic analysis of a closed queueing system with a \(GI/\infty \) service center. Queueing Syst. 25(1–4), 235–280 (1997)CrossRef Krichagina, E.V., Puhalskii, A.A.: A heavy-traffic analysis of a closed queueing system with a \(GI/\infty \) service center. Queueing Syst. 25(1–4), 235–280 (1997)CrossRef
22.
Zurück zum Zitat Kyprianou, A.E.: Introductory Lectures on Fluctuations of Lévy Processes with Applications. Springer, Berlin (2006) Kyprianou, A.E.: Introductory Lectures on Fluctuations of Lévy Processes with Applications. Springer, Berlin (2006)
23.
Zurück zum Zitat Liptser, R.S., Shiryaev, A.N.: Theory of Martingales. Kluwer, Dordrecht (1989)CrossRef Liptser, R.S., Shiryaev, A.N.: Theory of Martingales. Kluwer, Dordrecht (1989)CrossRef
24.
Zurück zum Zitat 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)CrossRef 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)CrossRef
25.
Zurück zum Zitat Lu, H., Pang, G.: Heavy-traffic limits for a fork–join network in the Halfin–Whitt regime (2015) (under review) Lu, H., Pang, G.: Heavy-traffic limits for a fork–join network in the Halfin–Whitt regime (2015) (under review)
26.
Zurück zum Zitat Lu, H., Pang, G., Zhou, Y.: \(G/GI/N(+GI)\) queues with service interruptions in the Halfin–Whitt regime. Math. Methods Oper. Res. 83(1), 127–160 (2016)CrossRef Lu, H., Pang, G., Zhou, Y.: \(G/GI/N(+GI)\) queues with service interruptions in the Halfin–Whitt regime. Math. Methods Oper. Res. 83(1), 127–160 (2016)CrossRef
27.
Zurück zum Zitat Neuhaus, G.: On weak convergence of stochastic processes with multidimensional time parameter. Ann. Math. Stat. 42(4), 1285–1295 (1971)CrossRef Neuhaus, G.: On weak convergence of stochastic processes with multidimensional time parameter. Ann. Math. Stat. 42(4), 1285–1295 (1971)CrossRef
28.
Zurück zum Zitat Nguyen, V.: Processing networks with parallel and sequential tasks: heavy traffic analysis and Brownian limits. Ann. Appl. Prob. 3(1), 28–55 (1993)CrossRef Nguyen, V.: Processing networks with parallel and sequential tasks: heavy traffic analysis and Brownian limits. Ann. Appl. Prob. 3(1), 28–55 (1993)CrossRef
29.
Zurück zum Zitat Nguyen, V.: The trouble with diversity: fork–join networks with heterogeneous customer population. Ann. Appl. Prob. 4(1), 1–25 (1994)CrossRef Nguyen, V.: The trouble with diversity: fork–join networks with heterogeneous customer population. Ann. Appl. Prob. 4(1), 1–25 (1994)CrossRef
30.
Zurück zum Zitat Olvera-Cravioto, M., Ruiz-Lacedelli, O.: Parallel queues with synchronization (2015) (preprint) Olvera-Cravioto, M., Ruiz-Lacedelli, O.: Parallel queues with synchronization (2015) (preprint)
31.
Zurück zum Zitat Özkan, E., Ward, A.R.: On the control of fork–join networks (2015) (preprint) Özkan, E., Ward, A.R.: On the control of fork–join networks (2015) (preprint)
32.
Zurück zum Zitat Pang, G., Whitt, W.: Service interruptions in large-scale service systems. Manag. Sci. 55, 1499–1512 (2009a)CrossRef Pang, G., Whitt, W.: Service interruptions in large-scale service systems. Manag. Sci. 55, 1499–1512 (2009a)CrossRef
33.
Zurück zum Zitat Pang, G., Whitt, W.: Heavy-traffic limits for many-server queues with service interruptions. Queueing Syst. 61, 167–202 (2009b)CrossRef Pang, G., Whitt, W.: Heavy-traffic limits for many-server queues with service interruptions. Queueing Syst. 61, 167–202 (2009b)CrossRef
34.
Zurück zum Zitat Pang, G., Whitt, W.: Two-parameter heavy-traffic limits for infinite-server queues. Queueing Syst. 65(4), 325–364 (2010)CrossRef Pang, G., Whitt, W.: Two-parameter heavy-traffic limits for infinite-server queues. Queueing Syst. 65(4), 325–364 (2010)CrossRef
35.
Zurück zum Zitat Pang, G., Whitt, W.: Two-parameter heavy-traffic limits for infinite-server queues with dependent service times. Queueing Syst. 73, 119–146 (2013)CrossRef Pang, G., Whitt, W.: Two-parameter heavy-traffic limits for infinite-server queues with dependent service times. Queueing Syst. 73, 119–146 (2013)CrossRef
36.
Zurück zum Zitat Pang, G., Zhou, Y.: \(G/G/\infty \) queues with renewal alternating interruptions. Adv. Appl. Prob. (2016) Pang, G., Zhou, Y.: \(G/G/\infty \) queues with renewal alternating interruptions. Adv. Appl. Prob. (2016)
37.
Zurück zum Zitat Pang, G., Zhou, Y.: Two-parameter process limits for an infinite-server queue with arrival dependent services. Stoch. Process. Appl. (2016) Pang, G., Zhou, Y.: Two-parameter process limits for an infinite-server queue with arrival dependent services. Stoch. Process. Appl. (2016)
38.
Zurück zum Zitat Sklar, M.: Fonctions de répartition à n dimensions et leurs marges. Publ. Inst. Statist. Univ, Paris (1959) Sklar, M.: Fonctions de répartition à n dimensions et leurs marges. Publ. Inst. Statist. Univ, Paris (1959)
39.
Zurück zum Zitat 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) 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)
40.
Zurück zum Zitat Varma, S.: Heavy and light traffic approximations for queues with synchronization constraints. Ph.D. Thesis (1990) Varma, S.: Heavy and light traffic approximations for queues with synchronization constraints. Ph.D. Thesis (1990)
41.
Zurück zum Zitat Whitt, W.: Stochastic-Process Limits: An Introduction to Stochastic-Process Limits and Their Application to Queues. Springer, New York (2002) Whitt, W.: Stochastic-Process Limits: An Introduction to Stochastic-Process Limits and Their Application to Queues. Springer, New York (2002)
42.
Zurück zum Zitat 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) 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.
Zurück zum Zitat Zviran, A.: Fork–join networks in heavy traffic: diffusion approximations and control. M.Sc. Research Thesis. Technion, Haifa (2011) Zviran, A.: Fork–join networks in heavy traffic: diffusion approximations and control. M.Sc. Research Thesis. Technion, Haifa (2011)
Metadaten
Titel
Heavy-traffic limits for an infinite-server fork–join queueing system with dependent and disruptive services
verfasst von
Hongyuan Lu
Guodong Pang
Publikationsdatum
22.11.2016
Verlag
Springer US
Erschienen in
Queueing Systems / Ausgabe 1-2/2017
Print ISSN: 0257-0130
Elektronische ISSN: 1572-9443
DOI
https://doi.org/10.1007/s11134-016-9505-y

Weitere Artikel der Ausgabe 1-2/2017

Queueing Systems 1-2/2017 Zur Ausgabe

Premium Partner