Control of Fork-Join Networks in heavy traffic

A Fork-Join Network (FJN) is a natural model for a queueing system in which customers, or rather tasks associated with customers, are processed both sequentially and in parallel. In this paper we analyze a network that, in addition, accommodates feedback of tasks. An example of a FJN is an assembly operation, where parts are first produced and then assembled to ultimately create a final product. Another example is an emergency department, where a patient “forks” into, say, a blood test and an X-ray, which must then “join” the patient as a prerequisite for a doctor examination. There is a fundamental difference between the dynamics of these two examples: In an assembly network, parts are exchangeable while, in an emergency department, tasks are associated uniquely with patients. They are thus nonexchangeable in the sense that one cannot combine/join tasks associated with different customers. In single-server feed-forward FJNs, FCFS processing maintains a fully synchronized flow of tasks. Probabilistic feedback, however, introduces flow disruptions that give rise to task delays and ultimately a decrease in throughput rate. Nevertheless, we show that a simple flow control of tasks can render this decrease of performance asymptotically negligible (though it is not absolutely negligible). More specifically, we analyze a concrete FJN, with nonexchangeable tasks and Markovian feedback, in the conventional heavy-traffic (diffusion) regime. We prove asymptotic equivalence between this network and its corresponding assembly network (exchangeable tasks), thus establishing asymptotic throughput-optimality of our control. The analysis also reveals further interesting properties, such as state-space collapse of synchronization queues.