Queuing with future information (Q744387)

The paper under review studies the following admission control problem. Consider a single queue equipped with a server that runs at rate \(1-p\) jobs per unit time where \(p\) is a fixed constant in \((0,1)\). The queue receives a stream of incoming jobs, arriving at rate \(\lambda\in(0,1)\). If \(\lambda>1-p\), then the arrival rate is greater than the processing rate of the server, and, in order to keep the system stable, some admission control is required. In particular, upon its arrival to the system, a job will either be admitted to the queue or redirected, or, in other words, it does not enter this specific queueing system and is lost. Then, the goal of the decision maker is to minimize the average delay experienced by admitted jobs, under the constraint that the average rate at which jobs are redirected does not exceed \(p\). The closely related model can be found in [\textit{J. N. Tsitsiklis} and \textit{K. Xu}, Stoch. Syst. 2, No. 1, 1--66 (2012; Zbl 1296.60253)]. The paper under review shows ``that the amount of information about the future has a significant impact on system performance in the heavy-traffic regime. When the future is unknown, the optimal average queue length diverges at rate \(\log_{1/(1-p)}\frac{1}{1-\lambda}\) as \(\lambda\to1\). In sharp contrast, when all future arrival and service times are revealed beforehand, the optimal average queue length converges to a finite constant, \(\frac{1-p}{p}\), as \(\lambda\to1\). Then it is shown that the finite limit of \(\frac{1-p}{p}\) can be achieved using only a finite look-ahead window starting from the current time frame, whose length scales as \(O(\log\frac{1}{1-\lambda})\) as \(\lambda\to1\). This leads to the conjecture of an interesting duality between queuing delay and the amount of information about the future'' (from the authors' abstract).