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

random walkqueueing theoryresource poolingadmissions controlfuture informationheavy-traffic asymptotics

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30) 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.

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

• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• 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
• 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)

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

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)