Analytic approximations of fork-join queues

摘要

Fork-join queues characterize a network of parallel servers where an arriving job splits into subtasks, and are serviced in parallel. Exact analytic results are known for the mean response time of a two server system. For more than two parallel servers, approximations for the mean response time of both homogeneous and heterogeneous servers have been found. One such approximation is a split-merge queue, which is a type of fork-join queue; and, it is known that the response time yields an approximation and upper bound for the mean response time in the fork-join queue. In this study, we develop a matrix exponential representation of the maximum order statistic of the service time distribution for homogeneous and heterogeneous split-merge queues. We then apply these results to the M/G/1 queue, which enables us to derive the queue length distribution, the response time distribution, and other performance measures for split-merge queues that can be used as approximations and upper-bounds of fork-join queues.