Some Recent Work and Further Problems in the Theory of Queues

1. Introduction. The significance of A.Ẏa Khinchin's work. 2. Restoring the Markovian Character to Non-Markovian Queues. “Lumping” of the states of a Markov process. The inverse transition of Markov processes by means of “un-lumping” of states (by introducing supplementary variables). “Imbedding” of Markov chains. Possible waiting time. Use of generalized Erlang distributions. The problem of extending a chain with discrete time to a chain with continuous time. 3. The detailed Analysis of Markovian Queues. Derivation of ergodic limits. The problem concerning the spread of convergence; geometric ergodicity. Integral representations; reversibility.4. Special Methods: (a) Approximations. The effect of perturbation of the initial distributions. Approximation in heavy traffic. 5. Special Methods: (b) Decompositions, Dualities, Combinatorial Methods. Runnenberg's interpretation of Pollaczek's formula. Prabhu's work on the “busy period”. Spitzer's identity and its relation to the theory of queues. 6. More General Inputs and Outputs. Classical input streams. The problem of delayed input and its connection to the queueing problem with sequential service by several servers. The identification problem; infinite permutations connected with queues. Winsten's work on bounded delays. Connection with the contemporary investigations of point processes.