2:00 pm Friday, May 9, 2014
Random Structures : Fork-Join Networks with Non-Exchangeable Synchronization in Heavy Traffic by
Gordon (Guodong) Pang [mail] (Pennsylvania State University) in RLM 8.136
Fork-join networks consist of a set of service stations that serve job requests simultaneously and sequentially according to pre-designated deterministic precedence constraints. Such networks have many applications in manufacturing and telecommunications, patient flow analysis in healthcare and parallel computing. We are primarily motivated by patient flow analysis in hospitals, where as a prerequisite for a doctor examination, all the tests results for the same patient must be ready, and they cannot be mixed among patients. We call this type of constraint as non-exchangeable synchronization (NES), that is, each job can be synchronized only if all of its asks are completed. A main challenge to study fork-join networks with NES is the resequencing of tasks’ arrival orders at each service station after service completion. We tackle the resequencing issue when each service station has multiple servers under the FCFS discipline. In this talk, we focus on a fundamental fork-join network model with a single class of jobs and NES in the many-server heavy-traffic regimes. Upon service completion, each parallel task will join a buffer associated with its service station and wait for synchronization. The goal is to understand the waiting buffer dynamics for synchronization as well as the service dynamics. We develop a new approach to show functional central limit theorems for the number of tasks in each waiting buffer for synchronization jointly with the number of tasks in each parallel service station and the number of synchronized jobs, under general assumptions on the arrival and service processes. All the limiting processes are functionals of two independent processes, the arrival limit process and the generalized Kiefer process driven by the service vector for the parallel tasks. We characterize the transient and stationary distributions of these limiting processes.
Submitted by