Algorithmic and approzimation analyses of the split and match queue

A queueing system in which an arriving unit “splits” into two subunits, to be served by two independent servers is considered. After service is completed on each of the subunits the "matched" units leave the system. The arrival stream is assumed to be Poisson and the service times for the two subunit streams are assumed to be mutually independent exponentially distributed random variables. By treating one of the queues as bounded, this system is shown to have a matrix-geometric steady state vector which can be computed efficiently. Expressions are developed for the mean, variance and the distribution function of the sojourn time of a unit as well as the interdeparture time of units. Some numerical results are presented, and based on these results an efficient approximation scheme is developed which greatly reduces the required computational effort and permits the evaluation of the characteristics for systems with more than two branches.