Heavy-Traffic Limits for a Fork-Join Network in the Halfin-Whitt Regime

References

• R. J. Adler and J. E. Taylor. (2007) Random Fields and Geometry. Springer. MR2319516Google Scholar
• M. Armony, S. Israelit, A. Mandelbaum, Y. N. Marmor, Y. Tseytlin and G. B. Yom-Tov. (2015) Patient flow in hospitals: a data-based queueing-science perspective. Stochastic Systems. Vol. 5, No. 1, 146–194. MR3442392Link, Google Scholar
• R. Atar, A. Mandelbaum and A. Zviran. (2012) Control of fork-join networks in heavy traffic. Communication, Control, and Computing (Allerton), 50th Annual Allerton Conference on. IEEE.Google Scholar
• F. Baccelli, M. Lelarge and S. Foss. (2004) Asymptotics of subexponential max plus networks: the stochastic event graph case. Queueing Systems. Vol. 46, No. 1–2, 75–96. MR2072276Google Scholar
• F. Baccelli, A. M. Makowski and A. Shwartz. (1989) The fork-join queue and related systems with synchronization constraints: stochastic ordering and computable bounds. Advances in Applied Probability. Vol. 21, No. 3, 629–660. MR1013655Google Scholar
• F. Baccelli, W. A. Massey and D. Towsley. (1989) Acyclic fork-join queueing networks. Journal of the ACM (JACM). Vol. 36, No. 3, 615–642. MR1072240Google Scholar
• P. Billingsley. (2009) Convergence of Probability Measures. John Wiley & Sons.Google Scholar
• J. Blanchet, Y. Pei and K. Sigman. (2015) Exact sampling of some multi-dimensional queueing models with renewal input. Working paper. https://arxiv.org/abs/1512.07284Google Scholar
• P. Brémaud. (1981) Point Processes and Queues. Springer, New York.Google Scholar
• H. Dai. (2011) Exact Monte Carlo simulation for fork-join networks. Advances in Applied Probability. Vol. 43, No. 2, 484–503.Google Scholar
• J. Dean and S. Ghemawat. (2008) MapReduce: Simplified data processing on large clusters. Communications of the ACM. Vol. 51, No. 1, 107–113.Google Scholar
• A. B. Dieker and M. Lelarge. (2006) Tails for (max, plus) recursions under subexponentiality. Queueing Systems. Vol. 53, No. 4, 213–230.Google Scholar
• R. Durrett. (2010) Probability: Theory and Examples. Cambridge University Press. MR2722836Google Scholar
• S. N. Ethier and T. G. Kurtz. (2009) Markov Processes: Characterization and Convergence. John Wiley & Sons.Google Scholar
• L. Flatto and S. Hahn. (1984) Two Parallel Queues Created by Arrivals with Two Demands I. SIAM Journal on Applied Mathematics. Vol. 44, No. 5, 1041–1053. MR0759714Google Scholar
• L. Flatto. (1985) Two Parallel Queues Created by Arrivals with Two Demands II. SIAM Journal on Applied Mathematics. Vol. 45, No. 5, 861–878.Google Scholar
• J. Gallien and L. M. Wein. (2001) A simple and effective component procurement policy for stochastic assembly systems. Queueing Systems. Vol. 38, No. 2, 221–248.Google Scholar
• S. Halfin and W. Whitt. (1981) Heavy-traffic limits for queues with many exponential servers. Operations Research. Vol. 29, No. 3, 567–588. MR0629195Link, Google Scholar
• B. G. Ivanoff. (1980) The function space D([0, ∞)q, E). Canadian Journal of Statistics. Vol. 8, No. 2, 179–191.Google Scholar
• J. Jacod and A. N. Shiryaev. (1987) Limit Theorems for Stochastic Processes. Springer-Verlag, Berlin.Google Scholar
• A. Jean-Marie and L. Gün. (1993) Parallel queues with resequencing. Journal of the ACM (JACM). Vol. 40, No. 5, 1188–1208.Google Scholar
• L. Jiang and R. E. Giachetti. (2008) A queueing network model to analyze the impact of parallelization of care on patient cycle time. Health Care Management Science. Vol. 11, 248–261.Google Scholar
• I. Karatzas and S. E. Shreve. (1991) Brownian Motion and Stochastic Calculus. Springer. MR1121940Google Scholar
• H. Kaspi and K. Ramanan. (2011) Law of large numbers limits for many-server queues. Annals of Applied Probability. Vol. 21, No. 1, 33–114.Google Scholar
• H. Kaspi and K. Ramanan. (2013) SPDE limits of many-server queues. Annals of Applied Probability. Vol. 23, No. 1, 145–229.Google Scholar
• L. J. Klementowski. (1978) PERT/CPM and supplementary analytical techniques: an analysis of aerospace usage. Ph.D. Thesis. Faculty of the School of Engineering of the Air Force Institute of Technology, Air University.Google Scholar
• S. S. Ko and R. F. Serfozo. (2004) Response times in M/M/s fork-join networks. Advances in Applied Probability. Vol. 36, No. 3, 854–871.Google Scholar
• S. S. Ko and R. F. Serfozo. (2008) Sojourn times in G/M/1 fork-join networks. Naval Research Logistics. Vol. 55, No. 5, 432–443.Google Scholar
• E. V. Krichagina and A. A. Puhalskii. (1997) A heavy-traffic analysis of a closed queueing system with a GI/∞ service center. Queueing Systems. Vol. 25, No. 1-4, 235–280.Google Scholar
• R. C. Larson, M. F. Cahn and M. C. Shell. (1993) Improving the New York City arrest-to-arraignment system. Interfaces. Vol. 23, No. 1, 76–96.Link, Google Scholar
• M. Lin, L. Zhang, A. Wierman and J. Tan. (2013) Joint optimization of overlapping phases in MapReduce. Proceedings of IFIP Performance. Vol. 70, No. 10, 720–735.Google Scholar
• R. S. Liptser and A. N. Shiryaev. (1989) Theory of Martingales. Kluwer, Dordrecht.Google Scholar
• H. Lu and G. Pang. (2015) Gaussian limits of a fork-join network with non-exchangeable synchronization in heavy-traffic. Mathematics of Operations Research. Vol. 41, No. 2, 560–595.Google Scholar
• H. Lu, G. Pang and M. Mandjes. (2016) A functional central limit theorem for Markov additive arrival processes and its applications to queueing systems. Queueing Systems. Vol. 84, No. 3, 381–406.Google Scholar
• H. Lu and G. Pang. (2017) Heavy-traffic limits for an infinite-server fork-join queueing system with dependent and disruptive services. Queueing Systems. Vol. 85, No. 1–2, 67–115.Google Scholar
• M. Mandelker. (1982) Continuity of monotone functions. Pacific Journal of Mathematics. Vol. 99, No. 2, 413–418.Google Scholar
• A. W. Marshall and I. Olkin. (1967) A multivariate exponential distribution. Journal of the American Statistical Association. Vol. 62, No. 317, 30–44.Google Scholar
• A. Mandelbaum and P. Momčilović (2012) Queues with many servers and impatient customers. Mathematics of Operations Research. Vol. 37, No. 1, 41–65. MR2891146Link, Google Scholar
• G. Neuhaus. (1971) On weak convergence of stochastic processes with multidimensional time parameter. Annals of Mathematical Statistics. Vol. 42, No. 4, 1285–1295.Google Scholar
• V. Nguyen. (1993) Processing networks with parallel and sequential tasks: heavy traffic analysis and Brownian Limits. Annals of Applied Probability. Vol. 3, No. 1, 28–55.Google Scholar
• V. Nguyen. (1994) The trouble with diversity: fork-join networks with heterogeneous customer population. Annals of Applied Probability. Vol. 4, No. 1, 1–25.Google Scholar
• G. Pang, R. Talreja and W. Whitt. (2007) Martingale proofs of many-server heavy-traffic limits for Markovian queues. Probability Surveys. 4, 193–267.Google Scholar
• G. Pang and W. Whitt. (2010) Two-parameter heavy-traffic limits for infinite-server queues. Queueing Systems. Vol. 65, No. 4, 325–364.Google Scholar
• G. Pang and W. Whitt. (2012) Infinite-server queues with batch arrivals and dependent service times. Probability in Engineering and Informational Sciences. Vol. 26, No. 2, 197–220.Google Scholar
• G. Pang and W. Whitt. (2013) Two-parameter heavy-traffic limits for infinite-server queues with dependent service times. Queueing Systems. Vol. 73, No. 2, 119–146.Google Scholar
• G. Pang and Y. Zhou. (2016) Two-parameter process limits for an infinite-server queue with arrival dependent service times. Forthcoming in Stochastic Processes and their Applications. http://dx.doi.org/10.1016/j.spa.2016.08.003Google Scholar
• G. Pang and Y. Zhou. (2017) Two-parameter process limits for infinite-server queues with dependent service times via chaining bounds. Under review.Google Scholar
• D. Pinotsi and M. A. Zazanis. (2005) Synchronized queues with deterministic arrivals. Operations Research Letters. Vol. 33, No. 6, 560–566.Google Scholar
• B. Prabhakar, N. Bambos and T. S. Mountford. (2000) The synchronization of Poisson processes and queueing networks with service and synchronization nodes. Advances in Applied Probability. Vol. 32, No. 3, 824–843.Google Scholar
• A. A. Puhalskii and J. E. Reed. (2010) On many-server queues in heavy traffic. Annals of Applied probability. Vol. 20, No. 1, 129–195.Google Scholar
• J. E. Reed. (2009) The G/GI/N queue in the Halfin-Whitt regime. Annals of Applied Probability. Vol. 19, No. 6, 2211–2269.Google Scholar
• M. Sklar. (1959) Fonctions de répartition à n dimensions et leurs marges. Publ. Inst. Statist. Univ. Paris 8.Google Scholar
• M. Takahashi, H. Ōsawa and T. Fujisawa. (2000) On a synchronization queue with two finite buffers. Queueing Systems. Vol. 36, No. 1-3, 107–123.Google Scholar
• J. Tan, X. Meng and L. Zhang. (2012) Delay tails in MapReduce scheduling. ACM SIGMETRICS Performance Evaluation Review. Vol. 40, No. 1, 5–16.Google Scholar
• A. W. van der Vaart and J. A. Wellner. (1996) Weak Convergence and Empirical Processes. Springer.Google Scholar
• S. Varma. (1990) Heavy and light traffic approximations for queues with synchronization constraints. Ph.D. Thesis.Google Scholar
• W. Wang, K. Zhu, L. Ying, J. Tan and L. Zhang. (2013) Map task scheduling in MapReduce with data locality: throughput and heavy-traffic optimality. Proceedings of IEEE INFOCOM. 1609–1617.Google Scholar
• W. Whitt. (2002) Stochastic-Process Limits: An Introduction to Stochastic-Process Limits and Their Application to Queues. Springer.Google Scholar
• C. J. Willits and D. C. Dietz. (2001) Nested fork-join queueing network model for analysis of airfield operations. Journal of Aircraft. Vol. 38, No. 5, 848–855.Google Scholar
• I. Zaied. (2012) The offered load in fork-join networks: calculations and applications to service engineering of emergency department. M.Sc. Research Thesis. Technion.Google Scholar
• A. Zviran. (2011) Fork-join networks in heavy traffic: diffusion approximations and control. M.Sc. Research Thesis. Technion.Google Scholar