[PAST EVENT] Mathematics Colloquium and EXTREEMS-QED Lecture: Guodong (Gordon) Pang (Penn State University)

February 6, 2015
2pm - 3pm
Jones Hall, Room 301
200 Ukrop Way
Williamsburg, VA 23185Map this location
Abstract: 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 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 after all of its tasks are completed. A main challenge to study fork-join networks with NES under the FCFS service discipline is the resequencing of tasks arrival orders at each multi-server service station after service completion. We develop a new framework to solve the resequencing issue in the many-server heavy-traffic regimes where the arrival rates and the numbers of servers in each station get large appropriately.

In this talk, we focus on a fundamental fork-join network model with a single class of jobs and NES. Upon service completion, each parallel task will join a buffer associated with its service station and wait for synchronization. Service times of the parallel tasks of each job can be correlated. The goal is to understand the waiting buffer dynamics for synchronization as well as the service dynamics. We 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, in the many-server asymptotic regimes, 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. We also discuss how the results can be used for staffing and stabilizing some performance measures when the demand is time-varying and how the framework can be generalized to study multiclass fork-join network models.

Sarah Day