Greedy algorithm, $Z^1$ case

I.A. Kurkova, M.V. Menshikov

1997, v.3, Issue 2, 243-259

ABSTRACT

We consider a single server queueing system with stations in all integer points of the real line. The customers arrival streams at the different stations are independent Poisson processes. The service times of customers are mutually independent and exponentially distributed. The server serves each station exhaustively, i.e. till the station is empty. The next station to be served, is selected using the greedy algorithm: the server goes to the neighbouring station with the maximum number of customers. We study the trajectories of the server and his asymptotic position, as time tends to infinity.

Keywords: queueing system,Poisson stream,greedy server,Markov chain,transience