Queuing with future information

DOI10.1214/13-AAP973MaRDI QIDQ744387zbMATH OpenFDO

Authors Kuang Xu, Joel Spencer, Madhu Sudan

Publication date 25 September 2014

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.0618, https://projecteuclid.org/euclid.aoap/1403812371

zbMATH Keywords

admissions controlfuture informationheavy-traffic asymptoticsqueueing theoryrandom walkresource pooling

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Queues and service in operations research (90B22) Stochastic scheduling theory in operations research (90B36)

Abstract: We study an admissions control problem, where a queue with service rate $1-p$ receives incoming jobs at rate $lambdain(1-p,1)$, and the decision maker is allowed to redirect away jobs up to a rate of $p$, with the objective of minimizing the time-average queue length. We show 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 $simlo{g}_{1/(1-p)}frac11-lambda$, as $lambdao1$. In sharp contrast, when all future arrival and service times are revealed beforehand, the optimal average queue length converges to a finite constant, $(1-p)/p$, as $lambdao1$. We further show that the finite limit of $(1-p)/p$ can be achieved using only a finite lookahead window starting from the current time frame, whose length scales as $mathcalO(logfrac11-lambda)$, as $lambdao1$. This leads to the conjecture of an interesting duality between queuing delay and the amount of information about the future.

Review text

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).

Recommendations

• Necessity of future information in admission control
• Optimal control of arrivals to queues with delayed queue length information
• ADMISSION CONTROL WITH INCOMPLETE INFORMATION TO A FINITE BUFFER QUEUE
• On the optimal control of arrivals to a single queue with arbitrary feedback delay
• Admission control to an M/M/1 queue with partial information

Cites work

• Approximation algorithms for the stochastic lot-sizing problem with order lead times
• Asymptotic Blocking Probabilities in Loss Networks with Subexponential Demands
• Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: Asymptotic optimality of a threshold policy
• Heavy traffic resource pooling in parallel-server systems
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• Look-Ahead Policies for Admission to a Single Server Loss System
• Markov Decision Problems and State-Action Frequencies
• On pooling in queueing networks
• On the power of (even a little) resource pooling
• Optimal control of admission to a quenching system
• Reducing the Cost of Demand Uncertainty Through Accurate Response to Early Sales
• Scheduling Flexible Servers with Convex Delay Costs: Heavy-Traffic Optimality of the Generalized cμ-Rule
• Time-average optimal constrained semi-Markov decision processes

Cited in

(5)

• Personalized queues: the customer view, via a fluid model of serving least-patient first
• Necessity of future information in admission control
• An optimal callback policy for general arrival processes: a pathwise analysis
• Information and memory in dynamic resource allocation
• A study of congestion-based information guidance policy for hierarchical healthcare systems

This page was built for publication: Queuing with future information

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744387)