Heavy Traffic Limits for Fork-Join Networks with Synchronization Constraints

Open Access
Author:
Lu, Hongyuan
Graduate Program:
Industrial Engineering
Degree:
Doctor of Philosophy
Document Type:
Dissertation
Date of Defense:
September 09, 2015
Committee Members:
  • Guodong Pang, Dissertation Advisor
  • Necdet S Aybat, Committee Member
  • Manfred Heinz Denker, Committee Member
  • Paul Griffin, Committee Member
  • Vinayak V Shanbhag, Committee Member
Keywords:
  • fork-join networks
  • non-exchangeable synchronization
  • generalized Kiefer process
  • multiparameter sequential empirical process
Abstract:
Fork-join networks are a class of queueing networks, where each arriving job forks into multiple parallel tasks, to be served sequentially and simultaneously in separate service stations and then joined for further processing under some synchronization constraints. Such networks have broad applications in manufacturing and telecommunications, patient flow analysis in healthcare, parallel computing, MapReduce scheduling, military deployment operations and law enforcement systems. In the dissertation, we analyze the performance of fork-join networks with a single class of jobs under non-exchangeable synchronizations (NES). NES requires that parallel tasks are only synchronized if all the tasks associated with the same job are completed. We first study a fork-join network of stations with infinite servers and NES in heavy traffic. Jobs are forked into a fixed number of parallel tasks upon arrival and processed at the corresponding parallel service stations. Service times of parallel tasks of each job can be correlated. We consider 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. We develop a new approach to show a functional central limit theorem (FCLT) for these processes, under general assumptions on the arrival and service processes. Specifically, we represent these processes as functionals of a sequential empirical process driven by the sequence of service vectors for each job’s parallel tasks. All the limiting processes are functionals of two independent processes - the limiting arrival process and a generalized Kiefer process driven by the service vector of each job. We characterize the transient and stationary distributions of the limiting processes. In the second work, we consider fork-join networks with NES in a renewal random environment. The system is operating in a renewal random environment with alternating up and down periods. In each up period, the system operates normally as our first model, 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. 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 and weakly dependent sequence satisfying the phi-mixing condition. We study the impact of 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 a functional weak law of large numbers (FWLLNs) and an FCLT for these processes, where the limit processes in the FCLT possess a stochastic decomposition property and the convergence requires the Skorohod M1 topology. In the third work, we study a fork-join network with NES, where each service station has finite statistically identical parallel servers. Service times of the parallel tasks of each job can be correlated and form a sequence of i.i.d. random vectors with a general continuous joint distribution function. We consider the system in the Halfin-Whitt (Quality-and-Efficiency- Driven, QED) regime, in which the arrival rate of jobs and the number of servers in each station get large appropriately so that all service stations become critically loaded asymp- totically. We study the joint dynamics of the queueing and service processes at all stations and the associated unsynchronized queueing processes. We show FWLLNs and FCLT for these processes. All the limit processes in the FCLT are characterized via functionals of the initial limit quantities, the arrival limit process and a generalized multiparameter Kiefer process driven by the service vectors.