Asymptotic optimality of maximum pressure policies in stochastic processing networks

DOI10.1214/08-AAP522MaRDI QIDQ2378631zbMATH OpenOpenAlexFDO

Authors J. G. Dai, Wuqin Lin

Publication date 13 January 2009

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

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

zbMATH Keywords

diffusion limitsheavy trafficasymptotic optimalitystate space collapsemaximum pressure policiesBrownian modelsstochastic processing networksbackpressure policies

Mathematics Subject Classification ID

Diffusion processes (60J60) Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Stochastic network models in operations research (90B15) Communication networks in operations research (90B18) Network design and communication in computer systems (68M10)

Abstract: We consider a class of stochastic processing networks. Assume that the networks satisfy a complete resource pooling condition. We prove that each maximum pressure policy asymptotically minimizes the workload process in a stochastic processing network in heavy traffic. We also show that, under each quadratic holding cost structure, there is a maximum pressure policy that asymptotically minimizes the holding cost. A key to the optimality proofs is to prove a state space collapse result and a heavy traffic limit theorem for the network processes under a maximum pressure policy. We extend a framework of Bramson [Queueing Systems Theory Appl. 30 (1998) 89--148] and Williams [Queueing Systems Theory Appl. 30 (1998b) 5--25] from the multiclass queueing network setting to the stochastic processing network setting to prove the state space collapse result and the heavy traffic limit theorem. The extension can be adapted to other studies of stochastic processing networks.

Recommendations

• Heavy traffic analysis of maximum pressure policies for stochastic processing networks with multiple bottlenecks
• From local to global stability in stochastic processing networks through quadratic Lyapunov functions
• Maximum Pressure Policies in Stochastic Processing Networks
• Heavy traffic analysis of open processing networks with complete resource pooling: asymptotic optimality of discrete review policies
• Stability and Asymptotic Optimality of Generalized MaxWeight Policies

Cites work

• scientific article; zbMATH DE number 1631026 (Why is no real title available?)
• scientific article; zbMATH DE number 3912096 (Why is no real title available?)
• scientific article; zbMATH DE number 3951715 (Why is no real title available?)
• scientific article; zbMATH DE number 4076265 (Why is no real title available?)
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• scientific article; zbMATH DE number 1022519 (Why is no real title available?)
• scientific article; zbMATH DE number 1936531 (Why is no real title available?)
• scientific article; zbMATH DE number 932422 (Why is no real title available?)
• scientific article; zbMATH DE number 932423 (Why is no real title available?)
• scientific article; zbMATH DE number 964349 (Why is no real title available?)
• A broader view of Brownian networks
• A large deviations approach to asymptotically optimal control of crisscross network in heavy traffic
• A multiclass Station with Markovian Feedback in Heavy Traffic
• Adaptive back-pressure congestion control based on local information
• Allocation of interdependent resources for maximal throughput
• An invariance principle for semimartingale reflecting Brownian motions in an orthant
• Brownian models of open processing networks: Canonical representation of workload.
• Diffusion approximations for open multiclass queueing networks: Sufficient conditions involving state space collapse
• Diffusion approximations for some multiclass queueing networks with FIFO service disciplines
• Dynamic control of Brownian networks: State space collapse and equivalent workload formulations
• Dynamic scheduling of a parallel server system in heavy traffic with complete resource pooling: asymptotic optimality of a threshold policy
• Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: Asymptotic optimality of a threshold policy
• Dynamic server allocation to parallel queues with randomly varying connectivity
• Heavy Traffic Convergence of a Controlled, Multiclass Queueing System
• Heavy traffic analysis of a system with parallel servers: Asymptotic optimality of discrete-review policies
• Heavy traffic analysis of open processing networks with complete resource pooling: asymptotic optimality of discrete review policies
• Heavy traffic limits for some queueing networks
• Heavy traffic resource pooling in parallel-server systems
• Instability of FIFO queueing networks
• MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic
• Maximum Pressure Policies in Stochastic Processing Networks
• Multiple channel queues in heavy traffic. I
• On dynamic scheduling of a parallel server system with complete resource pooling
• On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models
• Re-entrant lines
• Resource Allocation and Cross-Layer Control in Wireless Networks
• Scheduling Flexible Servers with Convex Delay Costs: Heavy-Traffic Optimality of the Generalized cμ-Rule
• Scheduling networks of queues: Heavy traffic analysis of a simple open network
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
• State space collapse with application to heavy traffic limits for multiclass queueing networks
• Stochastic discrete flow networks: Diffusion approximations and bottlenecks
• Two workload properties for Brownian networks
• Uniqueness of solution in linear programming

Cited in

(32)

• Optimal control of parallel server systems with many servers in heavy traffic
• On the asymptotic optimality of the \(c\mu\)-rule in queueing networks
• Optimal switching policy for batch servers
• Randomized scheduling algorithm for queueing networks
• A survey on skill-based routing with applications to service operations management
• Diffusion approximations for controlled weakly interacting large finite state systems with simultaneous jumps
• Controlled stochastic networks in heavy traffic: convergence of value functions
• Static routing in stochastic scheduling: performance guarantees and asymptotic optimality
• Heavy-Traffic Analysis of Queueing Systems with No Complete Resource Pooling
• Fluid models of congestion collapse in overloaded switched networks
• Fluctuation Bounds for the Max-Weight Policy with Applications to State Space Collapse
• A push-pull network with infinite supply of work
• Near optimal control of queueing networks over a finite time horizon
• Justifying diffusion approximations for multiclass queueing networks under a moment condition
• Switched networks with maximum weight policies: fluid approximation and multiplicative state space collapse
• Control of fork-join processing networks with multiple job types and parallel shared resources
• Brownian inventory models with convex holding cost. I: Average-optimal controls
• On the control of fork-join networks
• Stability and Asymptotic Optimality of Generalized MaxWeight Policies
• Heavy traffic analysis of maximum pressure policies for stochastic processing networks with multiple bottlenecks
• Optimal queue-size scaling in switched networks
• A load balancing system in the many-server heavy-traffic asymptotics
• Diffusion limit of fair resource control -- stationarity and interchange of limits
• Transform methods for heavy-traffic analysis
• Asymptotically tight steady-state queue length bounds implied by drift conditions
• Ergodic control of resource sharing networks: lower bound on asymptotic costs
• Managing flexibility: optimal sizing and scheduling of flexible servers
• A fluid approach to large volume job shop scheduling
• On converse Lyapunov theorems for fluid network models
• Maximum Pressure Policies in Stochastic Processing Networks
• The single-server scheduling problem with convex costs
• Diffusion approximations for load balancing mechanisms in cloud storage systems

This page was built for publication: Asymptotic optimality of maximum pressure policies in stochastic processing networks

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