It is interesting and challenging to study double-ended queues with First-Come-First-Match discipline under customers impatient behavior and non-Poisson inputs. Note that the system stability can be guaranteed by the customers impatient behavior, but the existence of impatient customers makes analysis of such double-ended queues more difficult or even impossible to find any explicitly analytic solution due to having to deal with more complicated level-dependent Markov processes. Thus it becomes more and more important to develop effective algorithms in a variety of practical matching problems. This paper studies a block-structured double-ended queue, whose block structure comes from two independent Markovian arrival processes (MAPs), which are non-Poisson inputs. We first show that such a queue can be expressed as a new bilateral quasi birth-and-death (QBD) process which has its own interest. Based on this, we provide a detailed analysis for the bilateral QBD process and the double-ended queue, including the system stability, the stationary queue length distributions, the average stationary queue lengths, and the sojourn time of any arriving customers. Then we develop three effective algorithms for computing the performance measures (e.g., the stationary queue length distributions, the average stationary queue lengths, and the average sojourn time) of the double-ended queue. Finally, we use some numerical examples in tabular and graphical to illustrate how the performance measures are influenced by some key system parameters. We believe that the methodology and results given in this paper can be applicable to deal with more general double-ended queues in practice, and develop effective algorithms for the purpose of many actual uses.
Download