  It is interesting and challenging to study double-ended queues with
First-Come-First-Match discipline under customers' impatient behavior and
non-Poisson inputs. The system stability can be guaranteed by the customers'
impatient behavior, while the existence of impatient customers makes analysis
of such double-ended queues more difficult or even impossible to find an
explicitly analytic solution, thus it becomes more and more important to
develop effective numerical methods 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 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 both the bilateral QBD process and
the double-ended queue, including the system stability, the queue size
distributions, the average stationary queue lengths, and the sojourn time of
any arriving customers. Furthermore, we develop three effective algorithms for
computing the performance measures (i.e., the probabilities of stationary queue
lengths, the average stationary queue lengths, and the average sojourn times)
of the double-ended queue with non-Poisson inputs. 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 described in this paper can be applicable to deal with
more general double-ended queues in practice, and develop some effective
algorithms for the purpose of many actual uses.
