Asymptotic optimality of maximum pressure policies in stochastic processing networks
From MaRDI portal
Publication:2378631
DOI10.1214/08-AAP522zbMATH Open1175.90083arXiv0901.2451OpenAlexW3099615934MaRDI QIDQ2378631FDOQ2378631
Publication date: 13 January 2009
Published in: The Annals of Applied Probability (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0901.2451
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
diffusion limitsheavy trafficasymptotic optimalitystate space collapsemaximum pressure policiesBrownian modelsstochastic processing networksbackpressure policies
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models
- Title not available (Why is that?)
- Uniqueness of solution in linear programming
- Multiple channel queues in heavy traffic. I
- Stochastic discrete flow networks: Diffusion approximations and bottlenecks
- Title not available (Why is that?)
- MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic
- Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
- Scheduling Flexible Servers with Convex Delay Costs: Heavy-Traffic Optimality of the Generalized cμ-Rule
- Heavy traffic analysis of a system with parallel servers: Asymptotic optimality of discrete-review policies
- Title not available (Why is that?)
- Dynamic server allocation to parallel queues with randomly varying connectivity
- Adaptive back-pressure congestion control based on local information
- Instability of FIFO queueing networks
- Heavy traffic resource pooling in parallel-server systems
- An invariance principle for semimartingale reflecting Brownian motions in an orthant
- Diffusion approximations for open multiclass queueing networks: Sufficient conditions involving state space collapse
- State space collapse with application to heavy traffic limits for multiclass queueing networks
- Heavy traffic analysis of open processing networks with complete resource pooling: asymptotic optimality of discrete review policies
- Scheduling networks of queues: Heavy traffic analysis of a simple open network
- Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: Asymptotic optimality of a threshold policy
- Title not available (Why is that?)
- Dynamic scheduling of a parallel server system in heavy traffic with complete resource pooling: asymptotic optimality of a threshold policy
- Resource Allocation and Cross-Layer Control in Wireless Networks
- A broader view of Brownian networks
- Brownian models of open processing networks: Canonical representation of workload.
- Title not available (Why is that?)
- Maximum Pressure Policies in Stochastic Processing Networks
- Dynamic control of Brownian networks: State space collapse and equivalent workload formulations
- Two workload properties for Brownian networks
- Re-entrant lines
- A large deviations approach to asymptotically optimal control of crisscross network in heavy traffic
- Title not available (Why is that?)
- On dynamic scheduling of a parallel server system with complete resource pooling
- Allocation of interdependent resources for maximal throughput
- Heavy traffic limits for some queueing networks
- Title not available (Why is that?)
- Heavy Traffic Convergence of a Controlled, Multiclass Queueing System
- Diffusion approximations for some multiclass queueing networks with FIFO service disciplines
- A multiclass Station with Markovian Feedback in Heavy Traffic
Cited In (32)
- Optimal switching policy for batch servers
- Optimal control of parallel server systems with many servers in heavy traffic
- On the asymptotic optimality of the \(c\mu\)-rule in queueing networks
- 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
- Fluctuation Bounds for the Max-Weight Policy with Applications to State Space Collapse
- Fluid models of congestion collapse in overloaded switched networks
- Justifying diffusion approximations for multiclass queueing networks under a moment condition
- A push-pull network with infinite supply of work
- Near optimal control of queueing networks over a finite time horizon
- 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
- Maximum Pressure Policies in Stochastic Processing Networks
- A fluid approach to large volume job shop scheduling
- On converse Lyapunov theorems for fluid network models
- 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)
