Gaussian Limits for a Fork-Join Network with Nonexchangeable Synchronization in Heavy Traffic

References

• Antkiewicz R, Gasecki A, Najgebauer A, Pierzchała D, Tarapata Z (2010) Stochastic PERT and CAST logic approach for computer support of complex operation planning. Analytical and Stochastic Modeling Techniques and Applications, Vol. 6158 (Springer, Berlin), 159–173.Crossref, Google Scholar
• Aras AK, Liu Y, Whitt W (2014) Heavy-traffic limit for the initial content process, submitted.Google Scholar
• Armony M, Israelit S, Mandelbaum A, Marmor YN, Tseytlin Y, Yom-Tov GB (2015) On patient flow in hospitals: A data-based queueing-science perspective. Stochastic Systems 5:1–49.Crossref, Google Scholar
• Atar R, Mandelbaum A, Zviran A (2012) Control of fork-join networks in heavy traffic. 2012 50th Ann. Allerton Conf. Comm., Control, Comput. (IEEE, Piscataway, NJ), 823–830.Crossref, Google Scholar
• Avi-Itzhak B, Halfin S (1991) Non-preemptive priorities in simple fork-join queues. Cohen JW, Pack CD, eds. Queueing, Performance and Control in ATM (ITC-13) (Elsevier Science, Amsterdam), 231–238.Google Scholar
• Baccelli F, Lelarge M, Foss S (2004) Asymptotics of subexponential max plus networks: The stochastic event graph case. Queueing Systems 46(1–2):75–96.Crossref, Google Scholar
• Baccelli F, Makowski AM, Shwartz A (1989a) The fork-join queue and related systems with synchronization constraints: Stochastic ordering and computable bounds. Ad. Appl. Probab. 21(3):629–660.Crossref, Google Scholar
• Baccelli F, Massey WA, Towsley D (1989b) Acyclic fork-join queuing networks. J. ACM 36(3):615–642.Crossref, Google Scholar
• Bickel PJ, Wichura MJ (1971) Convergence criteria for multiparameter stochastic processes and some applications. Ann. Math. Statist. 42(5):1656–1670.Crossref, Google Scholar
• Billingsley P (2009) Convergence of Probability Measures (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Bouzebda S, Zari T (2013) Strong approximation of empirical copula processes by Gaussian processes. Statistics 47(5):1047–1063.Crossref, Google Scholar
• Brémaud P (1981) Point Processes and Queues: Martingale Dynamics (Springer, New York).Crossref, Google Scholar
• Csörgő M, Horváth L (1988) A note on strong approximations of multivariate empirical processes. Stochastic Processes Appl. 28(1):101–109.Crossref, Google Scholar
• Csörgő M, Révész P (1975) A strong approximation of the multivariate empirical process. Studia Sci. Math. Hungar 10:427–434.Google Scholar
• Dai H (2011) Exact Monte Carlo simulation for fork-join networks. Ad. Appl. Probab. 43(2):484–503.Crossref, Google Scholar
• Dean J, Ghemawat S (2008) MapReduce: Simplified data processing on large clusters. Comm. ACM 51(1):107–113.Crossref, Google Scholar
• Dedecker J, Merlevède F, Rio E (2014) Strong approximation of the empirical distribution function for absolutely regular sequences in ℝd. Electron. J. Probab. 19(9):1–56.Google Scholar
• Dieker AB, Lelarge M (2006) Tails for (max, plus) recursions under subexponentiality. Queueing Systems 53(4):213–230.Crossref, Google Scholar
• Doukhan P, Fermanian JD, Lang G (2009) An empirical central limit theorem with applications to copulas under weak dependence. Statist. Inference for Stochastic Processes 12(1):65–87.Crossref, Google Scholar
• Durieu O, Tusche M (2014) An empirical process central limit theorem for multidimensional dependent data. J. Theoret. Probab. 27(1):249–277.Crossref, Google Scholar
• Durrett R (2010) Probability: Theory and Examples (Cambridge University Press, New York).Crossref, Google Scholar
• Eick SG, Massey WA, Whitt W (1993) The physics of the Mt/G/∞ queue. Oper. Res. 41(4):731–742.Link, Google Scholar
• Ethier SN, Kurtz TG (2009) Markov Processes: Characterization and Convergence (John Wiley & Sons, New York).Google Scholar
• Gallien J, Wein LM (2001) A simple and effective component procurement policy for stochastic assembly systems. Queueing Systems 38(2):221–248.Crossref, Google Scholar
• Gurvich I, Ward A (2014) On the dynamic control of matching queues. Stochastic Systems 4:1–45.Crossref, Google Scholar
• Huang J, Mandelbaum A, Zhang H, Zhang J (2014) Refined models for efficiency-driven queues with applications to delay announcements and staffing. Working paper, The Chinese University of Hong Kong, Hong Kong.Google Scholar
• Ivanoff BG (1980) The function space D([0, ∞)q, E). Canadian J. Statist. 8(2):179–191.Crossref, Google Scholar
• Ivanoff BG, Merzbach E (1999) Set-Indexed Martingales (CRC Press, Boca Raton, FL).Google Scholar
• Jacod J, Shiryaev AN (1987) Limit Theorems for Stochastic Processes (Springer, Berlin).Crossref, Google Scholar
• Jean-Marie A, Gün L (1993) Parallel queues with resequencing. J. ACM 40(5):1188–1208.Crossref, Google Scholar
• Jiang L, Giachetti RE (2008) A queueing network model to analyze the impact of parallelization of care on patient cycle time. Health Care Management Sci. 11(3):248–261.Crossref, Google Scholar
• Karatzas I, Shreve SE (1991) Brownian Motion and Stochastic Calculus (Springer, New York).Google Scholar
• Khoshnevisan D (2002) Multiparameter Processes: An Introduction to Random Fields (Springer, New York).Crossref, Google Scholar
• Klementowski LJ (1978) PERT/CPM and Supplementary Analytical Techniques. An Analysis of Aerospace Usage. Technical report, DTIC Document, Defense Technical Information Center, Fort Belvoir, VA.Google Scholar
• Ko S-S, Serfozo RF (2004) Response times in M/M/s fork-join networks. Ad. Appl. Probab. 36(3):854–871.Crossref, Google Scholar
• Ko S-S, Serfozo RF (2008) Sojourn times in G/M/1 fork-join networks. Naval Res. Logist. 55(5):432–443.Crossref, Google Scholar
• Krichagina EV, Puhalskii AA (1997) A heavy-traffic analysis of a closed queueing system with a GI/∞ service center. Queueing Systems 25(1–4):235–280.Crossref, Google Scholar
• Larson RC, Cahn MF, Shell MC (1993) Improving the New York City arrest-to-arraignment system. Interfaces 23(1):76–96.Link, Google Scholar
• Lawler GF, Limic V (2010) Random Walk: A Modern Introduction (Cambridge University Press, New York).Crossref, Google Scholar
• Leadbetter MR, Lindgren G, Rootzén H (1983) Extremes and Related Properties of Random Sequences and Processes (Springer, New York).Crossref, Google Scholar
• Leite SC, Fragoso MD (2008) Heavy traffic analysis of state-dependent parallel queues with triggers and an application to web search systems. Performance Evaluation 67(10):913–928.Crossref, Google Scholar
• Lin M, Zhang L, Wierman A, Tan J (2013) Joint optimization of overlapping phases in MapReduce. Performance Evaluation 70(10):720–735.Crossref, Google Scholar
• Liptser RS, Shiryaev AN (1989) Theory of Martingales (Kluwer, Dordrecht, the Netherlands).Crossref, Google Scholar
• Lu H, Pang G (2014) Heavy-traffic limits for a fork-join network in the Halfin-Whitt regime. Submitted.Google Scholar
• Mandelbaum A, Momčilović P (2008) Queues with many servers: The virtual waiting-time process in the QED regime. Math. Oper. Res. 33(3):561–586.Link, Google Scholar
• Mandelbaum A, Momčilović P (2012) Queues with many servers and impatient customers. Math. Oper. Res. 37(1):41–65.Link, Google Scholar
• Marshall AW, Olkin I (1967) A multivariate exponential distribution. J. Amer. Statist. Assoc. 62(317):30–44.Crossref, Google Scholar
• Neuhaus G (1971) On weak convergence of stochastic processes with multidimensional time parameter. Ann. Math. Statist. 42(4):1285–1295.Crossref, Google Scholar
• Nguyen V (1993) Processing networks with parallel and sequential tasks: Heavy traffic analysis and Brownian limits. Annals of Applied Probability 3(1):28–55.Crossref, Google Scholar
• Nguyen V (1994) The trouble with diversity: Fork-join networks with heterogeneous customer population. Ann. Appl. Probab. 4(1):1–25.Crossref, Google Scholar
• Pang G, Whitt W (2010) Two-parameter heavy-traffic limits for infinite-server queues. Queueing Systems 65(4):325–364.Crossref, Google Scholar
• Pang G, Whitt W (2012) Infinite-server queues with batch arrivals and dependent service times. Probab. Engrg. Informational Sci. 26(2):197–220.Crossref, Google Scholar
• Pang G, Whitt W (2013) Two-parameter heavy-traffic limits for infinite-server queues with dependent service times. Queueing Systems 73(2):119–146.Crossref, Google Scholar
• Philipp W, Pinzur L (1980) Almost sure approximation theorems for the multivariate empirical process. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 54(1):1–13.Crossref, Google Scholar
• Pinotsi D, Zazanis MA (2005) Synchronized queues with deterministic arrivals. Oper. Res. Lett. 33(6):560–566.Crossref, Google Scholar
• Prabhakar B, Bambos N, Mountford TS (2000) The synchronization of Poisson processes and queueing networks with service and synchronization nodes. Ad. Appl. Probab. 32(3):824–843.Crossref, Google Scholar
• Puhalskii AA, Reed JE (2010) On many-server queues in heavy traffic. Ann. Appl. Probab. 20(1):129–195.Crossref, Google Scholar
• Reed JE (2009) The G/GI/N queue in the Halfin-Whitt regime. Ann. Appl. Probab. 19(6):2211–2269.Crossref, Google Scholar
• Sklar A (1959) Fonctions de répartition à n dimensions et leurs marges (Université Paris 8).Google Scholar
• Squillante MS, Zhang Y, Sivasubramaniam A, Gautam N (2008) Generalized parallel-server fork-join queues with dynamic task scheduling. Ann. Oper. Res. 160(1):227–255.Crossref, Google Scholar
• Straf ML (1972) Weak convergence of stochastic processes with several parameters. Proc. Sixth Berkeley Sympos. Math. Statist. Probab. Vol. 2 (University of California Press, Berkeley, CA), 187–221.Google Scholar
• Takahashi M, Ōsawa H, Fujisawa T (2000) On a synchronization queue with two finite buffers. Queueing Systems 36(1–3):107–123.Crossref, Google Scholar
• Talreja R, Whitt W (2009) Heavy-traffic limits for waiting times in many-server queues with abandonment. Ann. Appl. Probab. 19(6):2137–2175.Crossref, Google Scholar
• Tan J, Meng X, Zhang L (2012) Delay tails in MapReduce scheduling. ACM SIGMETRICS Performance Evaluation Rev. 40(1):5–16.Crossref, Google Scholar
• Tan X, Knessl C (1996) A fork-join queueing model: Diffusion approximation, integral representations and asymptotics. Queueing Systems 22(3–4):287–322.Crossref, Google Scholar
• Varki E, Dowdy LW (1996) Analysis of balanced fork-join queueing networks. ACM SIGMETRICS Performance Evaluation Rev. 24(1):232–241.Crossref, Google Scholar
• Varma S (1990) Heavy and light traffic approximations for queues with synchronization constraints. Unpublished doctoral dissertation, University of Maryland.Google Scholar
• Wang W, Zhu K, Ying L, Tan J, Zhang L (2013) Map task scheduling in MapReduce with data locality: Throughput and heavy-traffic optimality. Proc. 32nd IEEE Internat. Conf. Comput. Comm. (INFOCOM) (IEEE, Piscataway, NJ), 1609–1617.Crossref, Google Scholar
• Whitt W (2002) Stochastic-Process Limits (Springer, New York).Crossref, Google Scholar
• Willits CJ, Dietz DC (2001) Nested fork-join queueing network model for analysis of airfield operations. J. Aircraft 38(5):848–855.Crossref, Google Scholar
• Zaied I (2012) The offered load in fork-join networks: Calculations and applications to service engineering of emergency departments. Master’s thesis, Department of Industrial and Management Engineering, Technion—Israel Institute of Technology.Google Scholar
• Zviran A (2011) Fork-join networks in heavy traffic: Diffusion approximations and control. Master’s thesis, Department of Industrial and Management Engineering, Technion—Israel Institute of Technology.Google Scholar