Queuing with future information

DOI10.1214/13-AAP973zbMATH Open1309.60090arXiv1211.0618MaRDI QIDQ744387FDOQ744387

Authors: Kuang Xu, Joel Spencer, Madhu Sudan 

Publication date: 25 September 2014

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

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.

Full work available at URL: https://arxiv.org/abs/1211.0618

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

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)

Cites Work

• Optimal control of admission to a quenching system
• Title not available (Why is that?)
• 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
• On pooling in queueing networks
• Approximation algorithms for the stochastic lot-sizing problem with order lead times
• Heavy traffic resource pooling in parallel-server systems
• On the power of (even a little) resource pooling
• Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: Asymptotic optimality of a threshold policy
• Time-average optimal constrained semi-Markov decision processes
• Markov Decision Problems and State-Action Frequencies
• Look-Ahead Policies for Admission to a Single Server Loss System
• Asymptotic Blocking Probabilities in Loss Networks with Subexponential Demands

Cited In (5)

• Personalized queues: the customer view, via a fluid model of serving least-patient first
• Information and memory in dynamic resource allocation
• An optimal callback policy for general arrival processes: a pathwise analysis
• Necessity of future information in admission control
• 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)